Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Лекции по параллельному программированию - файл 1.doc


Лекции по параллельному программированию
скачать (9032 kb.)

Доступные файлы (1):

1.doc9032kb.19.11.2011 16:03скачать

содержание
Загрузка...

1.doc

Реклама MarketGid:
Загрузка...
1 Модели параллелизма

Модель передачи сообщений (МПС). Каждый процесс имеет собственное локальное адресное пространство. Обработка общих данных и синхронизация осуществляется посредством передачи сообщений (пример - стандарт MPI). Это основная модель для вычислительных кластеров.

MPI (Message Passing Interface) - стандартизованный интерфейс для построения программ по модели обмена сообщениями. MPI - наиболее широко используемый и динамично развивающийся интерфейс в своем классе. Существуют бесплатные и коммерческие реализации для большинства суперкомпьютерных платформ.

Достоинства:

  • Возможность использования в языках Фортран, Си, Си++

  • Возможность совмещения обменов сообщениями и вычислений

  • Несколько режимов передачи сообщений

  • Широкий набор коллективных операций

  • Широкий набор редукционных операций

  • Удобные средства именования адресатов сообщений

  • Возможность задания типа передаваемой информации

Недостатки:

  • Слишком сложен для прикладного программиста

(программирование на низком уровне)

Модель с общей памятью (МОП). Процессы разделяют общее адресное пространство, отсутствуют ограничения на использование общих данных, предполагается явная спецификация общих данных и упорядочение доступа к ним с помощью средств синхронизации. Логически независимые нити (потоки) вычислений определяются на уровне функциональных задач или витков цикла (пример - OpenMP).

OpenMP - это интерфейс прикладной программы (API), расширяющий последовательный язык программирования (Фортран, Си, Си++) набором директив распараллеливания. Стандарт параллельного программирования для систем с общей памятью (SMP-систем).

OpenMP реализует параллелизм по управлению:

Программа начинает свое выполнение как один процесс (главная нить), пока не встретится параллельная область программы (ограничивается директивами PARALLEL и END PARALLEL). При входе в параллельную область главная нить порождает некоторое число подчиненных ей нитей, образуя группу нитей. Все операторы программы, находящиеся в параллельной конструкции, выполняются всеми нитями группы параллельно, пока не произойдет выход из параллельной области или не встретится одна из конструкций распределения работ (DO, SECTIONS или SINGLE). При выходе из параллельной конструкции все порожденные ранее нити сливаются с главной, которая продолжает выполняться далее последовательно.

Достоинства:

  • Реализация возможностей систем с общей памятью

  • Явное и полное задание параллелизма программистом

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

  • Единственность разрабатываемого кода – отсутствие необходимости поддерживать последовательный и параллельный вариант программы (директивы OpenMP игнорируются обычными компиляторами)

  • Гибкий механизм контроля над поведением параллельного приложения

  • Поддержка наиболее распространенных языков программирования

Недостатки:

  • Ограничения, характеризуемые областью применения

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

^ HPF (High Performance Fortran) - расширения языка Фортран-90.

HPF-2 - расширения языка Фортран-95. 

Часть расширений реализована в виде функций и операторов языка, а часть - в виде директив компилятору (которые являются комментариями языка Фортран).

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

Распределение данных производится в два этапа:

  • с помощью директивы ALIGN задается соответствие между взаимным расположением элементов нескольких массивов

  • с помощью директивы DISTRIBUTE группа массивов отображается на решетку процессоров.

В HPF вся работа по распределению данных возлагается на программиста.

Модель DVM

реализует два уровня параллелизма:

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

  • ^ Параллелизм задач реализуется распределением данных и независимых вычислений на решетку процессоров.

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

Типы директив:

  • Распределения данных

  • Распределение вычислений

  • Спецификация удаленных данных


  1. Основные архитектуры ВС для параллельных вычислений. Классификация Флина.


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

Все ВС можно разделить на 4 категории:

1) SISD – од. К, од. Д



2) SIMD - од. К, мн. Д-х



3) MISD - мн. К, од. Д-х



4) MIMD - мн. Поток К. и Д-х
3. Понятие параллельной формы. Представление параллельного алгоритма в виде граф-схемы.

