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

Е.С.Борисов

четверг, 9 сентября 2004 г.

1 Введение
2 Средства параллельных вычислений
3 Математические модели
4 Постановка задачи и ее решение
5 Реализация
Литература

1 Введение

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

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

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

Основным параметром оценки работы параллельной системы является коэффициент ускорения [4] :

$\displaystyle s(p)=\frac{T(1)}{T(p)}$

(1)

где

- время выполнения программы на

процессорах.

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

Оценить максимально возможное ускорение для данной программы можно, используя закон Амдала[3] :

$\displaystyle s(p)\leq\frac{1}{f+\frac{1-f}{p}}$

(2)

где $0\leq f\leq 1$ - доля последовательных операций в параллельной программе,

- количество процессоров.

2 Средства параллельных вычислений

Приведем краткое описание технологий параллельных вычислений. Средства параллельных вычислений можно разделить на три уровня :

**Рисунок 1:** Средства параллельных вычислений
$\begin{figure}\centering \begin{tabular}{\vert c \vert} \hline {\bf уровень 2}\\... ...\ аппаратура\\ (SMP, MPP, Кластеры, \ldots)\\ \hline \end{tabular} \end{figure}$

2.1 Аппаратные средства для параллельных вычислений

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

SMP - симметричная мультипроцессорная система. SMP обычно состоит из нескольких одинаковых процессоров и массива общей памяти. Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Наличие общей памяти упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число (обычно не более 32).
PVP - параллельная векторная система. Основным признаком PVP-систем является наличие специальных векторно-конвейерных процессоров. Как правило, несколько таких процессоров работают одновременно над общей памятью (аналогично SMP) в рамках многопроцессорных конфигураций.
MPP - система массового параллелизма. MPP состоит из нескольких однородных вычислительных узлов. Каждый такой узел имеет свою локальную память (прямой доступ к памяти других узлов невозможен), один или несколько центральных процессоров( иногда - жесткий диск). Узлы обычно связаны специальной высокоскоростной сетью. Общее число процессоров в таких системах может достигать нескольких тысяч.
NUMA - система с неоднородным доступом к памяти. NUMA представляет собой нечто среднее между SMP и MPP. В NUMA память физически распределена, но логически общедоступна. Масштабируемость NUMA-систем ограничивается объемом адресного пространства и возможностями операционной системы.
Кластеры - недорогой вариант MPP. Обычно это сеть из персональных компьютеров или рабочих станций общего назначения, которая объединяется в ''виртуальную многопроцессорную машину''. Для связи узлов используется одна из стандартных сетевых технологий (Ethernet, Myrinet).

2.2 Коммуникационные библиотеки

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

Соответственно типу организации памяти, существует два основных типа коммуникационных библиотек [5] и интерфейсов параллельного программирования :

Библиотеки использующие модель общей памяти - этот класс библиотек обычно применяют для SMP систем
Библиотеки построенные по модели обмена сообщениями удобно использовать для систем с распределенной памятью - массово-параллельные (MPP) и кластерные системы

Надо отметить, что одно может быть сымитировано через другое :

модель обмена сообщениями для SMP - вырожденным каналом связи передачи сообщений служит разделяемая память.
модель общей памяти для MPP - организация единого виртуального адресного пространства ( аппаратно реализовано на NUMA-машинах)

Существует множество библиотек и интерфейсов параллельного программирования. Отметим наиболее популярные из них.

OpenMP(http://www.openmp.org) - программный интерфейс для программирования компьютеров с общей памятью, т.е. для вычислителей принадлежащих к классу симметричных мультипроцессоров (SMP) и к классу систем с неоднородным доступом к памяти (NUMA).
PVM : parallel virtual machine (http://www.epm.ornl.gov/pvm) Эта система ориентирована на работу с гетерогенными кластерами, поддерживает языки программирования C/C++/fortran, работает на широком классе систем, включая рабочие станции, суперкомпьютеры и сети персональных компьютеров. PVM реализует модели обмена сообщениями и динамического распараллеливания, т.е. существует возможность порождать новые ветви параллельной программы в процессе ее выполнения.
MPI : Message Passing Interface (http://www.mpi-forum.org) - стандарт для построения параллельных программ по модели обмена сообщениями. Существуют реализации почти для всех суперкомпьютерных платформ, а также для сетей рабочих станций UNIX и Windows NT. Это наиболее популярный и широко используемый стандарт.

2.3 Средства автоматического распараллеливания

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

В случае полуавтоматической системы распараллеливания, в тексте последовательной программы выделяются блоки, которые могут выполнятся параллельно. Обычно, в текст вставляются специального вида комментарии, которые игнорируются обычным (последовательным) компилятором. Примером такой полуавтоматической системы может служить Adaptor - одна из реализаций спецификации HPF : High Performance Fortran (http://www.crpc.rice.edu/HPFF).
Автоматические системы распараллеливания[6] выполняют декомпозицию последовательного алгоритма самостоятельно. На вход подается последовательная программа, на выход выдается её параллельный аналог. Пример такой системы: BERT77 - средство автоматического распараллеливания Fortran-программ
(http://www.plogic.com/bert.html). Системы из этого класса так же могут помочь пользователю выяснить, можно ли распараллелить данную задачу, оценить время ее выполнения, определить оптимальное число процессоров.

3 Математические модели

Рассмотрим три модели для описания параллельных вычислений. В этой работе применяется алгебродинамический подход к построению математических моделей параллельных вычислений[4]. Этот подход основывается на алгебре алгоритмов Глушкова[7]. Для описания функционирования моделей будем использовать понятия теории дискретных динамических систем[7].

Дискретная динамическая система (ДДС, transition systems) представляет собой тройку :

$\displaystyle (S,S_0,\delta)$

где

- множество состояний
$S_0\subseteq S$ - множество начальных состояний
$\delta:S\rightarrow S$ - отношения переходов

Алгебра алгоритмов Глушкова [7] определяется следующим образом. Введем три множества :

- множество переменных (память)
- множество значений переменных (данные)
$B=\{b:V\rightarrow D\}$ - множество частичных отображений, его можно рассматривать как состояния памяти или информационную среду

Алгеброй алгоритмов назовем пару :

$\displaystyle A(Y,U)$

(3)

где

- алгебра операторов
- $y:B\rightarrow B$ - множество частичных преобразований информационной среды
- $\varepsilon$ - тождественный оператор
- $\phi$ - пустой оператор
- алгебра условий
- 0 - тождественно ложное условие
- - тождественно истинное условие
- $u:B\rightarrow \{0,1\}$ - множество частичных предикатов на

В алгебре алгоритмов (3) определены следующие операции :

последовательная композиция операторов :
где $P,Q\in Y$ - операторы, $b\in B$ - состояние памяти
условный переход : $u\rightarrow(P,Q)= \left\{\begin{aligned} P(b)\ :\ & u(b)=1\\ Q(b)\ :\ & u(b)=0 \end{aligned}\right.$
где $P,Q\in Y$ - операторы, $b\in B$ - состояние памяти, $u\in U$ - условие
итерация : $u\{P\}$
если $\exists\ n>0\ :\ \forall k\in\{1\ldots n-1\}\ u(P^k(b))=0\ , u(P^n(b))=1$
то $u\{P\}=P^n(b)$
иначе $u\{P\}$ не определено
где $P\in Y$ - оператор, $b\in B$ - состояние памяти, $u\in U$ - условие
умножение оператора на условие :
где $P\in Y$ - оператор, $b\in B$ - состояние памяти, $u\in U$ - условие

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

Регулярное выражение в назовём регулярной программой.

Модели памяти

Для множества регулярных программ $P=\{P_i\}$ модель распределённой памяти строится следующим образом :

: Множество переменных регулярной программы назовём множеством внутренних переменных или внутренней памятью программы если $I_i\cap I_j = \oslash$ для $i\neq j$
тогда множество $I=\bigcup\limits_i I_i$ назовём распределённой памятью
: Все множество переменных регулярной программы $P_i\in P$ назовём двухуровневой памятью
если $V=I\cup E$ ; $(\ I\cap E=\oslash\ )$ и определены операторы внешнего обмена - чтение $x:\leftarrow e$ и запись $x:\rightarrow e$ ( $x\in I ; e\in E$ )
В этом случае, назовём внешней памятью $P_i\in P$

В общем случае будем считать, что $\forall P_i \in P$ внутренняя память - распределена, внешняя память является общей.

4 Постановка задачи и ее решение

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

4.1 Модель полуавтоматической системы распараллеливания

Система полуавтоматического распараллеливания описывается тремя алгебродинамическими моделями :

- модель исходной последовательной программы, состоящей из определенного множества подпрограмм.
- модель параллельной программы. Данная модель построена на основе парадигмы обмена сообщениями, и описывает статическое распараллеливание, т.е. количество компонент параллельной программы фиксировано. ориентирована на системы с распределенной памятью, без общей внешней памяти (например - кластер на основе сети персональных компьютеров).
$\Delta : S \to P$ - модель транслятора-распараллеливателя на основе дискретной динамической системы,

**Рисунок 2:** Схема асинхронного вызова подпрограммы
$\includegraphics[width=10cm]{images/call.ps}$

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

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

4.2 Модель последовательной программы

Определим последовательную многокомпонентную программу как упорядоченное множество пар . Каждая такая пара определяет подпрограмму в :

$\displaystyle S=\{(s_0,S_0),\ldots,(s_n,S_n)\}$

(4)

где

- i-тая подпрограмма

$\{S_i\ \vert\ i=0\ldots n \}$ - множество регулярных программ с распределенной памятью
- уникальное имя подпрограммы ( $s_i\neq s_j$ для $i\neq j$ )

Введем операторы вызова подпрограммы и возврата из подпрограммы .

Оператор вызова подпрограммы обозначим

где
- - имя, вызываемой программы
- $(x_0\ldots x_s)$ - входные параметры
- $(y_0\ldots y_q)$ - результаты
Оператор возврата из подпрограммы обозначим $\downarrow(y_0\ldots y_q)$ где $(y_0\ldots y_q)$ - результаты

Процесс выполнения последовательной многокомпонентной программы описывается дискретной динамической системой $\Omega$ :

$\displaystyle \Omega=(S,\Sigma,\sigma_0,\Sigma_E,\delta)$

Здесь

- последовательная многокомпонентная программа (4)
- множество состояний
состояние определим так :

где
- - состояние памяти
- - состояние управления (остаточная программа)
- $\tau$ - список вызовов подпрограмм $(\tau\subset \Sigma)$
$\sigma_0=[\ \oslash,S_0,\oslash\ ]$ - начальное состояние
$\Sigma_E=\{\ [\ b,\downarrow(y_0\ldots y_q),\oslash\ ]\ \}$ - множество заключительных состояний
Отношение переходов задается следующим образом:
1. выполнение элементарного оператора :
  $[\ b,yR,\tau\ ] \Rightarrow [\ y(b),R,\tau\ ]$
2. условный переход :
  $[\ b,(u\rightarrow(R,Q))T,\tau\ ] \Rightarrow \left\{\begin{aligned} \lbrack\ ... ... :\ & u(b)=1\\ \lbrack\ b,QT,\tau\ \rbrack\ :\ & u(b)=0 \end{aligned}\right.$
3. итерация :
  $[\ b,u\{R\}Q,\tau\ ]\Rightarrow \left\{\begin{aligned} \lbrack\ b,Q,\tau\ \rbr... ...b)=0\\ \lbrack\ b,R\ u\{R\}Q,\tau\ \rbrack\ :\ & u(b)=1 \end{aligned}\right.$
4. вызов программы :
  $[\ b_i,f_jR_i,\tau\ ] \Rightarrow [\ b_j, S_j, [\ b_i ,f_jR_i,\tau\ ] * \tau\ ]$
  где
  $f_j=(y_0\ldots y_q)\leftarrow s_j(x_0\ldots x_s)$ - вызов программы
  - компонентная программа с именем
  $b_j(r)=\left\{ \begin{aligned} b_i(x_0)\ :\ & r = x^j_0\\ \cdots\\ b_i(x_s)\... ...x^j_s\\ \oslash \ :\ & r \notin \{x^j_0, \ldots, x^j_s\} \end{aligned}\right.$
  где $x^j_0, \ldots, x^j_s$ - внутренние переменные , соответствующие входам
5. возврат из подпрограммы :
  $[\ b_j,\downarrow(y^j_0\ldots y^j_q),[\ b_i,f_jR_i,\tau\ ]*\tau\ ] \Rightarrow [\ b_i', R_i, \tau\ ]$
  где
  $f_j=(y_0\ldots y_q)\leftarrow s_j(x_0\ldots x_s)$ - вызов программы
  $b_i'(r)=\left\{\begin{aligned} b_j(y^j_0)\ :\ & r = y_0\\ \cdots\\ b_j(y^j_q)\ :\ & r = y_q\\ b_i(r)\ :\ & r \notin \{y_0, \ldots, y_q\} \end{aligned}\right.$

4.3 Модель параллельной программы

Введем понятие параллельной программы и определим его как упорядоченое множество пар . Каждая такая пара определяет параллельный процесс :

$\displaystyle P=\{(p_0,P_0),\ldots,(p_n,P_n)\}$

(5)

где

- уникальное имя компоненты ( $p_i\neq p_j$ для $i\neq j$ )
- регулярная программа в алгебре алгоритмов (3), расширенная операторами обмена данными,
причем множество $\{P_i\ \vert\ i=0\ldots n \}$ является множеством регулярных программ с распределенной памятью

Определим два типа операторов обмена данными между компонентами параллельной программы :

синхронные операторы обмена - обе компоненты и дожидаются завершения транзакции :
- $x_i\rightarrow p_j$ - синхронная посылка данных из внутренней переменной компоненты в компоненту
- $x_i\leftarrow p_j$ - синхронный прием данных из компоненты во внутреннюю переменную компоненты
асинхронные операторы обмена - после вызова оператора, управление немедленно возвращается, а данные попадают в очередь на обработку:
- $x_i\leadsto p_j$ - асинхронная посылка данных из внутренней переменной компоненты в компоненту

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

Процесс выполнения последовательной многокомпонентной программы описывается дискретной динамической системой $\Pi$ :

$\displaystyle \Pi=(P,\Sigma,\sigma_0,\Sigma_E,\delta)$

Здесь

- параллельная программа (5)
- множество состояний
состояние определим так :
$\displaystyle \sigma = [\ (p_0,b_0,R_0),\ldots,(p_n,b_n,R_n),\tau\ ]$
где
- - имя компоненты параллельной программы
- - состояние памяти компоненты
- - состояние управления компонентой
  (остаточная программа при выполнении )
- $\tau=\{\tau_{ij}\}$ - матрица $n\times n$ ( - количество компонент в ), где $\tau_{ij}$ - очередь значений переменных из внутренней памяти компоненты на передачу в компоненту ; $\tau_{ii}=\oslash$
$\sigma_0$ - начальное состояние $\Pi$ : $[\ (p_0, \oslash,P_0),\ldots,(p_n, \oslash,P_n) , \oslash\ ]$
$\Sigma_E$ - заключительные состояния $\Pi$ : $\{\ [\ (p_0, b_0,\oslash),\ldots,(p_n,b_n,\oslash) , \oslash\ ]\ \}$
- отношения переходов
( фиксируются только используемые части вектора состояния)
1. выполнение элементарного оператора : $\lbrack\ b,yR\ \rbrack \Rightarrow \lbrack\ y(b),R\ \rbrack$
2. условный переход : $\lbrack\ b,(u\rightarrow(R,Q))T\ \rbrack \Rightarrow \left\{\begin{aligned} \l... ...rack\ :\ & u(b)=1\\ \lbrack\ b,QT\ \rbrack\ :\ & u(b)=0 \end{aligned}\right.$
3. итерация :
  $\lbrack\ b,u\{R\}Q\ \rbrack\Rightarrow \left\{\begin{aligned} \lbrack\ b,Q\ \r... ... & u(b)=0\\ \lbrack\ b,R\ u\{R\}Q\ \rbrack\ :\ & u(b)=1 \end{aligned}\right.$
4. синхронный обмен данными $p_i\rightarrow p_j$ :
  $\lbrack\ (p_i,b_i,(x_i\rightarrow p_j)R_i),(p_j,b_j,(x_j\leftarrow p_i)R_j)\ \rbrack \Rightarrow \lbrack\ (p_i,b_i,R_i),(p_j,b'_j,R_j)\ \rbrack$
  где
  $b'_j(r)=\left\{\begin{aligned} b_i(x_i)\ :\ & r=x_j\\ b_j(r)\ :\ & r\neq x_j \end{aligned}\right.$
5. асинхронная посылка данных $p_i\leadsto p_j$ :
  $\lbrack\ (p_i,b_i,(x_i\leadsto p_j)R_i),\tau_{ij}\ \rbrack \Rightarrow \lbrack\ (p_i,b_i,R_i),\tau_{ij}*b_i(x_i)\ \rbrack$
6. доставка данных из очереди $\tau_{ij}$ :
  $\lbrack\ (p_j,b_j,(x_j\leftarrow p_i)R_j),d*\tau_{ij}\ \rbrack \Rightarrow \lbrack\ (p_j,b'_j,R_j)\ \rbrack$
  где
  $b'_j(r)=\left\{\begin{aligned} d \ :\ & r=x_j\\ b_j(r)\ :\ & r\neq x_j \end{aligned}\right.$

4.4 Транслятор-распараллеливатель $\Delta$

Полуавтоматическая система распараллеливания последовательных программ описывается следующей дискретной динамической системой :

$\displaystyle \Delta=(S,\Sigma,\sigma_0,\sigma_E,\delta)$

Здесь

- последовательная многокомпонентная программа (4)
- множество состояний
состояние определяется так :
$\displaystyle \sigma=[R,\tau,\mu,\pi,P]$
где
- - остаточная программа от
- - параллельная программа (5)
- $\tau$ - очередь состояний вызовов последовательной программы , элементами этой очереди есть остаточные программы
- $\mu=\{\mu_p\}$ - множество неготовых переменных при выполнении параллельной программы ,
  где $\mu_p=\{\ [(y_0\ldots y_q),p']\ \}$ - множество неготовых внутренних переменных компоненты , где - компонента-поставщик значений для переменных $(y_0,\ldots,y_q)$
- $\pi$ - очередь имён параллельных компонент программы
$\sigma_0=[S,\oslash,\oslash,p_0,(p_0,\oslash)]$ - начальное состояние
$\sigma_E=[\oslash,\oslash,\oslash,p_0,P]$ - заключительное состояние
Отношения переходов задаются следующим образом:
введём обозначения :
$(x_0\ldots x_q)\leftarrow p = (x_0\leftarrow p)\ldots(x_q\leftarrow p)$
$(x_0\ldots x_q)\rightarrow p = (x_0\rightarrow p)\ldots(x_q\rightarrow p)$
$(x_0\ldots x_q)\leadsto p = (x_0\leadsto p)\ldots(x_q\leadsto p)$
1. трансляция оператора , не являющийся оператором вызова или возврата :
  $\displaystyle [\ yR,\tau, \mu, (p*\pi), (p,Q)\ ] \Rightarrow [\ R,\tau, \mu, (p*\pi), (p,Qy)\ ]$
2. трансляция оператора вызова программы
  :
  
  $\displaystyle [\ f_jR_i,\tau,\mu_p, (p*\pi), (p,Q)\ ] \Rightarrow [\ S_j,(R_i*\tau), \mu_p', (p'*p*\pi), P\ ]$
  где
  - $P=(p,Q(x_0\ldots x_s)\leadsto p')\cup(p',(x'_0\ldots x'_s)\leftarrow p)$ - создаём новую параллельную компоненту , посылаем параметры $(x_0\ldots x_s)$ из в , принимаем параметры в во внутренние переменные $(x'_0\ldots x'_s)$
  - $\mu'_p=(y_0\ldots y_q,p')\cup\mu_p$ - добавляем в очередь неготовых переменных $\mu_p$ выход $(y_0\ldots y_q)$ , вызванной программы
3. трансляция оператора возврата из подпрограммы последовательной программы $\downarrow(y_0\ldots y_q)$ :
  $\displaystyle [\ \downarrow(y_0\ldots y_q) ,R_i*\tau, \mu, (p'*p*\pi), (p',Q')\ ] \Rightarrow [\ R_i,\tau,\mu,(p*\pi), P\ ]$
  где $P=(p',Q'((y_0\ldots y_q)\to p))$
4. обработка неготовой входной переменной :
  пусть оператор из компоненты и
  если $\exists p' : (x_0\ldots x_q,p')\in \mu_p$ и $x_i\in\{x_0\ldots x_q\}$ то
  $\displaystyle [\ R,\tau,\mu'_p,\pi, (p,QyT)\ ]\Rightarrow [\ R,\tau,\mu_p,\pi, (p,Q((x_0\ldots x_q)\leftarrow p')yT)\ ]$
  где $\mu'_p=\mu_p\cup(x_0\ldots x_q,p')$

5 Реализация

Опишем реализацию транслятора-распараллеливателя для языка C.

5.1 Построение кластера

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

Можно использовать уже существующую сеть рабочих станций (системы такого типа иногда называют COW - Cluster Of Workstations). При этом узлы могут иметь различную архитектуру, производительность, работать под управлением разных OC (MS Windows, Linux, FreeBSD).

Если узлы планируется использовать только в составе кластера, то их можно существенно облегчить (отказаться от жёстких дисков, видеокарт, мониторов и т.п.). В облегчённом варианте узлы будут загружаться и управляться через сеть. Количество узлов и требуемая пропускная способность сети определяется задачами, которые планируется запускать на кластере.

5.2 Стандарт MPI

Message Passing Interface (MPI) - популярный стандарт для построения параллельных программ по модели обмена сообщениями. Этот стандарт обычно используют в параллельных системах с распределённой памятью (кластера и т.п.).

MPI содержит в себе разнообразные функции обмена данными, функции синхронизации параллельных процессов, механизм запуска и завершения параллельной программы. Стандарт MPI-1 описывает статическое распараллеливание, т.е. количество параллельных процессов фиксировано, это ограничение устранено в новом стандарте MPI-2, позволяющем порождать процессы динамически. MPI-2 в настоящее время находится в стадии разработки.

Разными коллективами разработчиков написано несколько программных пакетов, удовлетворяющих спецификации MPI (MPICH, LAM, HPVM etc.). Существуют стандартные ''привязки'' MPI к языкам С, С++, Fortran 77/90, а также реализации почти для всех суперкомпьютерных платформ и сетей рабочих станций.

5.3 Работа с MPI на кластере

В данной работе для прогона контрольных примеров был использован кластер на основе сети персональных компьютеров и библиотека MPICH (http://www-unix.mcs.anl.gov/mpi/mpich), созданная авторами спецификации MPI. Этот пакет можно получить и использовать бесплатно. В состав MPICH входит библиотека программирования, загрузчик приложений, утилиты. Существуют реализации этой коммуникационной библиотеки для многих UNIX-платформ, MS Windows.

Для запуска MPI-программ на гомогенном (состоящего из одинаковых узлов, работающих под одной OS) кластере необходимо выполнить следующие шаги.

Инсталлировать MPICH на головной узел (машина, с которой будем запускать MPI-программы) кластера. Инсталлировать MPICH на все узлы кластера обычно не требуется.
MPICH использует rsh (remote shell) для запуска процессов на узлах кластера. Поэтому необходимо запустить на каждом узле rshd (remote shell server) и согласовать права доступа.
Для обеспечения более высокого уровня сетевой безопасности можно использовать ssh - OpenSSH remote login client.
Компиляция MPI-программы на языке С выполняется утилитой mpicc, представляющей собой надстройку над C-компилятором, установленным в данной OS.
mpicc myprog.c -o myprog
Перед запуском ''бинарника'' myprog необходимо разослать его на все узлы кластера, причем локальный путь до myprog должен быть одинаковый на всех машинах, например - /usr/mpibin/myprog.
Вместо процедуры копирования программы на узлы можно использовать NFS (Network File System) :
- на головной машине запускаем NFS-сервер и открываем каталог с myprog
- на каждом рабочем узле кластера, монтируем NFS головной машины, используя единый для всех узлов локальный путь.
Запуск MPI-программы производится командой :
mpirun -machinefile machines -np n myprog
- machines - файл, содержащий список узлов кластера
- n - количество параллельных процессов

После команды mpirun, MPICH, используя rsh, запускает n-раз программу myprog на машинах из machines. При запуске каждому процессу присваивается уникальный номер, и далее программа работает исходя из этого номера.

5.4 Реализация системы полуавтоматического распараллеливания

Используя MPI, можно писать эффективные параллельные программы, но непосредственное программирование в MPI имеет ряд недостатков. MPI можно назвать ассемблером виртуальной многопроцессорной машины. Написание MPI-программ требует от программиста специальной подготовки. Кроме того, MPI-программы, как средство низкого уровня, являются, в значительной мере, архитектурно зависимыми, что затрудняет их переносимость. Описанная система полуавтоматического распараллеливания $\Delta$ позволяет решить эти проблемы.

Реализация $\Delta$ транслирует программу на расширенном языке C в параллельную MPI-программу на C.

**Рисунок 3:** схема работы транслятора $\Delta$
$\begin{figure}\centering {\tt С$\Delta$-программа $\stackrel{\Delta}{\longrighta... ...ограмма $\stackrel{mpicc}{\longrightarrow}$ исполняемая программа}\end{figure}$

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

Пользователю необходимо разбить свою последовательную программу на части, которые могут выполнятся независимо друг от друга. Эти части записываются в виде пользовательских функций, в заголовки которых добавляется ключевое слово asyncron.
```
asyncron int my_big_func() {
   /* just do it :) */ 
   return 0;
}
```
Вызов такой функций порождает новый параллельный процесс. Таким образом - количество компонент параллельной программы определяется количеством вызовов асинхронных функций.
Трансляция выполняется командой delta. Кроме текста MPI - программы, транслятор выдает количество параллельных компонент этой программы, это число используется утилитой mpirun.
```
$ delta myprog.c > myprog_mpi.c
components : 4
$ mpicc myprog_mpi.c -o myprog_mpi
$ mpirun -machinefile machines -np 4 myprog_mpi
```

Важной особенностью данной системы является ''гладкий синтаксис''. Введение ключевого слова asyncron является единственным отличием языка C $\Delta$ от стандартного C. Программа для распараллеливателя может, без каких либо изменений, собираться обычным (последовательным) транслятором языка C, достаточно добавить в заголовок программы #define asyncron, в этом случае получается обычная (последовательная) программа.

Распараллеливатель можно получить [ здесь ]

5.5 Пример

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

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

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

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

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

последовательная программа
количество итераций
время счета - 108 секунд
```
   $ cc pi.c -o pi
   $ ./pi 
   pi = 3.1415926535899708
```
параллельная программа на двух процессорах
количество итераций
время счета - 57 секунд
```
   $ delta pi.c > pi_mpi.c
   components : 3
   $ mpicc pi_mpi.c -o pi_mpi
   $ mpirun -machinefile machines -np 3 pi_mpi
   pi = 3.1415926535899708
```

Программа вычисления $\pi$ для распараллеливателя -- [ pi.c ]

Параллельная MPI-программа вычисления $\pi$ , результат работы распараллеливателя -- [ pi_mpi.c ]

Литература

1: Задачи для суперкомпьютеров - http://parallel.ru/research/apps.html
2: Основные классы современных параллельных компьютеров - http://parallel.ru/computers/classes.html
3: В.В.Воеводин, Вл.В.Воеводин Параллельные вычисления - Санкт-Петербург : БХВ-Петербург, 2002 - 608 стр.
4: А.Е.Дорошенко Математические модели и методы организации высокопроизводительных параллельных вычислений - Киев : Наукова думка, 2000 - 176 стр.
5: Коммуникационные библиотеки - http://www.parallel.ru/tech/tech_dev/ifaces.html
6: Средства распознавания параллелизма в алгоритмах - http://www.parallel.ru/tech/tech_dev/auto_par.html
7: Ю.В. Капитонова, А.А. Летичевский Математическая теория проектирования вычислительных систем - Москва : Наука, 1988 - 295 стр.
8: Т-система - http://t-system2.polnet.botik.ru

Evgeny S. Borisov
2004-09-16

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