1. Os linda.

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

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

Недостатком является избыточная передача информации между отельными кортежами.

2. OS Idris (для SuperNode).

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

3. Os trollius.

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

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

4. OS MEIKOS.

В этой системе реализован режим разделения времени. Все ресурсы системы разделяются на домены. В пределах одного домена пользователю разрешается выполнять любую программу. В пределах одного домена – однопользовательский режим. В отдельном домене выполняется файловый сервер.

5. OS HELIOS.

Эта система по идеологии похожа на Unix, построена на основе модели «Клиент-Сервер», причем, процессы-клиенты и процессы-серверы могут выполняться на различных процессорах. Системные вызовы стандартизованы. В системе реализован специальный механизм маршрутизации. Интерфейс пользователя напоминает интерфейс Unix на уровне командных строк.

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

ЯЗЫК НОРМА.

Норма - полностью отечественная разработка. Относится к непроцедурным языкам.

НОРМА - предназначен для решения систем дифференциальных уравнений в частных производных методом сеток.

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

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

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

ЯЗЫК НОРМА (ПРОДОЛЖЕНИЕ)

13/10

В языке НОРМА основополагающими понятиями являются:

ОБЛАСТЬ и оператор

ПОЛАГАТЬ.

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

Сетка представляет собой векторное N-мерное пространство, в котором определены N направлений, и с каждым таким направлением связано уникальное имя, называемое индексом направления.

Любая область является некоторой ограниченной частью такой сетки.

Язык Бэкуса-Наура.

<понятие>::=<определение понятия> [необязательный элемент] {необязательный элемент}

| - элемент “ИЛИ”

• <одномерная область> ::= {<имя одномерной области>:} (<индекс> = <список значений>)

• <список значений>::=<значения>|<список значений>,<значение>

• <значение>::=<диапазон>|<имя диапазона>,<простое выражение>

• <диапазон>::={<имя диапазона>}|<начало диапазона>..<конец диапазона>

• <имя диапазона>::=<простой идентификатор>

• <начало диапазона>::=<простое выражение>

• <конец диапазона>::=<простое выражение>

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

Область произведения.

• <область произведения>::= {<имя области произведения>:}(список составляющих областей)

• <элемент списка>::=<одномерная область>|<имя одномерной области>|<область произведения>

Элементы списка отделяются символом точка с запятой.

• <область>::= {<имя области>:}(<список областей>)

Объединение областей обозначается запятой.

Пример описания области S.

S:(SIJ:(SI:(I=1..100); SJ: (J=1..200)); SL: (L=20..N))

В этом примере описывается область S, которая образуется из областей SIJ и SL, причем SL – одномерная, SLJ – двумерная, которая в свою очередь стоит из двух одномерных областей: SI и JS. Все описание представляет трехмерную область. SI, SJ и SL – номера подобластей. I, J, L – номера индексов направления.

На основе области S – может быть построена другая область S1

S1:(SIJ; SK:(K=1..N-2))

Условные области.

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

ЛЕВ() и

ПРАВ().

Пример:

SN1:S/SI ЛЕВ(2)+ПРАВ(1)

В этом описании формируется условная подоблость SN1, которая получается из исходной области S путем исключения из составляющей области SI слева двух точек и добавления справа одной точки.

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

Пример:

SA, SB : S/X + Y[I,J] – Z[J+1] > 0

В этом примере описываются две предикатные подобласти SA и SB. Переменные X, Y и Z должны быть заданы в узлах сетки. К подобласти SA относятся те узлы области S, для которых выполняется указанное неравенство. К подобласти SB относятся все остальные узлы.

Очевидно, что

SA  SB = 0

SA  SB = S

Типы величин в языке НОРМА.

ЦЕЛЫЙ

ВЕЩЕСТВЕННЫЙ

ВЕЩЕСТВЕННЫЙ С ДВОЙНОЙ РАЗРЯДНОСТЬЮ

• <описание скалярной величины>::=ВЕЛИЧИНЫ <список величин> СКАЛЯРЫ{<тип>}

• <описание величины, определенной на сетке> ::= ВЕЛИЧИНЫ <список величин> ОПРЕДЕЛЕНЫ НА <область> {<тип>}

Пример:

ВЕЛИЧИНЫ x,y,z СКАЛЯРНЫ ЦЕЛЫЕ

ВЕЛИЧИНЫ Vel, Po, tan ОПРЕДЕЛЕНЫ НА S

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

• <величина на сетке>::=<идентификатор> {[<список индексных выражений>]}

• <индексные выражения>::=<имя индекса> + <целое без знака>|<имя индекса>-<целое без знака>| <имя индекса>=<целое без знака>|<имя индекса>=<имя индекса>+<целое без знака>|<имя индекса>=<имя индекса>-<целое без знака>|<имя индекса>=<имя индекса>

• <описание индексной конструкции>::=ИНДЕКСНАЯ КОНСТРУКЦИЯ <имя> [<список индексных выражений>]

Пример:

ИНДЕСНАЯ КОНСТРУКЦИЯ НИЗ [I-1, Y-1, K+1]

Тогда V[НИЗ, L+1] ~ V[I-1, J-1, K+1, L+1] эквивалентно.

Входные и выходные величины в языке НОРМА.

В программе на языке НОРМА все величины, значения которых задаются из вне, должны быть описаны как входные, а величины, являющиеся результатами работы программы должны быть описаны как выходные.

Пример:

ВХОДНЫЕ x,y,U

ВЫХОДНЫЕ давление, плотность ПО треугольнику

В этом примере описываются входные величины x,y,U как СКАЛЯРНЫЕ. Выходные величины давление и плотность определены по треугольнику.

Так как язык НОРМА является непроцедурным, в программе явно не описываются порядок вычислений, который будет установлен транслятором на основе анализа соотношений между входными и выходными величинами, следовательно в программе на языке НОРМА невозможен потокоориентированный ввод и вывод. И все данные (входные и выходные) на внешнем носителе должны быть представлены в виде <идентификатор> = <значение>.

ОПЕРАТОРЫ ЯЗЫКА НОРМА.

20/11

Скалярный оператор (ничем не отличается от оператора на языке ФОРТРАН)

и оператор ПОЛАГАТЬ.

<ПОЛАГАТЬ>::=ДЛЯ <область> ПОЛАГАТЬ <список соотношений >

Этот оператора отличается от обычного оператора присваивания тем, что не требует немедленного присвоения значений переменным, указанным в списке соотношений.

При обработке оператора ПОЛАГАТЬ транслятор анализирует список соотношений для каждого узла указанной области, определяет необходимый порядок вычислений и возможность параллельного счета.

Пример 1:

S: (1..M) – область «S»

S1: S / S-ЛЕВ(1) – подобласть «S1»

ДЛЯ S1 ПОЛАГАТЬ X[I] = X[I-1] + X[I+1]

В этом примере может быть реализован только последовательный счет.

Пример 2:

Пусть 1 ≤ i ,j ≤ 7

X_i,j = f_x (X_i-1,j+1, Y_i-1,j+2)

Y_i,j = f_y (X_i+1,j-1, Y_i+3,j-1)

Если исследовать эти соотношения, то для этого примера можно составить две таблицы:

X

 i

1	1	1	1	1	1	1
1	2	2	2	2	2	2
1	7	6	4	4	4	3
1	8	8	7	6	5	5
1	10	9	9	8	7	6
1	12	11	10	10	9	8
1	4	13	12	11	11	10

Y

 i

6	5	3	3	3	1	1
7	7	5	5	4	1	1
9	8	7	6	6	1	1
11	10	9	8	7	1	1
13	12	11	10	9	1	1
14	13	13	12	11	1	1
1	1	1	1	1	1	1

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

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

Можно изменить содержание этих таблиц за счет увеличения общего числа шагов, и при этом можно организовать параллельный регулярный счет, что и было выполнено транслятором с языка НОРМА для указанных соотношений.

X

 i

7	6	5	4	3	2	1
9	8	7	6	5	4	3
11	10	9	8	7	6	5
13	12	11	10	9	8	7
15	14	13	12	11	10	9
17	16	15	14	13	12	11
19	18	17	16	15	14	13

Y

 i

8	7	6	5	4	3	2
10	9	8	7	6	5	4
12	11	10	9	8	7	6
14	13	12	11	10	9	8
16	15	14	13	12	11	10
18	17	16	15	14	13	12
20	19	18	17	16	15	14

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

