о к идеалу (огромное поле для интеллектуальной деятельности, нет необходимости выписывать громоздкие конструкции об- мена данными в стиле MPI), однако эффективность создаваемых HPF- компиляторами параллельных программ невысока (оставшаяся после указа- ний программиста часть процесса распараллеливания компилятором автома- тически распараллелена полностью быть не может). В целом HPF-подход оказался чрезмерно романтичным (с точки зрения соответствия конструкци- ям языка программирования поставленным целям).
Другой подход основан на модели параллелизма по управлению (work- sharing, модель распределения работы) и формально заключатся в дополне- нии языков программирования специальными конструкциями управления –
- 99 -
параллельными циклами и
параллельными секциями. Глубинная основа под- хода заключается в представлении параллельной программы системой
ни-тей (нить -
thread – упрощенный процесс, взаимодействующий с другими нитями посредством общих переменных и простейшей синхронизации). При этом вспомогательную работу (создание и уничтожение нитей, распределе- ние между ними витков параллельных циклов и параллельных секций – вы- зовов процедур, напр.) выполняет компилятор.
Первая попытка разработки подобного подхода относится еще к 1990 г., но только в 1997 г. появился стандарт языка OpenMP Fortran (позднее появились аналоги для C и Fortran’90/95, [6], http://openmp.org
). Программа на OpenMP начинает свое выполнение в виде единственного (именуемого
главной ни-тью) процесса. Главная нить выполняется последовательно до тех пор, пока управление не дойдет до начала первой параллельной области программы
(описываемой директивами
PARALLEL
и
END PARALLEL
). При входе в парал- лельную область главная нить порождает определенное число подчиненных ей нитей, образующих вместе с ней
текущую группу нитей, при выходе из параллельной области все порожденные при входе в нее нити сливаются с главной нитью (в целом последовательно реализуется серия параллельных процессов, многократно повторяющая диаграмму рис.3б). Все находящиеся внутри параллельной области операторы (включая вызовы процедур) вы- полняются всеми нитями текущей группы параллельно до момента выхода из параллельной области или встречи одной из инструкций распределения рабо- ты
DO
(распределение витков цикла между нитями),
SECTIONS
(распределе- ние между нитями заданных секций программы),
SINGLE
(указание секции, которая должны выполняться единой нитью). Для организации вычислений используются высокоуровневые директивы синхронизации. Пример простой программы с использованием OpenMP приведен в Приложении 2.
Программирование в технологии OpenMP в целом проще, чем на HPF, од- нако распределение данных в OpenMP практически никак не описывается
(понятно, что OpenMP идеален для многопроцессорных вычислительных систем c общей памятью). Перспективным можно было бы считать дополне- ние OpenMP возможностями распределения данных, однако реально в на- стоящее время развивается подход, объединяющий OpenMP (средство про- граммирования процессов) и MPI (механизм объединения процессов) -
гиб-ридная модель параллелизма по управлению с передачей сообщений, [6].
Примером системы, объединяющей распределение как вычислений так и данных, является DVM (
Distributed Virtual Memory или
Distributed Virtual Machine, 1994, http://keldysh.ru/dvm
), существуют версии Fortran’DVM и
C’DVM. Система разработки параллельных программ DVM разработана в
ИПМ им. М.В.Келдыша при участии студентов и аспирантов МГУ [1,6].
В DVM и данные и вычисления по процессорам
виртуальной параллельной машины распределяет программист и именно на него возлагается полная от-
- 100 - ветственность за соблюдение (ему известных) правил вычислений. Програм- мист определяет не только общие (вычисляемые на одних, а используемые на других процессорах) данные, но и отмечает точки в последовательной про- грамме, где необходимо обновить (синхронизировать) данные. При этом текст DVM-программы является корректным и для обычных ‘последователь- ных’ компиляторов (в Fortran’е для задания DVM-директив используются строки комментариев, в С применяется механизм макросов), что позволяет осуществлять сначала отладку последовательной версии программы, а в дальнейшем тестировать DVM-расширения исходного текста и компилиро- вать параллельный вариант программы.
Объявленные в программе переменные (исключая описанные как ‘распре- деленные’ массивы) копируются по всем процессорам. В момент старта
DVM-программы создается единственная ее ветвь (
поток управления), при входе в параллельную конструкцию (напр., параллельный цикл или область параллельных задач) ветвь разбивается на определенное количество парал- лельных ветвей, каждая из которых исполняется на выделенном процессоре
(число процессоров и топология многопроцессорной системы задается в ко- мандной строке программы); при выходе из параллельной конструкции все ветви вновь сливаются в первоначальную ветвь.
Для распределения массивов в системе DVM используется директива
DIS-
TRIBUTE
, являющаяся дополнением описательной (неисполняемой) части программы. Например, строка
CDVM$ DISTRIBUTE mass_1 (BLOCK)
описыва- ет распределение ранее описанного одномерного Fortran-массива mass_1 на решетку процессоров равными блоками (
WGT_BLOCK(wb, nwb)
задает распре- деление неравными блоками, * - отображение целым измерением),
выравни-вание массивов (расположение нескольких массивов согласованно друг с другом – например, на одном и том же процессоре) достигается применени- ем директивы
ALIGN
. Директивы
REDISTRIBUTE
и
REALIGN
динамически из- меняют распределение данных. Параллельное выполнение циклов задается директивой
CDVM$ PARALLEL
с параметрами, директива
MAP
определяет со- ответствие выполняемых задач секции процессоров и т.д. (пример For- tran’DVM-программы приведен в Приложении 1в). Таким образом DVM реа- лизует
модель параллелизма по данным и по управлению.
В целом DVM-система высокоперенос
има, достаточно гибк
а в описании возможностей распараллеливания и, вместе с тем, позволяет сократить время разработки и отладки программ.
В Институте Системного Программирования РАН разработан специальный язык mpC высокого уровня для программирования неоднородных сетей
(
http://www.ispas.ru/mpc
). Язык mpC использует нотацию C и включает воз- можности, необходимые для определения всех важных свойств параллельно- го алгоритма (нужное число параллельных процессов, объем вычислений и передаваемых данных для каждого процесса, сценарий взаимодействия про-
- 101 - цессов и т.п., причем имеется возможность изменять эти характеристики во время выполнения программы).
В mpC понятие
сети служит механизмом, позволяющего разработчику абстрагироваться от физических особенностей конкретной вычислительной системы (в простейшем случае сетью является множество
виртуальных про-цессоров); после описания сети программист связывает отображение ее вир- туальных процессоров с реальными процессами параллельной программы.
Автоматическая сеть определена внутри блока программы, при выходе из этого блока все захваченные под виртуальные процессоры сети освобожда- ются и сеть может быть переопределена заново;
статическая сеть сущест- вует все время существования программы. Каждая вновь создаваемая сеть имеет ровно один виртуальный процессор (
родитель создаваемой сети), об- щий с уже существующими сетями (через него передаются результаты вы- числений при прекращении существования сети). В любой момент выполне- ния mpC-программы имеется предопределенная сеть host и
виртуальный хост-процессор (родитель всех сетей).
Размазанная переменная (массив) оп- ределена для всех процессов и ее значение одинаково в каждом из них.
Ба-зовые функции императивно выполняются всеми процессорами,
узловые функции могут быть вызваны отдельным процессом или группой процессо- ров,
сетевые аналогичны базовым, но выполняются на конкретных сетях.
Обмен данными между процессами выполняется с помощью механизма
под-сетей –
подмножества процессоров, объединяющих две (или несколько) се- тей.
Важной особенность mpC состоит в наличии средств для динамического распределения объемов вычислений по виртуальным процессорам (что необ- ходимо для балансировки вычислений по узлам неоднородных сетей); для этого используется встроенные язык
овые возможности, реализуемые опера- тором recon.
В целом mpC представляет программисту огромные возможности разра- ботки параллельных программ, однако требует высокого профессионализма как в логическом программировании так и в практическом использовании языка.
Пропагандируется также система ОРС (Открытая Распараллеливающая
Система
, Open Parallelizing System Group, http://ops.rsu.ru/about.shtml
) - про- граммная инструментальная система, ориентированная на разработку распа- раллеливающих компиляторов, оптимизирующих компиляторов с парал- лельных языков, систем полуавтоматического распараллеливания.
- 102 -
4.2 Системы параллельного программирования на основе обмена сообщениями Вышеописанные системы разработки параллельных программ, несмотря на требования явного описания распределения вычислений и данных по процес- сорам, все же возлагают на ‘параллельный’ компилятор работу по реализации этих описаний. В некоторых случаях бывает полезным иметь возможность самостоятельного максимально полного управления процессом обработки информации (включая распределение данных и вычислений и обмен сообще- ниями между ветвями программы).
Модель программирования MPI (
Message Passing Interface, 1994, http://mpiforum.org
) основана на передаче сообщений.
Сообщение состоит из блока (блоков) передаваемых данных и дополнительной информации (тип передаваемых данных, идентификатор сообщения, номер процесса- получателя и др.).
MPI иногда называют ‘ассемблерным уровнем’ в параллельном програм- мировании, основывая это
необходимостью максимально подробного описа-ния всех необходимых операций обменов данными между частями програм- мы, выполняющимися на отдельных процессорах; при этом распределение данных и вычислений полностью возлагается на программиста и выполняет- ся средствами б
азового языка программирования (что очень непросто, по- этому и применяются синтетические подходы – например, вышеупомянутый
OpenMP+MPI). Возможности MPI реализованы как набор (размещенных в соответствующей библиотеке) MPI-функций (существует интерфейс с Fortran и C/C++); появившийся в 1997 г. проект стандарта MPI-2 существенно рас- ширяет возможности MPI (напр., динамическое порождение и уничтожение процессов; при этом для MPI-1 диаграмма процессов соответствует рис.3б, а для MPI-2 – рис.3в). В настоящее время существуют две основные реализа- ции MPI – MPICH (
MPI & Chameleon, http://www-unix.mcs.anl.gov/mpi/mpich
) и
LAM (
Local Area Machine, http://www.lam-mpi.org
). Существуют сведения, что
MPI-2 реализован в системе программирования векторно-параллельной сис- темы Earth Simulator.
Вообще говоря, для написания подавляющего большинства программ дос- таточно 6-ти функций интерфейса MPI:
MPI_Init
- инициализация MPI-библиотеки
MPI_Comm_size
- определение числа процессов
MPI_Comm_rank
- определение процессом собственного номера
MPI_Send
- пос
ылка сообщения
MPI_Recv
- получение сообщения
MPI_Finalize
- завершение программы MPI
- 103 - среди которых основными являются функции
MPI_Send/MPI_Recv обмена сообщениями типа ‘точка-точка’. Однако для удобства программирования в
MPI включен широкий набор функций - широковещательная передача
MPI_Bcast
, разд
ача сообщений от одного процесса всем процессам группы
MPI_Scatter
, cбор данных от всех процессов в группе в один из процессов
MPI_Gather и т.п., функции барьерной синхронизации процессов
MPI_Barrier
, глобальные операции редукции
MPI_Reduce
,
MPI_Allreduce
,
MPI_Reduce_Scatter
,
MPI_Scan
(конкретная операция редукции может быть переопределена пользователем) и др.
При программировании на MPI программист обязан
контролировать ис- ходный текст на наличие структур, вызывающих (труднодетектируемые на работающей программе) дедлоки (
deadlock – тупиковая ситуация, зависание); возникновение дедлока при MPI-программировании обычно сопряжено с ис- пользованием
блокирующих функций обмена сообщениями. В данном случае дедлок – ситуация, когда первый процесс не может вернуть управление из функции пос
ылки, поскольку второй не начинает прием сообщения, а второй не может начать прием, ибо сам по той же причине не может выполнить по- с
ылку.
Дополнительную гибкость дает MPI возможность определения
виртуаль-ной топологии процессоров; при этом (независимо от физической топологии процессорной решетки) может вводиться топология n
-мерных кубов (торов) или произвольного графа (
MPI_CART_CREATE
,
MPI_GRAPH_CREATE
соответ- ственно и функции поддержки их использования). Виртуальные топологии служат как целям упрощения программирования (например, двумерная ре- шетка удобна для произведения матричных операций), так и способствуют повышению производительности (при корректном их отображении на физи- ческую топологию вычислительных узлов многопроцессорной системы).
В целом создание программ с использованием MPI – удел любителей наи- более тонкого, гибкого (низкоуровневого) программирования, однако (вслед- ствие именно этого) имеются возможности разработки надстроек над MPI, существенно упрощающих работу. MPI применен при разработке большого количества проблемно-ориентированных параллельных библиотек. Простой пример Fortran’MPI-программы приведен в Приложении 1г).
К ‘ручным’ (низкоуровневым) технологиям разработки параллельных про- грамм относится и система PVM (
Parallel Virtual Machine, http://epm.ornl.gov/pvm/pvm_home.html
), предложенная исторически ранее MPI
(проект –1989, реализация – 1991 г.). PVM стандартизирует не только
ин-терфейс программиста (набор и содержание предоставляемых функций), но и
интерфейс пользователя (команды пользователя, вводимые с клавиатуры для управления параллельной программы), [4]. Функции PVM предоставля- ются общедоступной библиотекой, существуют реализации PVM для самых различных платформ.
- 104 -
Виртуальной машиной (ВМ) называют совокупность узлов, на которых исполняется параллельная программа; функционирование ВМ достигается функционированием на каждом узле процесса -
демона PVM.
Консоль PVM – специальная программа, позволяющая управлять виртуальной машиной.
Имеется возможность программным путем изменять (активизируя и ‘выклю- чая’ узлы) состав ВМ, стартовать и включать в состав ветвей параллельных программ процессы (т.е. динамически порождать ветви параллельной про- граммы) или отсоединять их от ВМ. Любой PVM-процесс может информиро- вать другой ждущий от него сообщений
процесс сигналом о возникновении ошибки, этот сигнал является основой механизма избежания зависания или аварийного завершения. Программная реализация посылки сообщений про- ста, по умолчанию сообщения буферизуемы; вероятность дедлока минималь- на. Как и в MPI, кроме обменов ‘точка-точка’ имеются широковещательные и сообщения редукции.
PVM изначально проектировалась разработчиками как система для задач с крупным зерном параллелизма (требования к эффективности коммуникаций не столь высок
и – в период разработки PVM применялись 10 Mbit Ethernet- сети); популярность PVM до сих пор высок
а (основные производители су- перкомпьютеров снабжают свои изделия и MPI и PVM).
Системой параллельного программирования на основе передачи сообще- ний является система Linda (
http://cs.yale.edu
), разработанная в середине 80-х г.г. в США. Идея Linda основана на простых положениях: a) параллельная программа представлена множеством процессов, каждый из которых выполняется подобно обычной последовательной програм- ме, б) все процессы имеют д
оступ к общей памяти, причем единицей хранения данных является
кортеж (в этом смысле общая память суть
простран-ство кортежей), в) всем процессам доступны следующие операции с пространством корте- жей:
поместить кортеж (можно поместить имеющийся кортеж, после чего в пространстве кортежей окажется два кортежа с одинаковым име- нем),
забрать (после этого кортеж становится недоступным остальным процессам) и
скопировать, г) процессы не взаимодействуют друг с другом явно, а только через про- странство кортежей.
Т.о. в отличие от MPI (где допуст
им прямой обмен данными любого про- цесса с любым), в Linda обмены осуществляются фактически через некий
‘карман’ (‘пространство кортежей’, причем вследствие возможности при по- иске кортежа использовать метод совпадения значения отдельных его полей
- 105 -
‘пространство кортежей’ фактически является
виртуальной ассоциативной памятью).
Разработчики Linda доказывают, что любой последовательный язык про- граммирования для превращения его в средство параллельного программи- рования достаточно добавить лишь четыре новые функции (три функции для операций над пространством кортежей и одна для порождения параллельных процессов) [1]. Функция out(…)
помещает кортеж в пространство кортежей, in(…)
ищет в пространстве кортежей нужный (используется маска), read(…)
аналогична in без удаления кортежа (полезно использовать для параллельного д
оступа к переменным из нескольких процессов), функция eval(…)
порожда- ет отдельный параллельный
процесс для вычисления значений функций, пе- речисленных в списке формальных параметров вызова функции, вычислен- ное значение помещается в пространство кортежей аналогично вызову out
Если в пространстве кортежей ни один кортеж не соответствует заданному в in или read образцу, процесс блокируется до момента появления соответст- вующего кортежа. Параллельная программа в системе Linda завершается, ко- гда все порожденные процесс завершились или все заблокированы функция- ми in и read
Указанные язык
Скачать 1.75 Mb.