на главную ] 

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

Е.С.Борисов

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

1 Введение

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

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

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

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

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

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

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

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


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

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 Результаты счета

Литература


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
Яндекс.Метрика
TOP.zp.ua PR-CY.ru
При использовании материалов этого сайта, пожалуйста вставляйте в свой текст ссылку на мою статью.