Эта задача (поиск) уравнений прямых сходна с задачей метода гиперплоскостей, однако здесь вычисление отдельных величин может «рассыпаться» по нескольким плоскостям.

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

ФУНКЦИИ В ЯЗЫКЕ НОРМА.

• <функция>::=<математическая функция> | <стандартная арифметическая функция> | <арифметическая функция> | <внешняя функция>

• <математическая функция>::=<имя математической функции><область><арифметическое выражение>

Пример

, i = 1,n

ВЕЛИЧИНА Y ОПРЕДЕЛЕНА НА C1: (i = 1,..n)

ВЕЛИЧИНА A ОПРЕДЕЛЕНА НА CЕТКА (С1, j = 1,..n)

ВЕЛИЧИНА X ОПРЕДЕЛЕНА НА C2 (z = 1,..n)

ДЛЯ С1 ПОЛАГАТЬ Y = i *SUM ( (j = 1…i-1) A[I,j] * x[j])

Организация циклов.

Для организации циклов в языке НОРМА вводится специальная процедура ИТЕРАЦИЯ. При этом возникает дополнительный индекс, связанный с итерационным процессом, который можно трактовать как обычный индекс, связанный с дополнительным направлением.

Пример.

Пусть задана система уравнений:

, i = 1,2….m

Пусть требуется найти решение методом итераций в виде

, i = 1,2….m, x = x0, |xⁿ – xⁿ⁺¹| < ε

МАТРИЦА: (С1: (i=1..m); C2: (j=1..m))

ВЕЛИЧИНА Х0, х, f ОПРЕДЕЛЕНА НА С1 ВЕЩЕСТВЕННАЯ

ВЕЛИЧИНА А ОПРЕДЕЛЕНА НА МАТРИЦА ВЕЩЕСТВЕННАЯ

ПАРАМЕТР СЕТКИ m = 100

ВХОДНЫЕ Х0 ПО МАТРИЦА

ВХОДНЫЕ EPS, A ПО МАТРИЦА

ВЫХОДНЫЕ XRES ПО С1

ВЕЛИЧИНА EPS СКАЛЯР

ИТЕРАЦИЯ Х (ХRES) ПО n

НАЧАЛЬНЫЕ ЗНАЧЕНИЯ n=0

ДЛЯ С1 ПОЛАГАТЬ Х=Х0

КОНЕЦ

ДЛЯ С1 ПОЛАГАТЬ

Х = 1/А [J=1] *f - SUM((C2 / i<>j) A*X [i=j, n=1])

ВЫХОД ПРИ MAX((C1) ABS(X - X[n-1])) < EPS

КОНЕЦ ИТЕРАЦИИ

Программа на языке НОРМА представляет собой последовательность разделов, один из которых является главным и обязательно присутствует в программе.

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

Вызов раздела выполняется оператором CALL, в котором задается имя раздела и фактические параметры. Правила оформления разделов такие же как правила оформления подпрограмм на языке программ.

АСИНХРОННЫЕ ПАРАЛЛЕЛЬНЫЕ ПРОЦЕССЫ

4/12

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

Асинхронные процессы не требуют одинаковой скорости работы процессоров и жесткой потактовой синхронизации.

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

Такие ресурсы

- различные устройства

- общая память

- общие структуры данных

Взаимодействие параллельных процессов основано:

1. Синхронизация 2-х и более процессов

2. Проблема «производитель - потребитель»

3. Проблема взаимных блокировок

Синхронизация параллельных процессов.

Проблема синхронизации возникает при использовании параллельными процессами общих ресурсов:

- аппаратные ресурсы

- программные ресурсы (структуры данных и процедуры)

- информационные ресурсы

Режимы использования:

- монопольное (ресурсом владеет только один процесс)

- разделяемое (ресурсом владеет любое число процессов)

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

Задача синхронизации – обеспечить вхождение в свою критическую секцию только одного процесса.

Средства синхронизации:

- высокого уровня

- низкого уровня

Нижний уровень: средство «двоичный семафор»

Двоичный семафор: принимается значение 0 / 1 при выполнении операций

P(x)	x, если x = 0
	x-1, если x = 1
V(x)	x, если x = 1
	x+1, если x = 0