Любая ВС м.б. представлена как совокупность функ-но независимых обрабатывающих устр-в, кот-е осущ-т обработку параллельно. Алгоритм д.б. представлен в виде последовательности групп операций, причем все операциив 1-ой группе независимы и м.б. выполнены на любом обрабатыв-м устр-ве. Каждая группа зависит либо от исх. Данных, либо от рез-тов выполнения предыдущей операции.Группы операции выполняются последовательно. Такой алгоритм – параллельная форма.

Каждая группа наз-ся ярусом. Общее число ярусов наз-ся высотой, МАХ число операций в ярусе- ширина формы.

Такая парал-ная форма м.б. реализована на ВС за Т пропорциональная высоте этой формы. Среди всех возм-х парал-х форм одного алгоритма всегда есть одна или несколько форм мин. Высоты. Такие формы назыв. Мах. Они опр-ют мин. Возможное время вып-я алгоритма.



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

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

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

Применение КНП вкдючает след-е этапы:

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

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

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

Если получ. Подзадачи однотипные, то выгоднее реализовать всю задачу на SIMD.

Такой подход- крупноблочное распараллеливание.


5.Область применения, особенности и недостатки метода гиперплоскостей.

Пример:(можно не писать )

Пусть задан след циклич алг-м:

DO 99 I=1,L

DO 99 J=2,M

DO 99 K=2,N

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

99 continue

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

Со второго шага можно делать параллельный счет .

Найдем некую плоскость параллельного счета.

2I+J+K=const, рассек прос-во операндов
Для всех точек принадлеж этой плоскости можно осущ-ть независимый параллел счет тела цикла.Введем тновые переменные:

_ _ _

Пусть есть система: 1)I = 2I+J+K 2)J=I 3)K=K =>получим

_ _ _ _

1) I=J 2)J=I-2J-K 3 )K=K => получим в итоге


Программа записана на паралл ФОРТРАНЕ ,ГДЕ CONC FOR ALL-это паралл независимое выполнение тела цикла для всех точек удовлет указ ограничениям.
В резул-те таких переобразований исходное трехмер прос-во операций сворачивается в одномерное прос-во

В ИСх прогр-ме общ число итераций=L*(M-1)*(N-1)

В полученной 2L+M+N-5

^ Общий случай: ^n-обознач степени

Пусть дан цикл
Do α I^1=l^1,U^1

……………..

Do α I^n=l^n,U^n

Тело цикла

Α continue
Для использ метода необходимо:

-Тело цикла не содержало операторов I/O

-нет Передачи управления вне цикла

-Обращ к процед и функц,которые могут изменять данные в теле цикла
Индексные выражения в операторах исходного тела цикла должны иметь вид:

l^I +m^I пример:I+1


i-ая i-ая const

переменая
В рез-те преобраз. Исх цикл преобраз-ся в

Для нахождения урав гиперпл-ти ищется отображение целочисленных наборов индексных переменных, учасвствующих в цикле в виде

n

J[(I^1,….,I^n)]=(сумма aj1Ij,….,сумма ajnI0)

J=1

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

-Все использ-ия переменных должны следовать за генерацией этих перемен-х

-любое появл переем в теле цикла наз вхождением переем в тело цикла

-есл опер-р появл в лев части опер присв то вхождение наз-ся генерацией,если в правой то использованием.
Для нахождения искомого отображения реш-ся задача целочисленного программир-я.В рез-те нах-ся коэф-ты ajn
I1=a11I+a12J

J1=a21I+a22J подбираем коэф-ты
Достоинства:строгая формализованность (использ-е в трансляторах для автоматич распаралеривания)

Недостатки:сложность алгоритмов вывода уравнений гиперплоск-ти
6.Параметры граф-схемы параллельного алгоритма.Метод гипер плоскостей.

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

Алгоритмы работающие с такой вс представ-ся в виде послед групп операций.

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

Каждая группа зависит от исх данных или от рез пред группы.

Кажд группа наз ярусом паралл формы.

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

Максим число операций в ярусе-ширина.

И см бил 5.


^ Общий случай: ^n-обознач степени

Пусть дан цикл
Do α I^1=l^1,U^1

……………..

Do α I^n=l^n,U^n

Тело цикла

Α continue
Для использ метода необходимо:

-Тело цикла не содержало операторов I/O

-нет Передачи управления вне цикла

