на главную ] 

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

Е.С.Борисов

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

1 Введение

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

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

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

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

где $ T(i)$ - время выполнения программы на $ i$ процессорах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где


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

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

$\displaystyle A(Y,U)$ (3)

где

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

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

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


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

Для множества регулярных программ $ P=\{P_i\}$ модель распределённой памяти строится следующим образом :
Множество переменных $ I_i$ регулярной программы $ P_i$ назовём множеством внутренних переменных или внутренней памятью программы $ P_i$ если $ I_i\cap I_j = \oslash$ для $ i\neq j$
тогда множество $ I=\bigcup\limits_i I_i$ назовём распределённой памятью $ P$

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

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

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

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

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

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

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

  1. порождается параллельный процесс $ p'$, с подпрограммой $ f'(x)$
  2. выходные переменные $ y$, подпрограммы $ f'$, помещаются в очередь неготовых значений процесса $ p$.
  3. вызвавшая подпрограмму $ f'$, подпрограмма $ f$ продолжает свою работу до тех пор, пока ей не понадобятся значения в переменных $ y$, в этом месте $ f$ происходит ожидание возврата $ f'$ (т. е. синхронизация процессов $ p$ и $ p'$)

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

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

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

где $ (s_i,S_i)$ - i-тая подпрограмма

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

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

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

Здесь

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

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

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

где

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

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


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

$\displaystyle \Pi=(P,\Sigma,\sigma_0,\Sigma_E,\delta)$
Здесь

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

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

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

Здесь

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) кластере необходимо выполнить следующие шаги.

  1. Инсталлировать MPICH на головной узел (машина, с которой будем запускать MPI-программы) кластера. Инсталлировать MPICH на все узлы кластера обычно не требуется.

  2. MPICH использует rsh (remote shell) для запуска процессов на узлах кластера. Поэтому необходимо запустить на каждом узле rshd (remote shell server) и согласовать права доступа.

    Для обеспечения более высокого уровня сетевой безопасности можно использовать ssh - OpenSSH remote login client.

  3. Компиляция MPI-программы на языке С выполняется утилитой mpicc, представляющей собой надстройку над C-компилятором, установленным в данной OS.
    mpicc myprog.c -o myprog

  4. Перед запуском ''бинарника'' myprog необходимо разослать его на все узлы кластера, причем локальный путь до myprog должен быть одинаковый на всех машинах, например - /usr/mpibin/myprog.

    Вместо процедуры копирования программы на узлы можно использовать NFS (Network File System) :

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

  5. Запуск 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 является единственным отличием языка 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 Результаты счета



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