Технологии высокопроизводительных вычислений

Данная задача является краевой задачей для уравнения в частных производных (уравнения теплопроводности), которую можно приблизить задачей на равномерной четырехугольной сетке. Сеточную задачу, в свою очередь, можно решать итерационным методом – мы выберем метод Якоби. Численный метод, к которому мы приходим, двигаясь упомянутым путем, очень прост.

Имеется двумерный массив F, значения элементов которого – это нормализованные значения температуры в узлах сетки, «наброшенной» на срез кирпича. По краям массива находятся значения температуры утюгов – граничные условия. Они в процессе расчета не изменяются. Со всеми остальными значениями поступаем так:

- для каждой ячейки вычисляем новое значение как среднее арифметическое значений четырех ее соседей,

- после того, как новые значения вычислены для всех ячеек, заменяем старые значения новыми, попутно вычисляя максимум абсолютной величины отклонения новых значений от старых,

- повторяем эти два шага до тех пор, пока максимум абсолютной величины отклонения не станет меньше заданного порога малости.

Для упрощения наших модельных рассмотрений исключим из алгоритма вычисление отклонений – будем выполнять фиксированное число итераций. Вот текст последовательной (для одного процессора) реализации этой вычислительной процедуры:

#include <stdio.h>

/***/

#define MX 640

#define MY 480

#define NITER 10000

#define STEPITER 100

       static float  f[MX][MY];

       static float df[MX][MY];

/***/

       int main( int argc, char **argv )

{

       int i, j, n, m;         

/***/

       printf( "Solving heat conduction task on %d by %d grid\n",

                MX, MY );             

       fflush( stdout );

/* Initial conditions: */

       for ( i = 0; i < MX; i++ )

        {

              for ( j = 0; j < MY; j++ )

                {

                 f[i][j] = df[i][j] = 0.0;

                 if      ( (i == 0)

                        || (j == 0) ) f[i][j] = 1.0;

                 else if ( (i == (MX-1))

                        || (j == (MY-1)) ) f[i][j] = 0.5;

                }

              }

/* Iteration loop: */

       for ( n = 0; n < NITER; n++ )

        {

              if ( !(n%STEPITER) ) printf( "Iteration %d\n", n );

/* Step of calculation starts here: */

              for ( i = 1; i < (MX-1); i++ )

                {

                 for ( j = 1; j < (MY-1); j++ )

                  {

                   df[i][j] = ( f[i][j+1] + f[i][j-1] + f[i-1][j] + f[i+1][j] )

                              * 0.25 - f[i][j];

                  }

                }

              for ( i = 1; i < (MX-1); i++ )

                {

                 for ( j = 1; j < (MY-1); j++ )

                  {

                   f[i][j] += df[i][j];

                  }

                }

              }

/* Calculation is done, F array is a result: */      

       return 0;

}

1.5.2. Параллельная реализация «на бумаге».

Простейшая параллельная реализация очевидна. Поделим массивы F и DF на горизонтальные полосы (группы строк) равной высоты, по числу процессоров.  Пусть каждый процессор обрабатывает свою полосу на каждой итерации.

Если наша машина – SMP-система, то параллельную реализацию мы построили. Если это – NUMA-система, то мы ее построили, при условии, что нам удастся расположить каждую полосу массивов F и DF в памяти, «своей» для обрабатывающего эти полосы процессора.

Нас сейчас, с учетом сказанного выше, интересует случай, когда расчет выполняется на MPP-системе (например, на вычислительном кластере). В этом случае задачу построения параллельной реализации нельзя считать законченной, поскольку непонятно, что делать с краями полосы массива F. В самом деле, вычисляя первую и последнюю строки полосы, процессор, вообще говоря, вынужден воспользоваться крайними строками соседних полос, а эти строки расположены на соседних процессорах. Следовательно, надо отводить полосы с «запасом» в одну строку в начале и одну в конце, а перед началом каждой итерации предусмотреть в программе передачу данных из краев полосы каждого процессора в «запасные» строки соседних процессоров, чтобы каждый из процессоров располагал свежей копией «соседских» краев, насчитанной на прошлой итерации. Теперь параллельную реализацию «на бумаге» можно считать построенной и для случая кластера. Далее будем, если явно не оговорено противное, говорить только о кластерах (точнее, об MPP-системах без общей памяти).

1.5.3. Что потребуется для параллельной реализации на практике.

Попытаемся реализовать на практике то, что так просто и логично выглядит на бумаге. С одной стороны, имеется кластер, например, из 8-ми процессоров. Это компьютеры, каждый – со своей ОС, и они связаны сетью. С другой стороны, имеется понимание, какая программа должна выполняться на каждом из них, и общее представление о том, как (на содержательном уровне) эти программы должны обмениваться данными друг с другом.

Означает ли это, что мы должны написать 8 исходных текстов, разложить по узлам кластера 8 исполняемых модулей, а затем, быстро перебегая от клавиатуры к клавиатуре, запустить все это на 8-ми компьютерах? И как эти исполняемые модули потом свяжутся друг с другом для обмена данными? Вопрос риторический – в курсе Параллельных и распределенных вычислений рассказывалось, как обстоит дело на самом деле. Осталось перечислить компоненты программного обеспечения кластера, которые нам потребуются, чтобы избежать описанной только что гипотетической страшной картины.

1.6. Общий состав программного обеспечения вычислительного кластера.

1). Каждый узел кластера должен быть оснащен ОС узла, включая необходимую сетевую поддержку, возможно, специального, применяемого только в вычислительных кластерах, сетевого оборудования и/или специальных сетевых протоколов.

2). Весьма желательно, чтобы все узлы имели доступ к общей сетевой файловой системе.

3). Для записи передачи данных из узла в узел должна быть предусмотрена коммуникационная библиотека (обычно – реализация MPI), часто опирающаяся на специальную сетевую поддержку.

4). С коммуникационной библиотекой должна быть интегрирована система запуска параллельных программ. Это – именно тот компонент, который «раскидывает» (автоматически, при помощи стандартных сетевых возможностей) исполняемый модуль по всем компьютерам, заботясь при этом о том, чтобы, начав выполняться, эти программы установили связь друг с другом, и могли обмениваться данными.

5). Наконец, если кластер используется как машина коллективного пользования, с системой запуска интегрируется система очередей и контроля доступа.

6). В свою очередь, над коммуникационными библиотеками типа MPI нередко надстраиваются, для удобства разработки прикладных программ, более высокоуровневые библиотеки и языки параллельного программирования.

7). Если, помимо всего прочего, предусмотрено использование кластера как части распределенного вычислительного ресурса, объединяющего многие, независимо администрируемые, суперкомпьютеры, придется добавить еще и средства метакомпьютинга (GRID – технологий). Эти средства неизбежно затрагивают системы запуска, очередей и контроля доступа, но могут включать в себя и программные надстройки над коммуникационной библиотекой.

В дальнейшем изложении мы обратим внимание на то, какие из упомянутых технологий при построении кластера заимствуются в готовом виде из мира компьютерных технологий массового применения, а какие разрабатываются специально для вычислительных кластеров.

1.7. Некоторые основные определения.

Программа, выполняющаяся на узле параллельной вычислительной системы, и взаимодействующая при этом с себе подобными, называется ветвью параллельной программы.

Вся совокупность взаимодействующих ветвей называется параллельной программой.

Совокупность даваемых программистом ответов на 3 вопроса:

-         как делится работа между ветвями параллельной программы,

-         как делятся данные между ветвями параллельной программы,

-         когда и какие данные передаются между ветвями

называется схемой параллелизма.

При записи в программе обменов сообщениями между ветвями могут использоваться различные программистские модели передачи данных. Наиболее часто используется модель двустороннего рандеву, при которой данные передаются от передатчика к приемнику тогда и только тогда, когда передатчик выдает запрос на передачу данных, а приемник, соответственно, на прием. Порядок срабатывания передатчика и приемника не существенен – синхронизация, то есть «ожидание опоздавшего», происходит автоматически, внутри коммуникационной библиотеки.

Помимо всевозможных высокоуровневых программных надстроек, облегчающих запись двустороннего рандеву в программе, имеются также базовые модели, принципиально отличные от двустороннего рандеву, например, модель односторонней передачи сообщений [1,2,3].

1.8. Технологии параллельной обработки данных без использования суперкомпьютеров.

Возможность организовать как можно более тесное взаимодействие между ветвями параллельной программы в процессе совместной работы ветвей над решением единой задачи принципиально важна для программиста, и разработчики вычислительных кластеров стараются оснастить свои изделия как можно более быстрыми сетями. Однако, существует (хотя и не является преобладающим в процентном отношении) довольно обширный класс задач, при решении которых взаимодействие между ветвями параллельной программы вообще не требуется. Точнее, оно требуется в начале и в конце решения задачи, но объем его пренебрежимо мал по сравнению с объемом самого расчета, который выполняется ветвями полностью независимо. Это так называемый вариантный счет, когда необходимо выполнить очень много одинаковых расчетов с различными исходными данными, а интеграция полученных результатов сравнительно не сложна. Поскольку взаимодействие между ветвями не требуется, ветви могут выполняться в разном темпе, например, на однопроцессорных машинах с разным быстродействием. Интеграция результатов откладывается «на потом», когда посчитанных вариантов накопится много. В отличие от традиционных суперкомпьютерных технологий, обозначаемых термином HPC (High Performance Computing – Высокопроизводительные вычисления), технологии вариантного счета принято обозначать термином HTC (High Throughput Computing – удачного русского термина пока нет). Для таких расчетов нет нужды строить суперкомпьютер – гораздо полезнее разработать программные средства отбора неиспользуемой вычислительной мощности из сетей общего назначения. Это – совершенно особая область, которую мы не будем рассматривать в нашем курсе специально. Здесь речь идет о задаче метакомпьютинга в ее наиболее общем виде. Периодически делаются попытки, наложив некоторые ограничения на дисциплину отбора мощности, все же воспользоваться технологиями метакомпьютинга для решения задач в дисциплине HPC, то есть организовать выполнение «кластерных», параллельных программ не на выделенном оборудовании, а на системах программного отбора мощности. В общем виде это сложнейшая технологическая задача. Некоторые частные варианты ее решения могут быть просты и, до некоторой степени, полезны. Об одном из таких решений – проекте МВС – 900 – мы поговорим в нашем курсе [1,2,3].

2. Некоторые основные понятия архитектуры процессоров и ОС.

Материал этого раздела не имеет суперкомпьютерной специфики. Эти сведения обычно излагаются во вводных курсах программирования для профильных специальностей. Однако, как показывает опыт, современные технологии разработки программ позволяют большинству студентов сочетать вполне удовлетворительный для работы программистом уровень практических знаний с неоправданно абстрактным, поверхностным представлением об основах работы компьютера как такового. Там, где требуется быстро и эффективно программировать в рамках устоявшихся технологий, это оправданно. Для разработчика банковских приложений знание о различиях между системами команд Pentium и Itanium – непозволительная роскошь и «засорение мозгов». Полезнее знать о конкретном способе реализации наследования и полиморфизма в Borland C++. Для разработчика суперкомпьютера, главная работа которого – создавать и помогать осваивать принципиально новые технологии использования оборудования, напротив, незнание того, что процессоры бывают с разной системой команд, а команды обращения к памяти – это совсем не то же самое, что команды работы с портами ввода-вывода – совершенно непозволительная роскошь. Начнем с определения некоторых основных понятий, которые зачастую воспринимаются как почти гуманитарные эпитеты, в то время как в действительности они имеют строгий инженерный смысл.

2.1. Некоторые основные определения.

1). Архитектурой называется функциональное описание объекта, то есть описание того, как он «виден» пользователю. Например, система команд процессора относится к его архитектуре, размер кэш – тоже, а технология изготовления кристалла, на котором выполнен микропроцессор – не относится. Это, в противоположность архитектуре, уже реализация процессора. Архитектура – что сделано, реализация – как сделано.

2). Виртуальное (нечто) – это нечто, не существующее, но представляющееся существующим. Виртуальная сеть – так организованная дисциплина передачи данных, как будто бы там был отдельный сегмент сети, в то время как никакого отдельного сегмента в действительности нет.

3). Прозрачное (нечто) – это нечто, существующее, но представляющееся несуществующим. При попытке пойти по ссылке на интересующий Вас сайт Интернет конкретная структура Интернет для Вас прозрачна. Ваши действия не зависят от того, в соседней комнате сайт или в Австралии.

Для иллюстрации еще нескольких важных понятий нам потребуется базовое представление об устройстве ЭВМ на уровне системы команд. Это представление потребуется нам не само по себе. Цель предстоящего краткого обзора в том, чтобы сформулировать минимальный и исчерпывающий перечень возможностей оборудования, на котором строится все многообразие программистских технологий. Именно исчерпывающий. Важно понимать не столько то, что излагаемые ниже возможности присущи аппаратуре, наряду с множеством других возможностей, сложных и загадочных, сколько то, что ничего принципиально другого в аппаратуре нет, и именно необходимость опираться на этот очень узкий набор базовых возможностей делает программное обеспечение таким, каким оно является. В качестве критерия полноты наших базовых представлений предлагается мысленный эксперимент. Начав с простейшего примера фон Неймановского процессора, будем постепенно обогащать его возможностями, до тех пор, пока не станет ясно, что на имеющемся наборе возможностей можно в принципе построить ОС Windows (или Linux) в том виде, в каком мы ее знаем.