-Обращ к процед и функц,которые могут изменять данные в теле цикла
Индексные выражения в операторах исходного тела цикла должны иметь вид:

l^I +m^I пример:I+1


i-ая i-ая const

переменая
В рез-те преобраз. Исх цикл преобраз-ся в

Для нахождения урав гиперпл-ти ищется отображение целочисленных наборов индексных переменных, учасвствующих в цикле в виде n

J[(I^1,….,I^n)]=(сумма aj1Ij,….,сумма ajnI0)

J=1

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

-Все использ-ия переменных должны следовать за генерацией этих перемен-х

-любое появл переем в теле цикла наз вхождением переем в тело цикла

-есл опер-р появл в лев части опер присв то вхождение наз-ся генерацией,если в правой то использованием

Для нахождения искомого отображения реш-ся задача целочисленного программир-я.В рез-те нах-ся коэф-ты ajn

I1=a11I+a12J

J1=a21I+a22J подбираем коэф-ты

Достоинства:строгая формализованность (использ-е в трансляторах для автоматич распаралеривания)

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


  1. Сравнит хар-ки последоват и паралл. алг-мов.

  • По сравнен с соотвеств послед алг-мом, парал-ные могут потреб выполнен “лишних” операц, число к-ых м.б большим

  • Разн ПФ одного исходн алг-ма фактич реализ разн алг-мы и => могут давать различн рез-ты в условн влиянии ошибок округления

  • Устойч-ть паралл алг-ма в общем случае хуже соответст послед.

Уст-ть более менее const при p<=n2

n- порядок матр к-ая обраб-ся

p – число процессоров


  1. Понятие мин пар-ной формы

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

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

Представлен в таком виде алг-м наз-ся пар-ной формой(ПФ)

Кажд группа операц зависит отисх данных либо от рез-тов вып-я пред группы.

Кажд группа-ярус пар-ной формы. Общее число ярусов – высота || формы.

Мах число операц в группе – ширина ПФ

Теоретич такой алг-м м.б реализован на многопроцессорн сист за время пропорц-ое высоте ПФ

Мин пар-ная форма – 1 или неск-ко форм пар-ной формы мин высоты для одног алг-ма.

Такие формы опр-ют мин возможное время вып-я алг-ма

9. Метод координат

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

Рассмотрим пример:

DO 24 I=2,M

DO 24 J=1,N

21 A( I,J ) = B( I,J ) + C( I )

22 C( I ) = B( I+1,J )

23 B( I, J ) = A(I + 1,J)**2

24 CONTINUE

Вычисл. I процесс используется в оп. 22 I+1 проц., что мешает их независ-ой работе.

Поэтому в методе осущ-ся неформальное преобраз-ие в т.ц. (ввод промежут. переменных и поменять местами опер-ры)

DO 24 J=1,N

^ DO 24 SIM FOR ALL I{I: 2 IM}

TEMP ( I ) = A( I+1,J )

21 A( I,J ) = B( I,J ) + C( I )

23 B( I,J) = TEMP ( I )**2

22 C( I ) = B ( I-1, J)

24 CONTINUE
В отлич. от метода гиперплоскостей, исп-ся констр-ия SIM вместо CONC, означающая, что опер-ры тела цикла могут выпол-ся ||-но, но требуется постоянная синхр-ия, т.е. для всех точек простр-ва итераций сначала выполн-ся I-ый опер-р тела цикла, затем след-ий и т.д., и для каждой точки организованно ожидание окончания выполнения опер-ра во всех других точках.

Такая схема вычисл-ий наиб. целесообразна для систем класса SIMD, в к-ых каждый процессорный элем-т выполн-ет одну и ту же опер-ию в любой мом. врем. В примере значение опер-ра с меткой 23, к-ое подсчитано i-ым процессором исп-ся опер-ом с i-1 процессором.

Это обстоят-во мешает их независимой работе.
В методе координат иногда приходится производить неформальные преобразования в теле цикла. В т.ч. вводить новые переменные (TEMP), менять местами опер-ры (23 и 22).

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

Если испол-ть метод гиперпл-ей, то линейные преобразования будут такими:

неI = I + J

неJ = J
M+N–2 итераций (в гиперпл-ях)

N итераций ( в корд. мет.)
+: в методе коорд. нет сложных преобраз-ий в теле цикла;

большее ускорение (в нек-ых случаях)

–: метод не применим для нек-ых исх-ых циклов и преобразования в теле цикла неформальны (выдел. дополн. опер-ов, перестановка опер-ов и др.).

треб-ет пооперат-ой синхр-ии

10. Проблемы параллельной обработки данных

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

2) Разные параллельные формы одного исходного алгоритма фактически реализуют разные алгоритмы в классическом понимании и поэтому могут давать разные результаты в условиях влияния ошибок округления.

3) устойчивость параллельных форм в общем случае хуже соответствующих последовательных.

4) Поиск максимальной параллельной формы – трудная математическая задача.
11.Метод параллелепипедов

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

Рассм. Пример:

D0 2 I=1,15 D0 2I=1,4

X(I)=X(6*I-27) ПОЛУЧАЕТСЯ D0 2 CONC FOR ALL JЄ {4*(I-1)≤J≤min{4I,15}}

^ 2 CONTINUE X(I)=X(6*I-27)

2 CONTINUE
Общая постановка задачи: пусть задано I={I1,I2,…In}

Требуется найти P1,P2,…Pn-ребра параллелепипеда, при которых исходная :

D0 1 I1=1,r1 D0 2 CONC FOR ALL JЄ{1,11}

D0 1 I2=1,r2 D0 2 Kj=1,Pj

.. преобразование в D0 2 I1=K1,r1,P1

D0 1 In=1,rn эквивалентную D0 2 I2=K2,r2,P2

Тело цикла конструкцию след. вида …

continue D0 2 In=Kn,rn,Pn

тело цикла

2 continue

(K-начальные значения параметра цикла, r-конечное, P-шаг)

Искомая конструкция создает для каждого наборa k1,k2,..,kn- паралл. Ветвь, представляющую собой вложенный цикл с шагами исполнения P1,P2,..,Pn. Причем для эквивалентности исходного и полученного циклов достаточно, чтобы в каждом из параллелепипедов не содержалось конкуреционно-зависимых итераций, а также чтобы все использования выполнились после соотвествующих генераций для всех групп параллелепипедов. Чтобы обеспечить минимальное время выполнения(мах распараллеливание) требуется, чтобы объем параллелепипеда был мах. Поиск такого параллелепипеда сводится к задаче целочисленного линейного программирования. Метод предполагает поитерационную синхронизацию, т.е ожидание в каждой ветви выполнения всех итераций одного и того же паралл-да.

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


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

Обмен информацией между отдельным процессами .затруднена синхронизация.

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

Название метода соответствует представл. линейной алгебры, когда при лин независимых индексных выражениях, итерации каждой ветви образуют пирамиду, «натянутую» на вектора, задающие направления зависимостей между итерациями.
В двумерном случае пирамид вырождаетсяв угол между крайними векторами.Если эти вектора обозначить как h(h1,h2) и g(g1,g2), то для исходного цикла, имеющего вид

D0 i1=1,r1

D0 i2=1,r2

Тело цикла

10 continue

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

D0 10 CONC FOR ALL KЄ{1, ..r2}

D0 10 i1=1,..r1

D0 10 i2=max{1,k-[(r1-i1)*g2/g1]},min{r2,k+[(r1-i1)h2/h1}

Тело цикла

10 continue

Поясняющий рисунок:




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

Линейный участок – любая последовательность операторов присваивания и усл/безусловных переходов.

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

  1. Wi-только чтение

  2. Xi-только запись

  3. Yi-сначала чтение затем запись

  4. Zi-сначала запись затем чтение

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

  1. (W1UY1UZ1)∩(X2UY2UZ2)=0

  2. (X1UY1UZ1)∩(W2UY2UZ2)=0

Тогда данные два оператора можно будет выполнять параллельно Ii-входные данные(в правой части) Оi-выходные(переменные в левой части)

Тогда i и j независимы, если Ii∩Oi=0 Ii∩Oj=0 Oi∩Oj=0
14 задача распараллеливания выражений

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

Использование дистрибутивного закона таит в себе некоторые опасности:

^ А(В+С) =АВ+АС

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

Используются 2 метода преобразования исходных выражений:

  1. Метод на основе старшинства операций

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


15. Проблемы параллельной обработки данных

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

2) Разные параллельные формы одного исходного алгоритма фактически реализуют разные алгоритмы в классическом понимании и поэтому могут давать разные результаты в условиях влияния ошибок округления.

3) устойчивость параллельных форм в общем случае хуже соответствующих последовательных.

4) Поиск максимальной параллельной формы – трудная математическая задача.
16. Метод построения дерева свертки, основанный на старшинстве операций

В настоящее время для распараллеливания выражений используют 2 метода преобразования исходного выражения: 1) метод, основанный на старшинстве операций

2) метод, использующий обратную польскую запись

В обоих случаях конечным результатом является набор пентат (совокупность пяти элементов, составляющих единое целое [Замеч.] ) вида (операнд 1, операция, операнд 2, результат, уровень).

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

Пример,

Пусть требуется вычислить следующее выражение:

S = A + B +C * D * E * F + G

1. входная строка: A + B +C * D * E * F + G

2. Результат первого прохода: T1 + T2 * T3 + g, где T1 = A + B

T2 = C * D

T3 = F * E

3. Результат второго прохода:

T4 + T5, где t4 = (T2 * T3)

T5 = (T1 + g)

4. Результитрующая строка:

(((С * D) * (e * f)) + ((a + b) + g)
Паралельная форма для вычисленного выражения называется деревом свертки.

3 ярус +

/ \

2 ярус * +

/ \ / \

1 ярус * * + \

| | | | | | \

исх данные 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

+

t5

t4

t6


18.


17 Распараллеливание рекуррентных соотношений.
Оператор: EQUIVALENCE <список эквивалентных идентификаторов>

Пр: EQUIVALENCE A(1),B(2),C(4)


Вот… Это всё, что было на этот вопрос :’(

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

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

Рассмотрим рекурсию первого порядка:

, где j =1,2,…, n

Рассмотрим частный случай рекурсии:

, где j = 1,2,…,n

Рассмотрим традиционную последовательную схему вычисления данной рекурсии. Пусть n=8.

Кол-во операций: n-1 операций сложения; n-1 операций сдвига

Степень параллелизма = 1






Сначала в аккумуляторы загружаются исходные данные d1-d8, Затем на I-ом уровне производится сдвиг содержимого аккумуляторов на одну позицию вправо и сложение содержимого каждого аккумулятора со сдвинутым значением. На втором уровне значения аккумуляторов сдвигаются на две позиции.

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

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

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

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



Виды записи выражения: -инфиксная запись: a+b; -префиксная +ab; -постфиксная ab+ .

методе анализируется входная строка, представляющая собой обратную польскую запись исходного выражения. Осуществляется движение слева направо по вх. строке до тех пор, пока не встретится триада: (операнд1, операнд2, операция).

Хотя бы одна такая триада содержится в любой обр. польской записи. После нахождения такой триады формируется соответствующая пентада <уровень><операция><оп-д1><оп-д2><результат>

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

Пример: Вх. строка: ab+cd*e*f*g++

Результат I-го прохода: T1T2e*f*g++ , где T1=ab+, T2=cd*
II-го T1T3f*g++, где T3
Ш-го T1T4g++, где T4=T3f*
IV T1T5+, где T5=T4g+




V T6, где T6=T1T5+

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

В настоящее время известны 4 метода распараллеливания циклов:

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

  2. Метод координат

  3. Метод параллелепипедов

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

Строится трёхмерное пространство итераций

2хмерный случай:
Пространство рассекается плоскостями, параллельными координатным осям.



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

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

DO 99 I=1,L

DO 99 J=2,M

DO 99 K=2,N

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

99 CONTINUE

Начиная со второго шага можно осуществлять независимый параллельный счёт.

Методом гиперплоскостей будет найдена плоскость, рассекающая исходное пространство итераций таким образом, что для всех точек, принадлежащих данной плоскости, можно осуществить независимый параллельный счёт (тела)???

Введём новые переменные, линейно зависящие от исходных, следующим образом:

I_1 J_1 K_1 Обратные преобразования

I_1 = I + J + K I = J_1

J_1 = I J=I_1 – 2J_1 – K_1

K_1 = K K=K_1

При таких преобразованиях тело цикла приобретает вид:

DO 99 I=6,2* + M + N

DO 99 CONC FOR ALL(J_1,K_1) Э???

{(J_1,K_1):1<=J_1<=K_1, 2<=I_1-2J_1-K_1<=M, 2<=K_1<=N}

V(I_1-2*J_1-K_1,K_1)=(V(I-2*J_1-K_1+1,K_1)+

+V(I_1-2*J_1-K,K_1+1)+V(I-2*J_1-K_1-1;K_1)+

+V(I_1-2*J_1-K_1,K_1-1)+0,25

99 CONTINUE

Результирующая программа записана на параллельном FORTRAN, где конструкция CONC FOR ALL означает независимое параллельное выполнение тела цикла всех точек пространства итераций, удовлетворяющих ограничениям. В результате таких преобразований трёхмерное пространство итераций сворачивается в одномерное пространство. В исходной программе общее число итераций равно L*(M-1)*(N-1).

В полученной конструкции – 2L+M+N-5. При достаточно больших значениях M и N выигрыш существенен.

+ строгая формализованность, позволяющая использовать метод в трансляторах для автоматического распараллеливания

- сложность алгоритма вывода ур-ний гиперплоскостей

Метод координат.

Рассмотрим пример:
^

DO 24 I=2,M

DO 24 J=1,N


21 A(I,J)=B(I,J)+C(I,J)

22 C(I)=B(I+1,J)**2???

24 CONTINUE

DO 24 J=1,N

DO 24 SIM FOR ALL I Э??? {I=2<=I<= M}

TEMP (I)=A(I+1,J)

22 A(I,J)=B(I,J)+C(I)

23 B(I,J)=TEMP(I)**2

21 C(I)=B(I-1,J)

24 CONTINUE

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

Такая схема вычислений наиболее целесообразна для систем класса SIMD, в которых каждый процессорный элемент выполняет одну и ту же операцию в любой момент времени. В примере значение оператора с меткой 23, которое подсчитано i-тым процессором, используется оператором 22 с I+1ым процессором. Это обстоятельство мешает их независимой работе.

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

+ в методе координат нет сложных преобразований в теле цикла

- метод неприменим для некоторых исходных циклов и преобразования в теле цикла неформальны
^

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


В этом методе подмножества независимо выполняемых операций ищутся в форме п/у параллелепипедов.

Общая постановка задачи: пусть задано исходное пространство итераций некоторого гнездового циклического алгоритма. I = {I1, I2, … ,In}

Требуется найти такие целые числа P1, Р2, … , Рn , называемые рёбрами параллелепипеда, при которых исходная конструкция (1) преобразуется в эквивалентную вида (2).



Искомая конструкция создаёт для каждого набора К1, К2, … , Кn параллельную ветвь, представляющую собой вложенный цикл с шагом исполнения Р1, Р2, … , Рn. Причём для эквивалентности исходного и полученного циклов достаточно, чтобы в каждом из параллелепипедов не содержалось конкурентно зависимых итераций, а также чтобы все использования выполнялись после соответствующих генераций для всех групп параллелепипедов. Для того, чтобы обеспечить мин. Время выполнения, требуется, чтобы объём соответствующего параллелепипеда был максимальным. Метод предполагает поститерационную синхронизацию, т.е. ожидание выполнения в каждой ветви.

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

Метод можно применять для простых циклов, а также для циклов с переменными верхними границами.

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

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

В исходном цикле выбираются все результирующие итерации. Каждая ветвь формируется путём включения в неё всех итераций, информац. связ. с уже включёнными в эту ветвь.
^ 20. Распараллеливание рекурсии. Метод каскадных сумм.

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

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

Рассмотрим рекурсию первого порядка:

, где j =1,2,…, n

Рассмотрим частный случай рекурсии:

, где j = 1,2,…,n

Рассмотрим традиционную последовательную схему вычисления данной рекурсии. Пусть n=8.

Кол-во операций: n-1 операций сложения; n-1 операций сдвига

Степень параллелизма = 1





Сначала в аккумуляторы загружаются исходные данные d1-d8, Затем на I-ом уровне производится сдвиг содержимого аккумуляторов на одну позицию вправо и сложение содержимого каждого аккумулятора со сдвинутым значением. На втором уровне значения аккумуляторов сдвигаются на две позиции.

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

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

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

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


Скачать файл (9032 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru