Студопедия
Главная страница | Контакты | Случайная страница | Спросить на ВикиКак

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. D) программа
  2. E) сферу по обслуживанию сельского хозяйства и по обеспечению его необходимыми для производства средствам
  3. I)Однофакторный дисперсионный анализ (выполняется с применением программы «Однофакторный дисперсионный анализ» надстройки «Анализ данных» пакета Microsoft Excel).
  4. I. Оценка обеспеченности предприятия основными средствами
  5. I. Программирование на CF Pascal
  6. I. Рабочая программа дисциплины
  7. I. Решение логических задач средствами алгебры логики
  8. I. Языки программирования
  9. IF(POS('ПРОГРАММИР',NAZ)<>0) AND
  10. II Кредиты и другие заемные средства

OCCAM - ориентированный на программирование транспьютерных устройств язык - C.Hoar, 1984),

основаны на традиционных языках - существуют параллельный C, параллельные Pascal, Fortran и даже ParJava

Оrса использующим объектно-ориентированный подход и поддерживающим параллельность по задачам и по данным,

ZPL обеспечивает параллельность по данным, является переносимым и достаточно производительным

Cilk расширяет ANSI C пятью (ключевые слова cilk, spawn, synch, inlet и abort) несложными инструментами для параллельного программирования,

MPI (Message Passing Interface, 1994, http://mpiforum.org) Модель программирования основана на передаче сообщений. Сообщение состоит из блока (блоков) передаваемых данных и дополнительной информации (тип передаваемых данных, идентификатор сообщения, номер процесса-получателя и др.).

Вообще говоря, для написания подавляющего большинства программ достаточно 6-ти функций интерфейса MPI:

 

MPI_Init - инициализация MPI-библиотеки
MPI_Comm_size - определение числа процессов
MPI_Comm_rank - определение процессом собственного номера
MPI_Send - посылка сообщения
MPI_Recv - получение сообщения
MPI_Finalize - завершение программы MPI

 

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

PVM (Parallel Virtual Machine) ‘ручная’ (низкоуровневым) технология разработки параллельных программ.

Виртуальной машиной (ВМ) называют совокупность узлов, на которых исполняется параллельная программа; функционирование ВМ достигается функционированием на каждом узле процесса - демона PVM.

Linda - Система параллельного программирования на основе передачи сообщений

Идея Linda основана на простых положениях:

a) параллельная программа представлена множеством процессов, каждый из которых выполняется подобно обычной последовательной программе,

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

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

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

Разработчики Linda доказывают, что любой последовательный язык программирования для превращения его в средство параллельного программирования достаточно добавить лишь четыре новые функции (три функции для операций над пространством кортежей и одна для порождения параллельных процессов). Функция out(…) помещает кортеж в пространство кортежей, in(…) ищет в пространстве кортежей нужный (используется маска), read(…) аналогична in без удаления кортежа (полезно использовать для параллельного доступа к переменным из нескольких процессов), функция eval(…) порождает отдельный параллельный процесс для вычисления значений функций, перечисленных в списке формальных параметров вызова функции, вычисленное значение помещается в пространство кортежей аналогично вызову out.

