Формы параллелизма

Параллелизм — это возможность одновременного выполнения более од-

ной арифметико-логической операции или программной ветви. Возможность

параллельного выполнения этих операций определяется правилом Рассела, ко-

торое состоит в следующем:

Программные объекты 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

Здесь одновременное выполнение дает неопределенный результат.

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

Наиболее общей формой представления этих зависимостей является ин-

формационный граф задачи (ИГ). Пример ИГ, описывающего логику конкрет-

ной задачи, точнее порядок выполнения операций в задаче

В своей первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.

Более определенной формой представления параллелизма является яруснопараллельная форма (ЯПФ): алгоритм вычислений представляется в виде яру

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

друга, в первый ярус — операторы, зависящие только от нулевого яруса, во

второй — от первого яруса и т. д.

Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: b i — ширина i -го яруса; B — ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из b i, 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 задается ЯПФ

Ширина параллелизма первого яруса этой ЯПФ (первый такт) сильно зависит от числа операций, включаемых в состав ЯПФ. Так, в примере для l 1 = 4 параллелизм первого такта равен двум, для l 1 = 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).

Возможны операции и большей размерности, чем векторные: над матрицами и многомерными массивами. Однако в параллельные ЯВУ включаются только векторные операции (сложение, умножение, сравнение и т. д.), потому что они носят универсальный характер, тогда как операции более высокого уровня специфичны.

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

Рассмотрим решение линейной системы уравнений: