Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


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




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

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

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

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

Программные объекты 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 описан быть не может (вся программа будет состоять в основ

ном из этих операторов), данный вид параллелизма должен автоматически вы-

являться аппаратурой ЭВМ в процессе выполнения машинной программы.

 

q

 

 

Для скалярного параллелизма часто используют термин мелкозернистый

параллелизм (МЗП), в отличие от крупнозернистого параллелизма (КЗП), к ко-

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

 

Крупнозернистый параллелизм (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)

вектор d 1, d 2,..., 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 соответ-

ствует перебору столбцов матрицы С, которые выступают в качестве векторов

 





Поделиться с друзьями:


Дата добавления: 2015-01-25; Мы поможем в написании ваших работ!; просмотров: 975 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Так просто быть добрым - нужно только представить себя на месте другого человека прежде, чем начать его судить. © Марлен Дитрих
==> читать все изречения...

2541 - | 2284 -


© 2015-2025 lektsii.org - Контакты - Последнее добавление

Ген: 0.013 с.