Для записи параллельных программ были созданы параллельные языки. Они могут быть совершенно новыми (например, ориентированный на программирование транспьютерных устройств язык OCCAM - C.Hoar, 1984), а могут быть основаны на традиционных языках - существуют параллельный C, параллельные Pascal, Fortran и даже ParJava (Институт Системного Программирования РАН, http://www.ispras.ru/~javap/parallel_java/par_java/ parjava.html). Другим языком параллельного программирования, использующим объектно-ориентированный подход и поддерживающим поддерживает параллельность по задачам и по данным, является Оrса (Henri Bal, Амстердамский университет, 1989, http://www.cs.vu.nl/orca). Язык ZPL (Larry Snyder, http://www.cs.washington.edu/research/zpl) обеспечивает параллельность по данным, является переносимым и достаточно производительным. Язык Cilk (Charles Leiserson, Massachusetts Institute of Technology, http://supertech.ics.mit.edu/cilk) расширяет ANSI C пятью (ключевые слова cilk, spawn, synch, inlet и abort) несложными инструментами для параллельного программирования, разработан для эффективного выполнения параллельных программ на симметричных мультипроцессорах с разделяемой памятью, поддерживает параллелизм по вычислениям и по данным, позволяет эффективно работать с параллельной рекурсией; с использованием 5-й версии Cilk создано несколько шахматных программ (одна из них, Cilkchess, показала хорошие результаты на всемирном компьютерном чемпионате по шахматам 14 20.VI.1999 г. в Paderborn, Germany).

Весьма показательным является связанное с проблемой распараллеливания алгоритмов обращение к результатам (давно разрабатываемой) теории функционального программирования (Т-система, НОРМА). Практическая реализация положений функционального программирования фактически переводит центр тяжести с операторного управления процессом обработки данных на процесс, управляемый данными.

Загрузка...

Можно реализовать data flow на чисто алгоритмическом уровне (аппаратная часть остается control flow и выполняет традиционно императивные инструкции), именно для этого как нельзя подходят идеи функционального программирования.

Модель программирования MPI (Message Passing Interface, 1994, http://mpiforum.org) основана на передаче сообщений. Сообщение состоит из блока (блоков) передаваемых данных и дополнительной информации (тип передаваемых данных, идентификатор сообщения, номер процесса-получателя и др.).

MPI иногда называют ‘ассемблерным уровнем’ в параллельном программировании, основывая это необходимостью максимально подробного описания всех необходимых операций обменов данными между частями программы, выполняющимися на отдельных процессорах; при этом распределение данных и вычислений полностью возлагается на программиста и выполняется средствами базового языка программирования (что очень непросто, поэтому и применяются синтетические подходы – например, вышеупомянутый OpenMP+MPI). Возможности MPI реализованы как набор (размещенных в соответствующей библиотеке) MPI-функций (существует интерфейс с Fortran и C/C++); появившийся в 1997 г. проект стандарта MPI-2 существенно расширяет возможности MPI (напр., динамическое порождение и уничтожение процессов; при этом для MPI-1 диаграмма процессов соответствует рис.2.2б, а для MPI-2 – рис.2.2в). В настоящее время существуют две основные реализации 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

 

среди которых основными являются функции 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 стандартизирует не только интерфейс программиста (набор и содержание предоставляемых функций), но и интерфейс пользователя (команды пользователя, вводимые с клавиатуры для управления параллельной программы). Функции PVM предоставляются общедоступной библиотекой, существуют реализации PVM для самых различных платформ.

Виртуальной машиной (ВМ) называют совокупность узлов, на которых исполняется параллельная программа; функционирование ВМ достигается функционированием на каждом узле процесса - демона PVM. Консоль PVM – специальная программа, позволяющая управлять виртуальной машиной. Имеется возможность программным путем изменять (активизируя и ‘выключая’ узлы) состав ВМ, стартовать и включать в состав ветвей параллельных программ процессы (т.е. динамически порождать ветви параллельной программы) или отсоединять их от ВМ. Любой PVM-процесс может информировать другой ждущий от него сообщений процесс сигналом о возникновении ошибки, этот сигнал является основой механизма избежания зависания или аварийного завершения. Программная реализация посылки сообщений проста, по умолчанию сообщения буферизуемы; вероятность дедлока минимальна. Как и в MPI, кроме обменов ‘точка-точка’ имеются широковещательные и сообщения редукции.

PVM изначально проектировалась разработчиками как система для задач с крупным зерном параллелизма (требования к эффективности коммуникаций не столь высоки – в период разработки PVM применялись 10 Mbit Ethernet-сети); популярность PVM до сих пор высока (основные производители суперкомпьютеров снабжают свои изделия и MPI и PVM).

Системой параллельного программирования на основе передачи сообщений является система Linda (http://cs.yale.edu), разработанная в середине 80-х г.г. в США. Идея Linda основана на простых положениях:

 

a) параллельная программа представлена множеством процессов, каждый из которых выполняется подобно обычной последовательной программе,

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

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

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

 

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

Разработчики Linda доказывают, что любой последовательный язык программирования для превращения его в средство параллельного программирования достаточно добавить лишь четыре новые функции (три функции для операций над пространством кортежей и одна для порождения параллельных процессов). Функция out(…) помещает кортеж в пространство кортежей, in(…) ищет в пространстве кортежей нужный (используется маска), read(…) аналогична in без удаления кортежа (полезно использовать для параллельного доступа к переменным из нескольких процессов), функция eval(…) порождает отдельный параллельный процесс для вычисления значений функций, перечисленных в списке формальных параметров вызова функции, вычисленное значение помещается в пространство кортежей аналогично вызову out.


Дата добавления: 2014-12-15; просмотров: 21 | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2017 год. (0.168 сек.)