Параллельное программирование

Введение

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

1. Ограничение снизу – ограничение времени срабатывания элементов (100 пс).

2. Ограниченная скорость распространения электромагнитных сигналов по соединительным проводам схемы.

3. Повышение степени интеграции приводит к необходимости мер по отводу тепла.

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

Методы распараллеливания используются как аппаратные, так и программные.

С некоторого момента, стоимость растет быстрее производительности.

Классификация Флинна.

Флинн предложил классифицировать все существующие ВС следующим образом: соотнести потоки команд и потоки данных в ВС и выделил 4 типа ВС:

SISD

MISD

SIMD

MIMD

Проблемы параллельного программирования:

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

• Оценка эффективности параллельных алгоритмов. Существуют специальные программы, которые на каждом этапе предсказывают возможную эффективность.

• Существуют проблемы синхронизации и проблемы взаимных блокировок.

Параллельные алгоритмы (ПА).

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

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

Каждая группа – ярус ПФ.

Общее число ярусов называется высотой параллельной формы.

Максимальное число операций в ярусе называется шириной параллельной формы.

Теоретически такой алгоритм может быть реализован на параллельной ВС, за время, пропорциональное высоте параллельной формы.

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

ПРИМЕР: Пусть требуется выполнить следующее выражение: (AB+CD)(EF+GH)

Данные: A B C D E F G H

Ярус1: AB CD EF GH 4оп

Ярус2: AB+CD EF+GH 2оп

Ярус3: (AB+CD)(EF+GH) 1оп

Основная характеристика ПФ: коэффициент ускорения – это общее число операций в последовательном алгоритме / число ярусов.

В нашем примере K_y=7/3=2,33.

Для этого же примера можно предложить и другую параллельную форму.

Данные: A B C D E F G H

Ярус1: AB CD 2оп

Ярус2: EF GH 2оп

Ярус3: AB+CD EF+GH 2оп

Ярус4: (AB+CD)(EF+GH) 1оп

Здесь K_у=7/4=1,75

Данные: A B C D E F G H

Ярус1: AB CD 2оп

Ярус2: AB+CD EF 2оп

Ярус3: GH 1оп

Ярус4: EF+GH 1оп

Ярус5: (AB+CD)(EF+GH) 1оп

Здесь K_у=7/5=1,4

Особенности параллельного алгоритма (ПА).

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

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

13. Устойчивость ПА в общем случае хуже устойчивости соответствующих последовательных.

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

Поиск мах. ПФ является трудной задачей, поэтому для оценки качества ПА используют следующий критерий: если при вычислении некоторого выражения используются операции, использующие не более Р аргументов, то справедливо соотношение: S ≥ log_pn, где S – высота ПФ, n- количество обработанных параллельно данных (размерность).

Построение параллельного алгоритма.

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

Концепция «Неограниченного параллелизма».

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

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

Точность выполнения операций так же не учитывается.

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

Применение этой концепции включает следующие этапы:

• Расщепление исходной задачи на большие независимые подзадачи.

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

• Дальнейшее рекурсивное расщепление подзадач до тех пор, пока не будут получены типовые математические задачи.

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

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

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

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

Методы преобразования последовательных алгоритмов в параллельную форму.

Любой последовательный алгоритм можно представить в виде совокупности участков 3 типов:

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

• Выражения (в т.ч. рекуррентные соотношения);

• Циклические участки (циклы).

Наибольших выигрыш получается при распараллеливании циклических участков.

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

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

Факторами резко снижающим эффективность таких систем являются:

- команды условных и безусловных переходов,

- информационная зависимость операторов,

- косвенная адресация.

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

Рассмотрим i-тый участок памяти. Все переменные, которые изменяются на этом учаcтке можно отнести к одной из четырех категорий:

• Только считываемые переменные W_i

• Только записываемые переменные X_i

• Сначала считываемые, а потом записываемые Y_i

• Сначала записываемые, а потом считываемые Z_i

С учетом таких обозначений для любой пары операторов P1 и P2 на этом участке должны выполняться следующие соотношения:

(W1Y1Z1)(X2Y2Z2)=0

(X1Y1Z1)(W2Y2Z2)=0

Если эти условия выполняются, то операторы независимы и могут быть выполнены параллельно.

Алгоритм

Для рассмотрения одного из возможных алгоритмов распараллеливания введем следуюшие обозначения:

I_i – входные данные для i-того оператора, т.е. переменные в правой части оператора присваивания

Oi –выходные данные, т.е. переменные в левой части оператора присваивания.

Для независимости двух операторов i-го и j-го необходимо выполнения следующих соотношений:

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

П РИМЕР: Пусть исходный линейный участок задан орграфом

Есть матрица смежности для него

C

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0
4	0	0	1	0	0	0	0	0
5	0	1	0	0	0	0	0	0
6	0	0	0	0	1	0	0	0
7	0	0	0	1	0	1	0	0
8	0	0	0	0	0	0	1	0

Матрица передачи управления

L

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0

Очевидно, что для распараллеливания необходимы еще входные/выходные данные. Они так же представляются булевскими матрицами m на n, где n строк представляют операторы, а m столбцов - идентификаторы переменных. В нашем случае 5 переменных, поэтому матрица 8 строк и 5 столбцов

I

	1	2	3	4	5
1	0	0	0	0	0
2	0	1	0	0	0
3	1	0	0	0	0
4	0	1	0	0	0
5	0	0	0	0	1
6	0	1	0	0	0
7	0	0	1	1	0
8	0	0	0	0	1

O

	1	2	3	4	5
1	0	1	0	0	0
2	0	0	0	0	0
3	0	0	1	0	0
4	0	0	0	1	0
5	0	0	1	0	0
6	0	0	0	1	0
7	0	0	0	0	1
8	0	0	0	0	0

В этих матрицах соответствующий элемент равен единице в том случае если переменная с номером j является входной для оператора I. Для матрицы O, соответственно, та же единица соответствует выходной.

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

Для построения матрицы C_p сначала строится матрица последовательности выполнения операторов для исходного участка, матрица P.

P

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0
4	1	1	1	0	0	0	0	0
5	1	1	0	0	0	0	0	0
6	1	1	0	0	1	0	0	0
7	1	1	1	1	1	1	0	0
8	1	1	1	1	1	1	1	0

В ней отображен порядок следования операторов.

Для построения матрицы C_p необходимо простроить две матрицы P_p (матрица неполного параллелизма) и L_p (матрица параллельной логики).

Алгоритм построения матрицы C_P.

6. Стоятся вспомогательные матрицы P_p=P (матрица неполного параллелизма) и L_p=L (матрица параллельной логики)

7. Для всех пар (i, j), для которых элемент матрицы P равен единице («1»), вычисляется функция

IO_i^j = (I_j  O_i) (I_i  O_j) (O_i  O_j)

Если IO_i^j = 0, то операторы i и j – независимы, т.е их можно выполнять параллельно или сохранить последовательность выполнения, для этого случая соответствующий элемент матрицы P устанавливается в нуль (P_Pi^j = 0).

8. Для сохранения логических связей вычисляется элементы

L_Pi = L_i L_j,

где:

Li – i-тая строка матрицы L_p

L_j – j – итая строка матрицы L

В результате логическая связь, ведущая к оператору j будет идти и к оператору i.

9. Строится вспомогательная матрица C_p’= P_P  ( ), в которой сохраняются только прямые связи длиной 1.

10. Находим искомую матрицу C_p = L_p  C_p’.

Данные матрицы имеют следующий вид:

P_p

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0
7	0	0	1	1	1	1	0	0
8	0	0	0	0	0	0	1	0

L_p

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0
4	0	1	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0
6	0	1	0	0	0	0	0	0
7	0	0	0	0	0	1	0	0
8	0	0	0	0	0	0	0	0

C_p

	1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0	0
2	1	0	0	0	0	0	0	0
3	0	1	0	0	0	0	0	0
4	0	1	0	0	0	0	0	0
5	0	1	0	0	0	0	0	0
6	0	1	0	0	0	0	0	0
7	0	0	1	1	1	1	0	0
8	0	0	0	0	0	0	1	0

Недостатки алгоритма.

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

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

ПРИМЕР:

1 A=B+C

2 D=A+E

3 A=X+Y

4 F=A*Z

1 A1=B+C

2 D=A1+E

3 A=X+Y

4 F=A*Z

На этом линейном участке все операторы должны выполнятся строго последовательно, однако если переписать как указано ниже, то пары операторов 1,2 и 3,4 являются независимы и могут выполнятся параллельно.

Виды зависимостей между переменными:

• Информационная;

• Конкуренционная:

• 1 типа;

• 2 типа;

• Транзитивная;

• Логическая;

Распараллеливание выражений.

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

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

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

• Методы, основанные на сравнении старшинства операции.

• Методы, использующие обратную польскую запись.

Сравнение старшинства операций.

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

ПРИМЕР: Пусть требуется вычистить следующее выражение: E = a + b + c * d * e * f + g.

Входная строка	« a+b+c*d*e*f+g »
Результат первого прохода	T1+T2*T3+g, где T1 = (a+b), T2 = (c*d), T3 = (e*f)
Результат второго прохода	« T4+T5 », где T4 = (T2 * T3), T5 = (T1 + g)
Результат третьего прохода	« T6 », где T6 = (T4 + T5)
Выходная строка	(((c*d)*(e*f))+((a+b)+g)))

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

\

Стек пентад:

Уровень	Операция	1операнд	2операнд	Результат
1	+	a	b	T1
1	*	c	d	T2
1	*	e	f	T3
2	*	T2	T3	T4
2	+	T1	g	T5
3	+	T4	T5	T6

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

Метода анализа обратной польской записи.

• Инфиксная запись «a+b»

• Префиксная запись «+ab»

• Постфиксная запись «ab+», она же обратная польская

В этом методе продвигаются по входной строке слева на право до тех пор пока не встречается триада типа: <операнд1><операнд2><операция>. После нахождения такой триады генерируется пентада: <уровень><операция><операнд1><операнд2><результат>, причем уровень равен номеру прохода. Дойдя до конца строки, начинают новый проход, где в качестве операндов используются операнды, незатронутые на предыдущих проходах, а так же промежуточные результаты.

Этот метод не дает в общем случае параллельной формы минимальной высоты.

ПРИМЕР: Пусть требуется вычистить следующее выражение: E = a + b + c * d * e * f + g.

Входная строка:	ab+cd*e*f*g++
Результат первого прохода:	T1T2e*f*g++, где T1=ab+, T2=cd*
Результат второго прохода:	T1T3f*g++, где T3=T2l*
Результат третьего прохода:	T1T4g++, где T4=T3f*
Результат четвертого прохода:	T1T5+, где T5=T4g+
Результат пятого прохода:	T6, где T6=T1T5+
Выходная строка:	(a+b)+((((c*d)*e)*f)+g)

Данный метод часто используется.

Распараллеливание рекурсий.

Р

* В этом методе набор из n процессорных элементов (ПЭ) загружается данными, которые должны суммироваться. Существует возможность сдвига данных таким образом, что значение i-го ПЭ помещается в i+1-й, а 1-й ПЭ заполняется нулевым значением. Данные, выдвигаемые из n-го ПЭ, теряются. Метод каскадных сумм реализуется, как показано на рис.3. Здесь реализован случай n=8. Содержимое ПЭ сдвигается на одну позицию вправо и суммируется с несдвинутой копией. Если этот процесс повторять log2n раз, на каждом ярусе увеличивая сдвиг в два раза, то в результате в несдвинутой копии ПЭ сформируется требуемая последовательность Xi. Если требуется получить только полную сумму (Х8), то достаточно выполнить операции, обведенные кружком. (из лаб. практикума)

