Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.parallel.ru/sites/default/files/ftp/chg99/Berzigiyarov.doc Дата изменения: Wed Nov 2 11:53:58 2011 Дата индексирования: Tue Oct 2 03:05:48 2012 Кодировка: koi8-r

ТЕХНОЛОГИЯ РАЗРАБОТКИ МАСШТАБИРУЕМЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ДЛЯ SMP-
СИСТЕМ НА БАЗЕ MPI

Берзигияров П.К., Султанов В.Г.

Институт Проблем Химической Физики РАН
142432, Московская область, Черноголовка
parvaz@pro.icp.ac.ru, sultan@ficp.ac.ru

На примере задачи численного моделирования на супер-ЭВМ сложных
трехмерных течений, возникающих при развитии гидродинамических Релей-
Тейлоровских неустойчивостей, рассматриваются технологические аспекты
разработки масштабируемых параллельных вычислений для SMP-систем с
использованием библиотеки MPI. Получены расчетные значения ускорений,
позволяющие оценить масштабируемость алгоритма и его программной
реализации. Приведены значения ускорений, полученные в ходе
вычислительного эксперимента.

1. ВВЕДЕНИЕ

Разработка программных комплексов для проведения крупномасштабных
вычислительных экспериментов на параллельных вычислительных системах
представляет собой сложную в теоретическом и практическом плане задачу.
Существует большое количество работ посвященных различным аспектам
параллельного программирования. Как правило, та или иная методология
программирования иллюстрируется на сравнительно несложных задачах, и
относится, главным образом, к программированию "в малом". Типичными
примерами такого рода задач служат программы для реализации отдельных
алгоритмов из области линейной алгебры [1-3], программы для параллельного
вычисления числа ( [1,2,4] и т.д. Очевидно, что разработка параллельных
программ практического уровня сложности представляет собою многоэтапный
технологический процесс и не может быть продемонстрирована во всей своей
полноте на таких задачах. Говоря о технологии программирования, мы
подразумеваем все этапы разработки параллельной программы, начиная с
анализа задачи, выбора модели программы, декомпозиции задачи на
параллельные процессы и заканчивая вопросами анализа производительности и
организации вычислительного эксперимента.
Применение той или иной технологии программирования в значительной
мере определяется языковыми и инструментальными средствами параллельного
программирования. В последнее время широкую популярность получила
библиотека MPI (Message Passing Interface) [1-3, 5-7], представляющая собою
стандартизованный набор средств для обмена сообщениями. MPI включает
средства для организации индивидуальных типа "точка-точка" и коллективных
взаимодействий типа "один-ко-всем", "все-ко-всем". Поддерживаются все типы
данных для Фортрана и Си. Обеспечивается возможность задания
пользовательских топологий процессов (решетка, куб, тор и др.). На
сегодняшний день MPI является стандартом "де-факто" для программирования
систем с массовым параллелизмом. Известно большое количество реализаций для
всех наиболее известных архитектур, включающих не только системы с
распределенной памятью, основанными на обмене сообщениями, но и системы с
общей памятью. Важными особенностями библиотеки являются портируемость,
универсальность и простота. Все это обеспечивает хорошую основу для
переноса параллельных приложений с одной платформы на другую.
Другим, определяющим фактором, влияющим на технологию разработки
параллельных программ, является архитектурный аспект. Наиболее известными
типами архитектур являются векторно-конвейерные системы типа CRAY Y-MP[8],
системы с распределенной памятью [9-10] и системы с общей памятью
[11,16,17]. На сегодняшний день широкое распространение получили системы с
симметричной мультипроцессорностью или SMP-системы[11,16,17]. Типичным
представителями такого рода систем являются HP 9000 V-class[11], а также
используемая авторами SMP-система RM-600 E20/E60 Siemens Nixdorf [16,17],
основанная на архитектуре ccNUMA. Система включает 4GB общей адресуемой
памяти и использует до 24 RISC-процессоров MIPS R10000
В рамках настоящей работы рассматриваются следующие технологические
этапы в разработке сложных вычислительных программ для систем с массовым
параллелизмом:
1. Анализ задачи и выявление ее потенциального параллелизма;
2. Выбор модели программы и схемы распараллеливания;
3. Определение схемы вычислений и программирование задачи;
4. Компиляция, отладка и тестирование;
5. Трассировка и профилирование программы;
6. Проведение вычислительного эксперимента;
7. Анализ результатов.


2. АНАЛИЗ ЗАДАЧИ И ВЫЯВЛЕНИЕ ПОТЕНЦИАЛЬНОГО ПАРАЛЛЕЛИЗМА

Постановка задачи. Рассматривается трехмерная задача, ориентированная на
исследование развития гидродинамических неустойчивостей типа Релей-
Тейлоровских. Рассмотрим систему уравнений гидродинамики. В общем случае мы
можем представить их в следующем виде:
[pic],
где [pic] - некоторая гидродинамическая переменная ([pic], [pic], [pic],
[pic]). Для упрощения изложения мы рассматриваем задачу в двумерной
постановке, в случае трех измерений все последующие выкладки будут
аналогичны.

Метод решения. В качестве численного метода решения данной системы
уравнений мы рассмотрим метод, предложенный T. Yabbe [12], - метод "cubic-
polynomial interpolation". Метод строится на прямоугольной сетке с
постоянным шагом [pic]x и [pic]y по осям x и y соответственно.
Метод является двухэтапным, на первом этапе мы, используя полную
производную по времени, находим значение функции [pic] в некоторой точке
пространства, а на втором шаге интерполируем это значение обратно на сетку.

1. Шаг на лагражевой сетке:
[pic]


[pic]
[pic]



2. Интерполирование обратно на эйлерову сетку

[pic]
[pic]
[pic]
где [pic], [pic].
Значения А1, . , А7 не приводятся для краткости изложения.
Метод достаточно прост в реализации, но из-за наличия в нем
интерполяционной процедуры требуется дополнительные расходы по памяти. Как
видно из вышеприведенных формул, в методе кроме основных гидродинамических
переменных используются еще и их частные производные.


Параллелизм. Для распараллеливания в данной работе предлагается схема,
вытекающая из физического содержания данной задачи. В данной постановке, в
силу того, что все используемые уравнения гиперболического типа, мы имеем
конечную скорость распространения возмущения в исходной среде. Большинство
численных методов решения задач гидродинамики строятся на представлении
исходных уравнений в виде конечных разностей. Расчет точки i,j на (n+1)-м
временном слое происходит с использованием некоторого количества точек на n-
м слое (в большинстве случаев эти точки являются ближайшими соседями точки
i,j ), - схема явная. Численный расчет ведется послойно - по имеющемуся у
нас n-му временному слою мы выстраиваем (n+1)-й, и т.д.

В описанном выше методе мы получаем точку i,j на (n+1)-м временном
слое используя 9 точек с n слоя:











Рис. 1 . Схема расчета на (n+1)-м временном слое

Таким образом, исходную задачу мы можем разбить на несколько
пересекающихся только по границе разбиения областей, независимых друг от
друга на каждом расчетном шаге. Т.е. мы рассчитываем (n+1)-м временной слой
в каждой области, затем согласуем границы и переходим к расчету следующего
слоя.
Однако при таком подходе, когда мы делим расчетную область на
непересекающиеся подобласти, у нас возникают проблемы с пересчетом значений
на границах между данными областями, поэтому мы предлагаем следующий
достаточно логичный шаг, - делить исходную область на взаимно
перекрывающиеся подобласти. В этом случае, мы граничные точки, для
подобласти А будем рассчитывать в подобласти В, и наоборот - граничные
точки для подобласти В будем рассчитывать в подобласти А (Рис.2.). В данной
постановке нам достаточно перекрытия в 2 расчетные точки (Это связано со
спецификой данного численного метода, вообще говоря, достаточно перекрытия
в одну расчетную точку).













Рис.2. Схема перекрытий на границах областей

Рассмотрим в качестве примера исходную задачу размерностью 100х100
расчетных точек. Используя предложенный выше метод, мы делим исходную
область на четыре подобласти размерностью 25х100 (разрезаем по оси х).
Добавляем еще по точки на взаимный пересчет границ и получаем четыре
подобласти размерностью 27х100 каждая:







Рис.3. Пример схемы перекрытия на границах областей



Рис.4. Схема разбиения данных

У нас еще появятся по две «фиктивные» точки слева для области 1 и
справа для области 4. Таким образом, мы получаем четыре независимых на
каждом шаге по времени процесса. Для перехода к следующей итерации
необходимо согласование границ, так как первая область должна передать
второй ее левую границу для следующего шага по времени, в свою очередь
вторая область должна предать первой ее правую границу, и т.д.

Данная методика может быть обобщена на большинство численных методов
основанных на уравнениях гидродинамики. На Рис.4 представлена
соответствующая схема для трехмерной области.
Определим теперь потенциальный параллелизм алгоритма количественно.
Общий объем вычислений Vcalc в алгоритме определяется соотношением
Vcalc =s* k*N 3,
где N 3 - количество расчетных точек в трехмерной области моделирования, k
- количество операций, выполняемых в одной расчетной точке, s - количество
шагов по времени. Для простоты полагаем, что все операции, в том числе и
обмены имеют одинаковое время исполнения равное t. Рассмотрим наихудший
случай, когда все операции в одной точке выполняются последовательно.
Следовательно, на каждом шаге итерации алгоритм требует для своей
реализации k этапов. Тогда средняя степень параллелизма[13] r нашего
алгоритма будет равна

r = s* k*N 3/s*k = N 3 .

Ускорение и масштабируемость. Алгоритм и его программная реализация
являются масштабируемыми, если ускорение и производительность зависят
линейно от количества используемых процессоров[14]:

Sp = O(p),


где Sp - ускорение, p - количество процессоров. На практике алгоритмы, для
которых


Sp = O(p/(ln p))

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


Sp = T1/Tp,


или
где T1 - время вычислений на одном процессоре, Tp, - время вычислений на
p процессорах.
Для получения реалистических оценок будем учитывать время,
затрачиваемое программой на обмены и возможные накладные расходы на
вычисления в перекрывающихся подобластях. Как следует из принятой нами
схемы распределения данных, на каждом шаге итерации требуется обмен
границами. Левые границы пересылаются правым соседям, а правые границы
левым, т.е. объем обменов будет определяться следующим соотношением.
Vcomm = 2smN 2,

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
















Рис. 5. Влияние блокирующих передач на ускорение



Вычисления в областях перекрытия оцениваются следующим образом

Vover = sgN 2 (p-1),

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

To = sgN 2t.

Отметим также, что исходный алгоритм не требует никаких первычислений, а их
присутствие определяется исключительно программной реализацией алгоритма,
так как вариант с перевычислениями потребовал в нашем случае минимальных
переделок исходного кода. Вместе с тем, наличие дополнительных накладных
расходов на вычисления плохо отражается на масштабируемости алгоритмов,
поэтому мы отдельно рассмотрим каждый из этих случаев.
Учтем также то обстоятельство, что в библиотеке MPI имеются две
принципиально разные возможности организации обменов - блокирующие и
неблокирующие функции приема и передачи данных. Рассмотрим оба эти случая
отдельно.
Рассмотрим вначале ускорение при блокирующих передачах. На рисунке 5
изображено влияние блокирующих передач на производительность[15]. На первом
этапе 6-й процесс передает данные 7-му процессу, в то время как процессы с
нулевого по пятый простаивают в ожидании приема данных своими правыми
соседями. На втором этапе пятый процесс передает данные шестому, а
процессы с нулевого по четвертый простаивают. Таким образом, все обмены
завершатся за семь этапов. В общем случае обмены с использованием
блокирующих передач потребуют Tc(p-1) единиц времени, где Tc = 2smN 2t-
время на обмен одной границей , p - количество используемых процессоров.
Ускорение с использованием блокирующих передач будет определяться
следующим соотношением.
[pic]
Учитывая, что в нашем случае Tc = 2smN 2t, To = sgN 2t, , T1 = skN 3 t , r
= N 3, получим окончательно.
[pic]

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












Рис. 6. Попарное чередование посылок и приемов


В общем случае обмены не зависят от количества используемых
процессоров и потребуют 2Tc = Const единиц времени. Тогда ускорение будет
определяться следующим соотношением.
[pic]
Учитывая, что Tc = 2smN 2t, To = sgN 2t, , T1 = s*k*N 3 * t , r = N 3,
получим окончательно
[pic]

Перейдем теперь к рассмотрению случая с использованием неблокирующих
передач. В общем случае обмены с использованием неблокирующих передач не
зависят от количества используемых процессоров и потребуют Tc = Const
единиц времени. Тогда ускорение с использованием неблокирующих передач
будет определяться следующим соотношением.
[pic]
Учитывая, что Tc = 2smN 2t, To = sgN 2t, , T1 = s*k*N 3 * t , r = N 3,
получим окончательно
[pic]
В таблице 1 приведена зависимость ускорений Sp, Sp' и Sp'' от
количества используемых процессоров при значениях параметров,
соответствующих нашему алгоритму и наличии перевычислений в областях
перекрытий. Как видно из этой таблицы алгоритм хорошо масштабируется для
относительно небольшого количества процессоров p ( 64, что вполне подходит
для SMP-систем, но не для систем с массивным параллелизмом, поэтому
перейдем к рассмотрению реализаций без накладных расходов на перевычисления
в областях перекрытий.

Таблица 1: Значения ускорения Sp Sp' Sp'' в зависимости от количества
доступных процессоров p при следующих значениях параметров: N =72; k=500;
m=20; r = 373248, g=100
|P |1 |2 |4 |8 |12 |16 |64 |128 |256 |
| | | | | | | | | | |
|Sp |1,000|1.985|3.822|6.569|7.930|8.276|3.837|1.993|1.004|
|Sp' |1,000|1.980|3.922|7.692|11.32|14.81|48.48|78.04|112.2|
| | | | | |1 |5 |5 |9 |81 |
|Sp'' |1,000|1.985|3.939|7.759|11.46|15.06|51.24|85.46|128.2|
| | | | | |5 |3 |6 |0 |85 |

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

Таблица 2: Значения ускорения Sp Sp' Sp'' в зависимости от количества
доступных процессоров p при следующих значениях параметров: N =72; k=500;
m=20; r = 373248, g=0
|P |1 |2 |4 |8 |12 |16 |64 |128 |256 |
| | | | | | | | | | |
|Sp |1,000|1.996|3.947|7.531|10.46|12.63|11.67|6.715|3.481|
| | | | | |5 |2 |9 | | |
|Sp' |1,000|1.991|3.965|7.860|11.68|15.45|56.03|99.65|163.1|
| | | | | |8 |1 |1 |4 |73 |
|Sp'' |1,000|1.996|3.982|7.930|11.84|15.72|59.75|112.0|199.3|
| | | | | |2 |1 |1 |62 |08 |

Из таблиц видно, что реализация программы основанная на блокирующих
передачах не является масштабируемой и не позволяет эффективно использовать
ресурсы системы при p ( 16.
Реализация, основанная на попарном чередовании посылок и приемов,
позволяет более эффективно использовать вычислительные ресурсы системы.
Данная реализация является масштабируемой вплоть до значений p ( 128.
Как видно из таблицы наиболее эффективной является реализация
основанная на использовании неблокирующих функций обмена сообщениями. Эта
реализация является масштабируемой вплоть до значений p ( 256.
Эти результаты показывают, что алгоритм обладает значительным объемом
потенциального параллелизма и хорошей, с точки зрения распараллеливания
структурой, что позволяет надеяться на ускорения близкие к линейным в
зависимости от количества используемых процессоров, как для SMP-систем,
так и для систем с массивным параллелизмом.


3. ВЫБОР МОДЕЛИ ПРОГРАММЫ И СХЕМЫ РАСПАРАЛЛЕЛИВАНИЯ


MPMD-модель вычислений. MPI-программа представляет собой совокупность
автономных процессов, функционирующих под управлением своих собственных
программ и взаимодействующих посредством стандартного набора библиотечных
процедур для передачи и приема сообщений. Таким образом, в самом общем
случае MPI-программа реализует MPMD-модель программирования (Multiple
Program - Multiple Data)[1,2,14].


SPMD-модель вычислений. На практике, однако, очень часто ограничиваются
SPMD-моделью программирования (Single Program - Multiple Data)[1,2,14]. В
данной модели все процессы исполняют в общем случае различные ветви одной и
той же программы. Такой подход обусловлен тем обстоятельством, что задача
может быть достаточно естественным образом разбита на подзадачи решаемые
одинаковым образом.


|#include |
|#include |
|#include |
|void main( int argc, char *argv[ ]) |
|{ |
|MPI_Init(&argc,&argv); |
|MPI_Comm_size(MPI_COMM_WORLD,&numprocs); |
|MPI_Comm_rank(MPI_COMM_WORLD,&myid); |
| |
|If (myid == 0 ){ |
|/* Работает только корневой процесс */ |
|} |
|/* Все без исключения процессы выполняеют одну и ту же работу */ |
|if (myid == 0) { |
|/* Работает только корневой процесс */ |
|} |
|MPI_Finalize(); |
|} |


Рис. 7. Типичная схема SPMD-программы, написанной на языке Си


В качестве примера могут служить итеративные вычисления на регулярных
сетках из области математической физики и обработки изображений, при
которых одна и та же операция выполняется в каждой точке сетки. Типичный
параллельный алгоритм разбивает всю сетку на подсетки, каждая из которых
обрабатывается одинаковым образом. Обычно программист в этом случае пишет
одну программу, которая размножается в виде совокупности процессов.
Отметим, что с теоретической точки зрения любое множество MPMD-
программ может быть объединено в одну SPMD-программу[14]. С практической же
точки зрения SPMD-подход оказывается более предпочтительным при
распараллеливании последовательных программ, так как не требует
значительной переделки кода. На рисунке 7 представлена схема типичной SPMD-
программы.



4. ОПРЕДЕЛЕНИЕ СХЕМЫ ВЫЧИСЛЕНИЙ И ПРОГРАММИРОВАНИЕ ЗАДАЧИ

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

[pic]

Рис. 8. Схема вычислений


Кроме того, структура обменов также является однородной, за исключением
первого и последнего процессов. В дополнение к этому корневой процесс
выполняет незначительный объем вычислений, обусловленный необходимостью
сборки значений шагов по времени от остальных процессов, вычислением
минимального значения шага с последующей рассылкой этого значения остальным
процессам.
Другим важным аспектом, является выбор уровня распараллеливания. В силу
того, что максимально доступное количество процессоров в системе
относительно невелико и равно 24 процессорам, мы выбираем крупноблочную
схему распараллеливания. Основные этапы вычислений на одном временном шаге
представлены на рисунке 8. В соответствие с ним мы имеем следующую схему на
каждом шаге:
. Вычисление значений шагов по времени для каждого процесса;
. Сборка значений шагов по времени на корневом процессе;
. Вычисление минимального значения шага по времени на корневом процессе;
. Рассылка минимального значения шага всем остальным процессам;
. Локальные вычисления в своей трехмерной подобласти;
. Обмен левыми и правыми границам.
Схема программы соответствует SPMD-модели, представленной на рисунке 7.

5. КОМПИЛЯЦИЯ, ОТЛАДКА И ТЕСТИРОВАНИЕ ПРОГРАММЫ

Компиляция. На этапе компиляции наиболее важным, является вопрос построения
исполняемого кода, оптимизированного для используемого в системе процессора
MIPS R10000. Это достигается использованием опции -F X4, которая в свою
очередь эквивалентна набору следующих опций: -K mips4, -K old, -F O3, -F I,
-F Olimit,3000, -F G32, -F loopunroll,8, -F unrolllimit,2000, -F
hw_br_predict, -B do_jmpopt, -d n. Рассмотрим некоторые, наиболее важные
из этих опций[16]:
-K mips4: Компилятор генерирует инструкции для RISC-процессора MIPS
R10000. Если указана опция -K lp64, то генерируются 64-разрядные
инструкции( по умолчанию порождаются 32-х разрядные инструкции
-F O3: Осуществляется глобальная оптимизация 3-го уровня (устранение
общих подвыражений; оптимизация циклов, например, устранение инвариантов
циклов; устранение "мертвых" кодов; раскрутка циклов; распределение
регистров для процедур оптимизации 3-го уровня).
-F I: Осуществляет макроподстановку для библиотечных функций Си,
устраняя таким образом, накладные расходы на вызовы функций и возвраты из
них.
-F loopunroll,8: Данная опция управляет раскруткой циклов. Значение 8,
указывает оптимизатору максимальный уровень раскрутки. Значение по
умолчанию равно 4. Подавляется опция значением равным 0.
-F hw_br_predict: Данная опция имеет смысл только в комбинации с
опцией -K mips4 и позволяет использовать аппаратную поддержку предсказания
ветвей, реализованную в процессоре R10000.

Запуск программы и привязка процессов к процессорам. MPI-программа не
осуществляет непосредственного порождения параллельных процессов. Процессы
порождаются исполняющей системой при запуске программы. Программа
запускается следующим образом [17]:
mpirun -np 12 yabbe.
Количество порождаемых процессов определяется опцией -np так, например, в
нашем случае порождено 12 процессов yabbe. Порожденные таким образом
процессы должны явным образом узнать свой идентификатор, а также их
количество. На рисунке 9 изображен начальный фрагмент программы,
выполняющей все эти действия.

|#include |
|#include |
|typedef struct mpcreq { |
|cpumask_t mpc_cpu; /* CPU identifier */ |
|pid_t mpc_pid; /* valid process ID */ |
|} mpcreg_t; |
| |
|void main( int argc, char *argv[ ]) |
|{ |
|mpcreg_t numPROC; |
|MPI_Init(&argc,&argv); |
| |
|/* Определяем количество процессов, порожденных исполняющей |
|системой*/ |
| |
|MPI_Comm_size(MPI_COMM_WORLD,&numprocs); |
| |
|/*Определяем собственный идентификатор*/ |
| |
|MPI_Comm_rank(MPI_COMM_WORLD,&myid); |
| |
|/Исключающая привязка процессов к процессорам*/ |
|numPROC.mpc_cpu = CPUNO_TO_LCPUID(myid); |
|numPROC.mpc_pid = getpid(); |
|mpcntl(MPCNTL_BINDXCLU,&numPROC); |
| |
|/* Дальнейшие вычисления */ |
|} |

Рис. 9. Начальный фрагмент программы

Для эффективного использования ресурсов системы необходимо осуществить
отображение процессов на процессоры, т.е. осуществить привязку процессов к
процессорам. Различают два вида привязки: исключающую и неисключающую[17].
Наиболее эффективным вариантом является исключающая привязка. Осуществить
ее можно несколькими способами, например, посредством системной команды
launchit -C4 yabbe,
выполняющую, в данном случае, привязку процесса yabbe к процессору с
номером 4.

Другим способом является привязка посредством системной команды
mpcntl. Привязку можно осуществить и из программы, как это показано на
рисунке 9.

Отладка и тестирование. Отладка и тестирование являются важными
технологическими этапами в разработке программы. В параллельном случае их
роль возрастает еще больше, так как возникают новые классы ошибок (тупики,
некорректные обмены и т.д.) не встречающиеся в последовательном случае.
Особенную сложность представляют программы обрабатывающие очень
большие объемы информации. В настоящее время система не обладает
параллельными версиями отладчиков. Поэтому, в целях отладки использовался
трассировщик MPI (опция - mpitrace) [7], отладочная информация, вставляемая
в текст вручную, а также визуальное представление результатов расчетов, для
ситуаций поддающихся интерпретации, например, проведения расчетов с
известными формами возмущений в областях обрабатываемых ранее на
последовательном компьютере.
В ходе отладки, в частности, были устранены такие ошибки, как тупики
при обменах границами, возникающие вследствие недостаточного буферного
пространства. Рассмотрим эту проблему подробнее. Пусть процессы вначале
посылают данные, а затем принимают их. Рассмотрим ситуацию, когда два
процесса пытаются одновременно осуществить блокирующие посылки друг другу.
В этом случае для завершения операции посылки данные должны покинуть буфер
посылающего процесса. Обычно эти данные помещаются в промежуточный буфер
(детали реализации, которого зависят от системы) до тех пор, пока
принимающий процесс не разместит их в своем буфере. Если размер














Рис. 10. Тупиковый и безопасный варианты блокирующих посылок


сообщения превышает размер буфера, то возникает ситуация тупика.
Первый процесс не может завершить свою операцию посылки до тех пор, пока
второй процесс не выполнит операцию приема, а второй процесс не может
выполнить операцию приема сообщения, потому что он не выполнил еще операцию
посылки и наоборот (Рис. 10а). Вероятность возникновения тупика зависит от
истории вычислений, размера сообщения и порядка передачи сообщений, что
приводит к случайному характеру возникновения тупиков и затрудняет отладку.

Существуют различные методы построения беступиковых программ:
использование неблокирующих операций приема и передачи, явный контроль за
буферизацией и другие методы. Для обеспечения безопасного режима обменов
нами использовался метод, описанный в работе [1], при котором четные
процессы вначале посылают данные, а затем принимают их, в то время как
нечетные процессы реализуют обратный порядок обменов (Рис.10б). Такой
порядок обменов является безопасным, т.е. программа всегда завершается
корректно даже в случае недостаточного буферного пространства. На рисунке
11 представлен соответствующий фрагмент программы.

|Void SendRecv(GLArray F, int Fl{ |
|if ( myid % 2 == 0){ |
|SendBound(F,Fl); |
|RecvBound(F,Fl); |
|} |
|else{ |
|RecvBound(F,Fl); |
|SendBound(F,Fl); |
|} |


Рис.11. Чередование порядка обменов для четных и нечетных процессов



6. ТРАССИРОВКА И ПРОФИЛИРОВАНИЕ ПРОГРАММЫ

Другим важным этапом в технологическом цикле разработки параллельных
программ является трассировка и профилирование. В процессе компиляции
трассировку и профилирование можно задать посредством опций: -mpitrace
и
-mpilog[7]. В первом случае порождается файл trace.log, фрагмент которого
представлен на рисунке 12. Данный файл содержит в символьном виде
информацию о последовательности вызовов MPI-функции в формате:
. [номер процесса] старт функции.
. [номер процесса] завершение функции.

Производительность MPI-программы можно оценить путем анализа файла *.clog,
порождаемого, если на этапе компиляции будет задана опция -mpilog.


|Starting MPI_Init... |
|[1] Ending MPI_Init |
|[1] Starting MPI_Comm_size... |
|[1] Ending MPI_Comm_size |
|... |
|[2] Starting MPI_Send with count = 4200, dest = 3, tag = 2... |
|[3] Ending MPI_Send |
|[3] Starting MPI_Recv with count = 4200, source = 2, tag = 2... |
|[0] Ending MPI_Send |
|[0] Starting MPI_Recv with count = 4200, source = 1, tag = 1... |
|[1] Ending MPI_Send |
|[1] Starting MPI_Recv with count = 4200, source = 2, tag = 1... |
|[2] Ending MPI_Send |
|[2] Starting MPI_Recv with count = 4200, source = 3, tag = 1... |
|[0] Ending MPI_Recv from 1 with tag 1 |
|... |



Рис.12. Фрагмент трассировочного файла trace.log


Для этого используется средство визуального просмотра clog-файлов -
Jumpshot [7, 18]. На рисунке 13 представлено окно программы, содержащее в
визуальном виде трассу исполнения параллельной программы, с графическим
отображением различных функций MPI и их длительностей. Отдельно
отображаются сообщения и их параметры.






Рис.13. Окно программы Jumpshot




7. ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ И АНАЛИЗ РЕЗУЛЬТАТОВ

Ускорение и масштабируемость. Параллельный вариант позволяет осуществлять
моделирование в трехмерной области размером 200*200*250 = 10 млн.
расчетных точек против области размером 50*50*50 = 125 тыс. расчетных точек
в последовательном варианте на рабочей станции DEC Alpha. Таким образом,
использование суперкомпьютерного комплекса позволило увеличить область
моделирования в 80 раз, что превышает почти на два порядка возможности
используемых последовательных рабочих станций. В таблице 3 приведены
реальные значения ускорений, полученные в ходе вычислительного
эксперимента. Эти результаты хорошо согласуются с оценками ускорений,
полученными в разделе 2. Как следует из рассмотрения таблицы 3, ускорение
зависит линейно от количества используемых процессоров, т.е. программа
является масштабируемой.

Таблица 3: Время вычислений (T) и ускорение (S) в зависимости количества
используемых процессоров
|Параметры |Количество процессоров |
| |1 |2 |4 |8 |12 |
|Область |72*72*72 |72*72*72 |72*72*72 |72*72*72 |72*72*72 |
|Кол-во |3942 |3942 |3942 |3942 |3942 |
|шагов | | | | | |
|Время, T |148819.450|79414.190 |40581.030 |21154.290 |14453.360 |
|[с] | | | | | |
|Ускорение,|1.000 |1.874 |3.667 |7.035 |10.297 |
|S | | | | | |



8. ЗАКЛЮЧЕНИЕ

В работе на примере задачи численного моделирования на супер-ЭВМ
сложных трехмерных течений, возникающих при развитии гидродинамических
Релей-Тейлоровских неустойчивостей, рассматриваются технологические аспекты
разработки масштабируемых параллельных вычислений для SMP-систем с
использованием библиотеки MPI. В рамках настоящей работы рассмотрены
основные технологические этапы в разработке сложных вычислительных программ
для систем с массовым параллелизмом: анализ задачи и выявление ее
потенциального параллелизма; выбор модели программы и схемы
распараллеливания; определение схемы вычислений и программирование задачи;
компиляция, отладка и тестирование; трассировка и профилирование программы;
проведение вычислительного эксперимента; анализ результатов.
Получены расчетные значения ускорений, позволяющие оценить
масштабируемость алгоритма и его программной реализации. Эти результаты
показывают, что алгоритм обладает значительным объемом потенциального
параллелизма и хорошей, с точки зрения распараллеливания структурой, что
позволяет надеяться на получение ускорений близких к линейным в зависимости
от количества используемых процессоров, как для SMP-систем, так и для
систем с массивным параллелизмом.
Приведены значения ускорений, полученные в ходе вычислительного
эксперимента, которые хорошо согласуются с теоретическими оценками.

Работа выполнена при поддержке Российского Фонда Фундаментальных
Исследований, грант 99-07-90370.


СПИСОК ЛИТЕРАТУРЫ



1. Snir M., Otto S. W., Huss-Lederman S., Walker D., and Dongarra J.. MPI:
The Complete Reference. MIT Press. Boston, 1996.
2. Dongarra J., Otto S. W., Snir M., and Walker D., An Introduction to the
MPI Standard. Technical report CS-95-274. University of Tennessee,
January 1995.
3. Foster I. Designing and Building Parallel Programs. Addison-Wesley, 95.
4. Бебб Р., Мак-Гроу Дж., Акселрод Т. и др. Программирование на
параллельных вычислительных системах: Пер. с англ. под ред. Р. Бебба II.
- М.:Мир, 1991.
5. MPI Forum "MPI: A Message-Passing Interface MPI Forum" ,Technical report
CS/E 94-013. Department of Computer Science. Oregon Graduate Institute.
March 1994.
6. Message Passing Interface Forum. MPI: A message-passing interface
standard // International Journal of Supercomputer Applications,
8(3/4),1994. pp.157-416
7. Gropp W. and Lusk E. User's Guide for mpich, a Portable Implementation
of MPI. Technical Report ANL-96/6. Aragone National Laboratory.1996.
8. Воеводин Вл.В. Архитектура векторно-конвейерных супер-ЭВМ CRAY C90. Курс
лекций "Параллельная обработка данных" // Лаборатория Параллельных
Информационных Технологий НИВЦ МГУ. 1998
http://parallel.srcc.msu.su/vvv/lec2.html
9. Воеводин Вл.В, Параллельные компьютеры с распределенной памятью //
ComputerWorld. ? 22. 1999 г.
10. Agervala T., Martin J.L., Mirza J.H. and others. SP2 Systems
Architectures // IBM Systems Journal, Vol. 34. N2. 1995.
11. Architecture HP 9000 V-Class Server, Second Edition, March 1998.
http://docs.hp.com/dynaweb/hpux11/hwdgen1a/varcen1/@Generic_BookView
12. Yabbe T., Ishikawa T., Wang P.Y. A Universal Solver for Hyperbolic
Equations by Cubic-Polinomial Interpolation II. Two- and Tree-Dimensional
Solvers // Computer Physics Communications. ? 66.1991. P. 233-242.
13. Ортега Дж. Введение в параллельные и векторные методы решения линейных
систем: Пер. с англ.-М.:Мир, 1991.

McBryan O. A. An overwiev of message passing environments // Parallel
Computing. 1994. V 20. P. 417-441.

14. Balay S., Gropp W.D., McInnes L.C., and Smith B.F. Efficient Management
of Parallelism in Object-Oriented Numerical Software Libraries, Modern
Software Tools in Scientific Computing, E. Arge, A. M. Bruaset and H. P.
Langtangen, Ed., Birkhauser Press, 1997. pp. 163-202.
15. C/C++ Compiler V 1.0 (Reliant Unix). User Guide. Siemens Nixdorf.
April 1997.
16. Reliant UNIX 5.43 (RM200, RM400, RM600) Commands. Users Reference
Manual. Vol. 1,2. 1997.
17. Browne S., Dongarra J., London K. Review of Performance Analysis Tools
for MPI Parallel Programs, http://www.cs.utk.edu/~browne/perftools-
review/
-----------------------
n - слой по времени

n + 1 - слой по времени

i,j

i+1,j

i-1,j

i-1,j-1

i,j-1

i+1,j-1

i-1,j+1

i,j+1

i+1,j+1

А

В

1

2

3

4

Время



send

send

граница для области B,

внутренняя точка для области A

send

send

send

send

send

recv


recv

recv

recv

recv

recv

recv

[pic]



P











Время



MPI_Send

MPI_Recv

MPI_Send

MPI_Recv

MPI_Send

MPI_Recv

MPI_Recv

MPI_Send

P0

P0

P1

P1

а) Тупиковый вариант

б) Безопасный вариант


send

P6

recv

send

recv

send

recv

send

recv


recv

P7

send

recv

send

recv

send

recv

send

P

P1

P5

P2

P0

P3

P4

P7

P4

P3

P0

P2

P5

P6

P1

граница для области A,

внутренняя точка для области B