Архитектура параллельных вычислений

Рассмотрим кратко основные языки и их расширения.

Fortran

Fortran — первый реализованный  язык программирования высокого  уровня, правда, с одной небольшой  оговоркой — для машин, построенных  по классической схеме фон  Неймана. Фортран широко используется  в первую очередь для научных  и инженерных вычислений. Одно  из преимуществ современного  Фортрана — большое количество  написанных на нём программ  и библиотек подпрограмм. 

Диалекты языка Fortran: Fortran-DVM, Cray MPP Fortran, F--, Fortran 90/95, Fortran D95, Fortran M, Fx, HPF, Opus, Vienna Fortran.

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

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

HPF - дальнейшее развитие языка Fortran 90. Включены богатые средства для распределения данных по процессорам. Необходимые коммуникации и синхронизации реализуются компилятором. Часть расширений реализована в виде функций и операторов языка, а часть - в виде директив компилятору.

Vienna Fortran 90 - дальнейшее развитие языка Fortran 90. Включает в себя многочисленные возможности распределения массивов данных по секциям процессорных массивов, а также распределения итераций циклов.

C/C++

Си— стандартизированный процедурный язык программирования, разработанный в начале 1970-х годо. Си был создан для использования в операционной системе UNIX. Для языка Си характерны современный набор конструкций управления потоком выполнения, структур данных и обширный набор операций.

C++ — компилируемый статически  типизированный язык программирования  общего назначения. В сравнении  с его предшественником — языком C, — наибольшее внимание уделено  поддержке объектно-ориентированного  и обобщённого программирования.

Charm/Charm++ - параллельные расширения  языков C и C++ соответственно. Программы,  написанные с их использованием, могут выполняться на компьютерах как с общей, так и с распределенной памятью.

Cilk - язык программирования  с поддержкой многопоточности,  базирующийся на языке C. Программист  должен заботиться о задании  максимального параллелизма, а его  использование и конкретную загрузку  процессоров определяет Cilk runtime system.

HPC - проект, разрабатываемый в CRIM (Centre de Recherche Informatique de MontrВal). Цель проекта - создание на основе языка C средства для поддержки параллельных вычислений на большом количестве различных платформ. Параллельные расширения языка строятся по аналогии с языком HPF.

MPL - объектно-ориентированный  язык программирования, базирующийся  на языке C++. Распределение данных  задается программистом, а все  необходимые пересылки и синхронизации  определяются компилятором и  осуществляются во время исполнения  с помощью Mentat run-time system.

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

MPC++ - расширение языка  C++, предназначенное для написания  параллельных программ. Каждому  процессору параллельного компьютера  сопоставляется один процесс,  который в свою очередь может  состоять из нескольких потоков.

Adl

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

Ada

Ada - универсальный язык  программирования, включающий в  себя средства для создания  параллельных программ. Официальный  язык программирования министерства  обороны США. Существует множество  компиляторов для самых разных  платформ.

MC#

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

DVM

DVM-система предназначена для создания переносимых и эффективных вычислительных приложений на языках C-DVM и Fortran-DVM для параллельных компьютеров с различной архитектурой.  Аббревиатура DVM соответствует двум понятиям: Distributed Virtual Memory и Distributed Virtual Machine.

Linda

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

NESL

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

Occam

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

Sisal

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

ZPL

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

 

3.2 Технологии  параллельного программирования

 

Введение в  технологию Open MP

В технологии Open MP за основу берется последовательная программа. Для создания параллельной версии пользователю представляются наборы:

1) директив,

2) процедур,

3) переменных окружения.

Стандарт Open MP разработан для языков Fortran и C (Fortran 77, 90, 95 и C, C++) и поддерживается производителями всех больших параллельных систем. Реализации стандарта доступны в UNIX и в среде Windows NT.

Конструкции Open MP в различных  языках мало отличаются, поэтому ограничимся языком Fortran.

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

Для поддержки параллелизма используется схема

FORK/JOIN.

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

В параллельной области все  переменные в программе делятся  на два класса:

1) общие (shared – разделяемые);

2) локальные (private – собственные).

Общие переменные существуют в одном экземпляре для всей программы  и под одним и тем же именем доступны всем нитям. Объявление локальной  переменной приводит к порождению многих экземпляров (по числу нитей) этой переменной под этим именем – по одному собственному экземпляру для каждой нити. Изменение  какой-либо нитью значения своего экземпляра локальной переменной никак не влияет на изменение значений экземпляров  этой переменной в других нитях.

Понятия областей программы  и классов переменных вместе с  порождением (расщеплением) и уничтожением (соединением) нитей определяют общую  идею написания программы с использованием технологии Open MP. Все директивы Open MP располагаются в комментариях и начинаются с одной из следующих комбинаций !$OMP, C$OMP или*$OMP (по правилам языка Fortran строки, начинающиеся с символов !,С или *, означают комментарии).

Все переменные окружения  и функции, реализующие стандарт Open MP, начинаются с префикса OMP_.

Описание параллельных областей: для такого описания используются две  директивы

!$OMP PARALLEL

< параллельная область  программы >

!$OMP END PARALLEL

Для выполнения фрагмента  программы, расположенного между данными  директивами, основная нить порождает  нити в количестве OMP_NUM_THREADS-1, где OMP_NUM_THREADS переменная окружения, значение которой пользователь задаёт перед запуском программы. Все порожденные нити исполняют программу, находящуюся между указанными директивами.

На директиве !$OMP END PARALLEL происходит неявная синхронизация нитей: сначала все нити достигают директиву!$OMP END PARALLEL, и лишь после этого происходит слияние всех нитей в основную нить, которая и продолжает процесс.

В параллельной области каждой имеющейся нитью может быть порождена  параллельная секция (порождение нитью  параллельных нитей) и последующее  их соединение (с сохранением главенства порождающей нити). Число нитей  в параллельной секции можно задавать с помощью функции OMP_SET_NUM_THEADS, которая устанавливает значение переменной OMP_ NUM_THEADS(при этом значения переменной OMP_DYNAMIC должно быть установлено в 1 с помощью функции OMP_SET_DYNAMIC). Стратегию обработки вложенных секций можно менять с помощью функции OMP_SET_NESTED.

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

!$OMP PARALLEL IF (< условие >).

Если < условие > не выполнено, то директива не выполняется и  программа обрабатывается в прежнем  режиме.

Распределение работы в Open MP можно проводить следующими способами:

1) программировать на  низком уровне;

2) использовать директиву !$OMP DO для параллельного выполнения циклов;

3) использовать директиву!$OMP SECTIONS для параллельного выполнения  независимых фрагментов программы;

4) применить директиву !$OMP SINGLE для однократного выполнения участка программы.

Возможности Open MP.

1. Синхронизация. Для синхронизации  работы нитей в Open MP предусмотрено  много возможностей; простейшая  из них использование директивы !$OMP BARIER. Нити, дошедшие до этой директивы, останавливаются, поджидая остальные нити; после достижения этой директивы всеми нитями работа продолжается.

2. Участок нити-мастера.  Фрагмент программы, который должна  выполнить лишь основная нить, определяется директивами 

!$OMP MASTER

<участок программы для  нити-мастера>

!$OMP END MASTER

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

3. Последовательное выполнение отдельного оператора. Директива !$OMP ATOMIC относится к непосредственно идущему за ней оператору, и её применение приводит к последовательному выполнению этого оператора всеми нитями.  4. Гарантированное поддержание когерентности. Вычислительная система может иметь сложную иерархию различных областей памяти, когерентность которых поддерживается автоматически. Однако, в некоторых случаях пользователь должен иметь особые гарантии того, что память, к которой он обращается, своевременно обновлена (синхронизирована). Для этого служит

Директива !$OMP FLASH[список переменных]

Применение этой директивы  приводит к синхронизации перечисленных  в списке переменных в том смысле, что все последние изменения  этих переменных будут внесены во все их копии.

 

Стандарт MPI.Элементы идеологии стандарта MPI

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

Основными понятиями MPI являются:

- процесс;

- группа процессов;

- коммуникатор.

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