Формы параллелизма
Параллелизм— это возможность одновременного выполнения более од-
ной арифметико-логической операции или программной ветви. Возможность
параллельного выполнения этих операций определяется правилом Рассела, ко-
торое состоит в следующем:
Программные объекты A и B (команды, операторы, программы) являются
независимыми и могут выполняться параллельно, если выполняется следующее
условие:
(InB OutA)(InA OutB) (OutA OutB) = Ø, (1.1)
где In(A) — набор входных, а Out(A) — набор выходных переменных объекта
A. Если условие (1.1) не выполняется, то между A и B существует зависимость
и они не могут выполняться параллельно.
Если условие (1.1) нарушается в первом терме, то такая зависимость назы
вается прямой. Приведем пример:
A: R = R1 + R2
B: Z = R + C
Здесь операторы A и B не могут выполняться одновременно, так как результат A является операндом B.
Если условие нарушено во втором терме, то такая зависимость называется обратной:
A: R = R1 + R2
B: R1 = C1 + C2
Здесь операторы A и B не могут выполняться одновременно, так как выполнение B вызывает изменение операнда в A.
Если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной:
A: R = R1 + R2
B: R = C1 + C2
Здесь одновременное выполнение дает неопределенный результат.
Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей.
Наиболее общей формой представления этих зависимостей является ин-
формационный граф задачи (ИГ). Пример ИГ, описывающего логику конкрет-
ной задачи, точнее порядок выполнения операций в задаче
В своей первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.
Более определенной формой представления параллелизма является яруснопараллельная форма (ЯПФ): алгоритм вычислений представляется в виде яру
сов, причем в нулевой ярус входят операторы (ветви), не зависящие друг от
друга, в первый ярус — операторы, зависящие только от нулевого яруса, во
второй — от первого яруса и т. д.
Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: bi — ширина i-го яруса; B — ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из bi, i = 1, 2, ...); li — длина яруса (время операций) и L длина графа; ε — коэффициент заполнения ярусов; θ — коэффициент разброса указанных параметров и т. д.
Главной задачей настоящего издания является изучение связи между клас
сами задач и классами параллельных ЭВМ. Форма параллелизма обычно достаточно просто характеризует некоторый класс прикладных задач и предъявляет
определенные требования к структуре, необходимой для решения этого класса
задач параллельной ЭВМ.
Изучение ряда алгоритмов и программ показало, что можно выделить сле
дующие основные формы параллелизма:
• Мелкозернистый параллелизм (он же параллелизм смежных операций или скалярный параллелизм).
• Крупнозернистый параллелизм, который включает: векторный паралле-
лизм и параллелизм независимых ветвей..
Мелкозернистый параллелизм (Fine Grain)
При исполнении программы регулярно встречаются ситуации, когда исходные данные для i-й операции вырабатываются заранее, например, при выпол
нении (i - 2)-й или (i - 3)-й операции. Тогда при соответствующем построении
вычислительной системы можно совместить во времени выполнение i-й опера-
ции с выполнением (i - 1)-й, (i - 2)-й, ... операций. В таком понимании скаляр-
ный параллелизм похож на параллелизм независимых ветвей, однако они очень
отличаются длиной ветвей и требуют разных вычислительных систем.
Рассмотрим пример. Пусть имеется программа для расчета ширины запрещенной зоны транзистора, и в этой программе есть участок — определение
энергии примесей по формуле
Тогда последовательная программа для вычисления E будет такой:
F1 = M * Q ** 4* P ** 2
F2 = 8 * E0 ** 2* E ** 2 * H** 2
E = F1/F2
Здесь имеется параллелизм, но при записи на Фортране или Ассемблере у нас нет возможности явно отразить его. Явное представление параллелизма для вычисления E задается ЯПФ
Ширина параллелизма первого яруса этой ЯПФ (первый такт) сильно зависит от числа операций, включаемых в состав ЯПФ. Так, в примере для l1 = 4 параллелизм первого такта равен двум, для l1 = 12 параллелизм равен пяти.
Поскольку это параллелизм очень коротких ветвей и с помощью операторов
FORK и JOIN описан быть не может (вся программа будет состоять в основ
ном из этих операторов), данный вид параллелизма должен автоматически вы-
являться аппаратурой ЭВМ в процессе выполнения машинной программы.
|
Для скалярного параллелизма часто используют термин мелкозернистый
параллелизм (МЗП), в отличие от крупнозернистого параллелизма (КЗП), к ко-
торому относят векторный параллелизм и параллелизм независимых ветвей.
Крупнозернистый параллелизм (coarse grain)
Векторный параллелизм. Наиболее распространенной в обработке структур данных является векторная операция (естественный параллелизм). Вектор— одномерный массив, который образуется из многомерного массива, если один из индексов не фиксирован и пробегает все значения в диапазоне его изменения. В параллельных языках этот индекс обычно обозначается знаком *.
Пусть, например, A, B, C — двумерные массивы. Рассмотрим следующий цикл:
DO 1 I = 1,N
1 C(I,J) = A(I,J) + B(I,J)
Нетрудно видеть, что при фиксированном J операции сложения для всех I можно выполнять параллельно, поскольку ЯПФ этого цикла имеет один ярус. По существу этот цикл соответствует сложению столбца J матриц А и В с записью результата в столбец J матрицы С. Этот цикл на параллельном яэыке записывается в виде такой векторной операции:
C (*, j) = A (*, j) + B (*, j).
Возможны операции и большей размерности, чем векторные: над матрицами и многомерными массивами. Однако в параллельные ЯВУ включаются только векторные операции (сложение, умножение, сравнение и т. д.), потому что они носят универсальный характер, тогда как операции более высокого уровня специфичны.
Области применения векторных операций над массивами обширны: цифровая обработка цифровая обработка сигналов (цифровые фильтры), механика, моделирование сплошных сред, метеорология, оптимизация, задачи движения и т.д.
Рассмотрим решение линейной системы уравнений:
Для решения таких систем уравнений при положительно определенной матрице коэффициентов используется метод простой итерации:
Пусть C(N,N) — матрица коэффициентов ci,j системы уравнений; D (N) —
вектор d1, d2, ..., dn; XK(N) — вектор (в исходный момент хранит
начальное приближение); XK1(N) — вектор ; ε — заданная по-
грешность вычислений. Тогда программа для параллельной ЭВМ может выгля-
деть следующим образом:
DIMENSION C(N,N), D(N), XK1(N), XK(N)
XK(*) = начальные значения
XK1(*) = D(*)
4 DO 1 I = 1,N
1 XK1(*) = XK1(*) + C(*,I)*XK(I)
IF (ABS(XK1(*)-XK(*))-ε) 2,2,3
3 XK(*) = XK1(*)
GO TO 4
2 Вывод XK1(*)
STOP
В этой программе многократно использована параллельная обработка эле
ментов векторов (практически во всех строках программы). Цикл по I соответ-
ствует перебору столбцов матрицы С, которые выступают в качестве векторов