Замечание: P и V операции должны быть неделимыми. Начавшись, они не могут быть прерваны.

Для синхронизации процессов на высоком уровне используются мониторы Xoap.

Хоар – монитор: совокупность процедур и структур данных, которыми в любой момент времени реализуется лишь один процесс.

Проблема «производитель - потребитель».

Проблема «производитель - потребитель» возникает при взаимодействии асинхронных параллельных процессов, использующих потребляемые («расходуемые») ресурсы.

Все ресурсы вычислительной системы делятся на 2 типа:

• SR – повторно используемые (все аппаратный ресурсы и неизменяемые ресурсы структуры данных)

• CR – потребляемые (изменяемые структуры данных и процедуры, а также все сообщения и сигналы.)

SR ресурсы: после освобождения процессом возвращаются в систему в неизменном виде для дальнейшего использования.

СR ресурсы: не возвращаются в систему или возвращаются в изменённом виде

Данная проблема решается с помощью общих семафоров.

Общий семафор – целочистенная переменная, принимающая значения 0 ≤ x ≤ n.

Операции

P(x)	x-1, если x > 0
	0, если x = 0 – перевод процесса в режим ожидания
V(x)	x+1, если x < n
	x, если x = n

Процесс-производитель выполняет над общим семафором V операцию, а процесс-потребитель – P операцию. Т.о. осуществляется их синхронизация.

Общий семафор имеет физический смысл:

Проблема взаимных блокировок.

Тупик

Тупиковое состояние

Клинч

Дедлок

Смертельное объятие

Пример:

SR система – тупиковая ситуация.

Причем, процесс Р1 не освобождает Р2, пока не получит Р1; аналогично с Р2.

Тупиковое состояние:

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

2. Процессы удерживают некоторые ресурсы, и система без внешнего воздействия не может выйти из этого состояния.

Меры борьбы с тупиками

- Статические

- Динамические

• Обнаружение с последовательным выходом из тупика

  • Прекращение

    • Ручной выход

    • Автоматический

  • Перехват ресурсов

• Методы предотвращения

  • Метод упорядоченных классов

  • Алгоритм банкира

Статические методы – методы одного решения. Применяются в системах, где простые алгоритмы, число параллельных процессов ограничено.

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

Прекращение процессов

- с ручным выходом: ограниченное количество ресурсов, в которых можно найти косвенные критерии попадания системы в тупик (например, существенное увеличение времени выполнения процесса)

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

Минимальная цена выхода (Прекращение процессов с автоматическим выходом)

Р₁ С₁

……….

Р_n P_n

P_n – параллельные процессы

C_n – цена, внешняя, динамически назначаемая.

Цена отображает ценность процесса.

Затем формируется шкала цен для всех процессов и всех сочетаний.

Р₁ + Р₂ – С₁ + С₂

…………………..

Полученная шкала сортируется по возрастанию.

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

Процессы, входящие в цикл, составляют тупиковое множество.

Алгоритм

1. Если система находится в тупиковом состоянии, то в шкале цен помечаются процессы, входящие в тупиковое множество.

2. Моделируется состояние системы, если прекратить процесс с минимальной ценой.

3. Затем снова анализируется граф состояний. Если система выходит из тупика – алгоритм заканчивается, и выдаётся команда на прекращение процесса.

4. Если система не выходит из тупика, то восстанавливается предыдущее состояние и выбирается другая группа процессов.

АЛГОРИТМ БАНКИРА

11/12

В алгоритме Банкира (на основе априорной информации о процессах и ресурсах) перед выполнением каждой элементарной операции (операция запроса на ресурс SR типа, CR типа или освобождения ресурса CR типа) проверяется новое состояние системы.

В случае удовлетворения этого запроса - если состояние безопасное, то запрос удовлетворяется, в противном случае - нет.

Все состояния системы делятся на три категории:

- безопасное,

- опасное,

- тупиковое.

Пояснение: Граф переходов из состояния в состояние:

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

Опасными считаются состояния, из которых возможен переход в тупиковое состояние.

Из тупикового состояния невозможен переход ни в какое другое состояние.

Алгоритм банкира исключает попадания системы в опасные состояния.

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

Алгоритм банкира состоит из двух частей:

1. Первая часть определят тип будущего состояния

2. Вторая часть принимает решения и корректирует модель.

Одно из возможных решений представлено в виде программы на псевдокоде.

if ВЫДЕЛ [i,j] + ЗАПРОС > АНОНС [i,j] then

< ошибка ; полный запрос анонса >

else

if ЗАПРОС [i,j] > СВОБ [j] then

< поставить p_i в ожидание >

else

< определить новое состояние:

ВЫДЕЛ [i,j] := ВЫДЕЛ [i,j] + ЗАПРОС [i,j]

СВОБ [j] := СВОБ [j] – ЗАПРОС [i,j]>

end_if;

if НОВОЕ СОСТОЯНИЕ БЕЗОПАСНО then

< выделить ресурс j процессу i >

else

< восстановить исходное состояние >;

< поставить p_i в ожидание >

end_if;

end_if;

РАСПТЕКУЩ: table [0…m-1] of ЦЕЛЫЙ;

ОСТ: SET of ПРОЦЕССЫ;

РАСПТЕКУЩ:= СВОБОДНЫЙ;

ОСТ:= { ВСЕ ПРОЦЕССЫ };

ВОЗМОЖН:= ИСТИНА;

while ВОЗМОЖН do

< ИСКАТЬ P в ОСТ такой, что АНОНС [i,*] – ВЫДЕЛ [i,*] ≤ РАСПТЕКУЩ >;

if ПРОЦЕСС найден then < имитировать выполнение P >;

РАСПТЕКУЩ:= РАСПТЕКУЩ + ВЫДЕЛ [i,*];

ОСТ:= ОСТ – {P}

else

ВОЗМОЖН:= ЛОЖЬ;

end_if

end_while;

СОСТОЯНИЕ БЕЗОПАСНО:= { ОСТ:= < пусто >}

Достоинства и недостатки алгоритма банкира.

Достоинства: самый распространенный алгоритм когда недопустим тупик.

Недостатки:

• алгоритм требует априорной информации о потребностях всех процессов в ресурсах системы;

• алгоритм работает при ПОСТОЯННОМ составе процессов и ресурсов;

• алгоритм очень ресурсоемкий – потребление на собственные нужды ресурсов систем очень велико.

Современные тенденции в параллельном программировании.

При параллельном программировании разработчик, кроме составления алгоритма решения задачи, должен дополнительно:

• Определить возможность параллельного выполнения отельных частей программы.

• Распределить выделенные части алгоритма по отдельным параллельным ветвям с учетом архитектуры вычислительной системы.

• Обеспечить синхронизацию параллельных ветвей алгоритма.

• Распределить исходные данные и промежуточные результаты между параллельными ветвями алгоритма.

• Защитить параллельные части программы от взаимных блокировок.

• На каждом этапе проектирования алгоритма оценивать его эффективность.

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

Три наиболее распространенные системы параллельного программирования.

PVM

MPI

DVM

PVM

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

В настоящее время PVM используется на различных аппаратных платформах, включая системы с массовым параллелизмом.

В общем случае число задач, решаемое параллельно, может превосходить число процессоров.

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

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

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

Достоинством PVM является простота использования, наличия наследованного от Unix аппарата процессов и сигналов и возможность динамического добавления вновь созданных процессов.

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

MPI

Система MPI включает как минимум два компонента:

- библиотеки функций для языков C/C++ и фортран,

- загрузчик исполняемых файлов.

В системе MPI не предусмотрено средств декомпозиции и не предусмотрен отладчик. Фактически MPI является системой межпроцессной связи.

В настоящее время система MPI является стандартом передачи сообщений и основой других параллельных систем программирования.

MPI в свою очередь имеет две версии: MPI и MPI2 (расширенная и модернизированная версия).

Существует множество реализаций MPI. Одна из наиболее известных это MPICH.

В MPI реализована модель параллелизма, называемая SPMD, которая является частным случаем модели MIMD. При написании программы, в системе MPI кодируются все параллельные ветви сразу.

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

В системе MPI количество процессов фиксировано, в системе MPI2 оно может меняться динамически в процессе решения задач.

Недостаток систем – синтаксическому разбору должны подвергаться оба текста.

Для решения задач анализа ветвей были разработаны специальные языки

mpC (massiv parallel C)

HPF (High Perfomance Fortran)

Все последующие разработки базируются на стандарте MPI.

18/12

«Разработка параллельных программ для вычисления кластеров и сетей»

В.А. Крюков

Институт прикладной математики им. М.В. Келдыша РАН

www.keldysh.ru

Разработки: HP-MPI и др.

DVM

Модели параллелизма:

- по данным

- параллелизм задач

Каждый экземпляр программы обрабатывает свое подмножество данных. Такой подход наиболее оправдан при распараллеливании гнездовых циклических алгоритмов.

Преимущества системы DVM:

• Простота разработки параллельных программ

• Мобильность системы

• Высокая эффективность выполнения программ

• Возможность композиции параллельных приложений из нескольких различных модулей

• Единая модель параллелизма для языков

  • Cи-DVM

  • Фортран-DVM

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

ГЛАВНОЕ ПРЕИМУЩЕСТВО: Программа на языке Cи-DVM или Фортран-DVM может выполняться как в обычном (последовательном) режиме, или как параллельная программа. Это достигается благодаря тому, что все специальные директивы для параллельного выполнения записываются в виде комментариев на соответствующем языке (Си или Фортран), и таким образом, не воспринимаются стандартным компилятором.

При использовании системы DVM программисту предоставляются следующие возможности спецификации параллельного выполнения программы:

• Распределения элементов массивов между процессорами системы.

• Распределение витков циклов между процессорами.

• Спецификация параллельно выполняющихся секций программы (параллелизм задач).

• Организация эффективного доступа удаленным данным.

• Организация эффективного выполнения редукционных операций.

Существуют следующие возможности повышения эффективности DVM программ:

• Использование групповых асинхронных взаимодействий процессоров (одновременное выполнение нескольких редукций для нескольких массивов).

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

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

• DVM программа динамически настраивается на параметры приложения, т.е. на количество и размер массивов данных

В состав системы DVM входят следующие компоненты:

• Компилятор Фортран-DVM

• Компилятор Си-DVM

• Библиотека Lib-DVM

• DVM-отладчик

• Предиктор (предсказатель производительности)

• Анализатор производительности DVM-программы

Библиотека Lib-DVM поддерживает выполнение DVM-программы, используя коммуникационные системы MPI и PVM.

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

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

Пример DVM-программы. Решение системы линейных уравнений методом Гаусса.

PROGRAMM GAUSS

C решение системы А*X + B

PARAMETER (N-100)

REAL A(N, N+1), X(N)

C A: матрица коэффициентов (N,N+1)

C вектор правых частей в N +1 столбцах

С X: вектор неизвестных

* DVM$ DISTRIBUTE A(BLOCK, *)

* DVM$ ALIGN X(I) WITH A(I,N+1)

С инициализация

* DVM$ PARALLEL(I) ON A(I,*)

DO 100 I=1,N

DO 100 J=1 ,N +1

IF (I.EQ.N+1) THEN

A(I,J)=2.0

ELSEIF (J.EQ.N+1) THEN

A(I,J)=0.0

ENDIF

ENDIF

100 CONTINUE

C исключение

DO 1 I=1,N

C I-я строка матрицы А буфферизутся

С перед обработкой I-го столбца уравнения

С ссылки A(I,K), A(I,J) заменяются ссылками на буфер

*DVM$ PARALLEL(Y) ON A(J,*), REMOTE_ACCESS(A(I,:))

DO 5 J=I+1,N

DO 5 K=I+1 ,N +1

A(I,K)=A(I,K)- A (I,J)+A(I,K)/A(I,I)

5 CONTINUE

1 CONTINUE

C сначала вычисляется X(N)

X(N) = A(N,N+1) / A(N,N)

C нахождение X(N-1), X(N-2) обратной подстановкой

DO 6 J=N-1,1,-1

C (J+1) элемент массива X буферизуется перед обработкой J-го уровня

*DVM$ PARALLEL(Y) ON A(I,*), REMOTE_ACCESS(X(J+1))

DO 7 I=1,J

A(I,N+1) = A(I,N+1) - A(I,=J+1) * X(J+1)

7 CONTINUE

8 CONTINUE

PRINT *,X

END

страница 2 / 75