екурсия - это последовательность вычислений, при котором значения очередного вычисляемого терма зависит от одного или нескольких ранее вычисленных термов. Под термом понимается результаты вычислений на очередном шаге. Если это значение зависит только от предыдущего терма – то рекурсия 1-го порядка. Исп. при решении систем уравнений, преобразовании матриц и других задач.

Общая линейная рекурсия первого порядка.

X_j = a_jX_j-1+d_j, где j = 1,2,…,n

Частный случай:

X_j = d_k, где j = 1,2,…,n

Рассмотрим традиционную схему вычислений.

ПРИМЕР: n = 8.

0	X1	X2	X3	X4	X5	X6	X7	X8
	d1	d2	d3	d4	d5	d6	d7	d8
	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6	Шаг 7	Шаг 8

В этом алгоритме:

n-1 операция сложения со степенью параллелизма единица, n-1 операция сдвига со степенью параллелизма 1.

Шаги:

1. Сначала n аккумуляторов загружаются исходными данными di.

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

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

В результате на уровне L* = log₂n каждый аккумулятор содержит соответствующую частичную сумму.

В полученном алгоритме log₂n “+” операций сложения со степенью параллелизма n и n-1 операция сдвига (маршрутизации) со степенью параллелизма n. Таким образом, по сравнению с обычной схемой общее кол-во операций сложения увеличивается, общее количество операций сложения выполнены за три шага. Если смещение по индексу выводит соответствующее значение из заданного диапазона, то это значение заполняется нулями. Если этот метод применить для получения конечной суммы элементов, не вычисляя всех частных сумм, то общее число сложений получается таким же, как и при последовательном вычислении, а количество шагов равно трем. (Если этот метод выполняется методом конечных сумм, то выполняются операции, обведенные в кружочки и число операций равно 7. Метод каскадных сумм хорошо работает, если n – степень 2.)

Этот алгоритм может быть реализован фрагментом программы на языке Fortran:

X=D

DO 1 L=1, LOG2(N)

X=X+SHIFTR(X, 2**(L-1))

1 CONTINUE

где, X и D – векторы из n элементов, «+» - параллельное сложение, SHIFTR – векторная функция, которая помещает копию вектора X со смещением на указное количество позиций (2**(L-1), т.е. 2 в степени (L-1)) вправо, в вектор SHIFTR.

Если вернуться к общей линейной рекурсии первого порядка, то при последовательном вычислении требуется 2n арифметических операций со степенью параллелизма «1» и n сдвигов со степенью параллелизма 1.

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

X=D

DO 1 L, LOG 2(N)

X=A*SHIFTR (X, 2**(L-1)) + X

A=A*SHIFTR (A, 2**(L-1))

1

где X, D и A – векторы.

Предложенный метод каскадных сумм может быть использован для вычисления нелинейных рекурсий первого порядка. Например, n!=(n-1)!*n – вот рекурсия первого порядка.

Для циклической редукции существуют прикидки времени выполнения при больших n: нужно выполнить ≈3log₂n со степенью параллелизма n² и 2 операциями сдвига со степенью параллелизма n.

Распараллеливание циклов

Существует несколько методов:

• Метод гиперплоскостей;

• Метод координат;

• Метод параллелепипедов;

• Метод пирамид.

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

Метод гиперплоскостей

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

Метод предполагает использование сложного математического аппарата. Лучше использовать в системах MIMD.

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

Пусть дан гнездовой циклический алгоритм вида:

DO 99 I=1,L

DO 99 J=2,M

DO 99 K=2,N

V(J,K)=(V(J+1,K)+V(J-1,K)+V(J,K-1)+V(J,K+1))*0,25