Декомпозиция последовательных программ при параллельных вычислениях.

Е.С.Борисов

вторник, 10 июня 2003 г

1 Введение

Для параллельных вычислительных систем необходимо создавать специальные программы. В тексте такой программы определяются части (ветки), которые могут выполнятся параллельно, а также алгоритм их взаимодействия. Можно выделить два основных подхода к построению параллельных программ [1] :

распараллеливание по управлению. Вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей. (соответствует архитектуре MIMD)
распараллеливание по данным. Весь исходный массив данных разбивается на подмножества и фрагменты распределяются между процессорами системы Одни и те же операции выполняются одновременно над несколькими элементами массива данных. (соответствует архитектуре SIMD)

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

Автоматические системы распараллеливания [5] выполняют декомпозицию последовательного алгоритма самостоятельно. На вход подается последовательная программа, на выход выдается её параллельный аналог. Пример такой системы это BERT77 средство автоматического распараллеливания Fortran-программ [6].

В случае полуавтоматической системы распараллеливания, в тексте последовательной программы выделяются блоки, которые могут выполнятся параллельно. Обычно, в текст вставляются специального вида комментарии, которые игнорируются обычным (последовательным) компилятором. Примером такой полуавтоматической системы может служить Adaptor - одна из реализаций спецификации HPF (High Performance Fortran)[4].

В данной статье предлагается полуавтоматическая система распараллеливания программ на C++ для популярной коммуникационной библиотеки MPICH.

2 Полуавтоматическая система декомпозиции

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

Определим метки препроцессора:

$INIT$ - инициализация MPI
$FIN$ - завершение работы MPI
$ROOT$ и $ENDROOT$ - код между этими метками выполняется только одним (нулевым) процессом
$SUM$ DECOMP(i=m,n) REDUCE(sum) REDUCETYPE(type) и $ENDSUM$ - распараллеливание подсчета суммы $sum=\sum\limits_{i=m}^n f(i)$ , где f(i) - алгоритм подсчета, описанный между $SUM$ и $ENDSUM$

Препроцессор [ здесь ]

3 Пример

Рассмотрим классический пример параллельного программирования - вычисление $\pi$ . Число $\pi$ будем вычислять как определенный интеграл :

$\begin{displaymath}\int\limits_{0}^{1}{\frac{4}{1+x^2}}dx = \left. 4\cdot \arctg(x)\right\vert _0^1 = \pi\end{displaymath}$

Согласно правилу прямоугольников интеграл можно заменить суммой:

$\begin{displaymath}\pi \approx h \cdot \sum\limits_{i=1}^{n}\left(\frac{4}{1+x_i... ...h = \frac{1}{n}\ ;\ x_i = \left( i - \frac{1}{2}\right)\cdot h\end{displaymath}$

Последовательная программа с комментариями [ здесь ]
Параллельная программа ( результат препроцессирования ) [ здесь ]

3.1 Результаты счета

Последовательная программа
Количество итераций 10⁹
Время счета - 108 секунд
```
   [ mpibin ]$ ./pi 
   pi = 3.1415926535899708
```
Параллельная программа на двух процессорах
Количество итераций 10⁹
Время счета - 57 секунд
```
   [ mpibin ]$ mpirun -machinefile machines -np 2 pi
   Process 0 on node2.home.net
   Process 1 on node1.home.net
   pi = 3.1415926535899708
```

Литература

1: А.Е.Дорошенко "Математические модели и методы организации высокопроизводительных параллельных вычислений" -- Киев, "Наукова думка", 2000
2: Коммуникационные библиотеки - http://www.parallel.ru/tech/tech_dev/ifaces.html
3: MPI - http://www.mpi-forum.org
4: HPF - http://www.crpc.rice.edu/HPFF/
5: Средства распознавания параллелизма в алгоритмах - http://www.parallel.ru/tech/tech_dev/auto_par.html
6: BERT77 - http://www.plogic.com/bert.html

Evgeny S. Borisov
2003-06-10

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