WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«Программирование на последовательном языке программирования и последующее автоматическое распараллеливание Преимущества • применять опыт программирования, накопленный в ...»

Автоматическое

распараллеливание

последовательных программ

Степени параллелизма. Статическое и динамическое

распараллеливание последовательных программ

Как писать код для параллельного

вычисления?

Программирование на последовательном языке

программирования и последующее автоматическое

распараллеливание

Преимущества

• применять опыт программирования, накопленный в течение

многолетней эксплуатации традиционных последовательных ЭВМ;

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

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

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

Четыре стадии решения задачи на параллельной вычислительной системе:

• выбор подходящего алгоритма (стадия А);

• выражение алгоритма на подходящем языке высокого уровня (ЯВУ) – написание программы (стадия Я);

• компиляция программы в объектный код (стадия О);

• выполнение программы (стадия П).

Степень параллелизма • ||А - степень параллелизма алгоритма, • ||Я - степень параллелизма программы, • || О - степень параллелизма объектного кода, • || П - степень параллелизма вычислительного процесса.

А Я О П Идеальный вариант сохранения параллелизма Потеря и восстановление параллелизма при использовании последовательного языка программирования и распараллеливающего, в частности, векторизующего компилятора Использование проблемно-ориентированного (непроцедурного) языка программирования Использование параллельного ЯВУ, ориентированного на архитектуру данной параллельной вычислительной системы Распараллеливание ациклических участков Алгоритм распараллеливания ациклических участков программы

• построение графа зависимостей по данным между операторами программы;

• построение ярусно-параллельной формы (ЯПФ) программы;

• составление по ЯПФ параллельной программы;

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

Построение графа зависимостей по данным Граф зависимостей по данным G между операторами программы (Data Dependence Graph, DDG) строится на основе информационной, логической и конкуренционной зависимости между операторами программы.

Информационная зависимость между операторами программы Оператор B зависит от оператора A информационно, если оператор "вырабатывает" некоторую переменную x, которую использует оператор B.

Другими словами, оператор B зависит от оператора A информационно, если:

1) существует путь от входного оператора программы, проходящий через операторы A, B,

2) оператор A является последним перед B оператором этого пути, "вырабатывающий" значение переменной X, которое используется оператором B.

Логическая зависимость между операторами программы

Оператор B зависит от оператора A логически, если:

1) существует путь от входного оператора программы до оператора A,

2) оператор A является "распознавателем", решающим будет или нет выполняться оператор B.

Конкуренционная зависимость между операторами программы

Операторы A, B зависят друг от друга конкуренционно, если:

1) существуют пути от входного оператора программы как до оператора A, так и до оператора B

2) операторы A и B "вырабатывают" одну и ту же переменную x.

Пример Пользователь вводит относительные адреса x, y начала и конца массива. Известно, что переменная, имеющее наибольшее значение соответствует концу массива, а переменная, имеющая наименьшее значение, – началу массива. Требуется распечатать массив, а также нижнюю и верхнюю его границы.

Программа A ввод (x, y);

B l := x;

C h := y;

D v := c+x;

E z := c+y;

P если xy то F иначе G;

F h := x; l := y;

G печать от min (z, v) до max (z, v);

H печать (l, h);

Граф зависимостей Построение ярусно-параллельной формы программы

• На первый ярус ЯПФ заносятся все операторы, в которые не идут стрелки графа зависимостей G;

• Если построено k ярусов, то в (k+1)-й ярус заносятся все те операторы, которые имеют входящие стрелки только от первых k ярусов.

Ярусно-параллельная форма для программы примера 1

1. Входящие стрелки отсутствуют только у оператора A. Поэтому на первый ярус ЯПФ помещаем только этот оператор.

2. Входящие стрелки только от операторов 1-го яруса имеют операторы B, C, D, E, P. Поэтому помещаем их на второй ярус.

3. Входящие стрелки только от операторов 1-го и 2-го ярусов имеют операторы F, G. Помещаем их на третий ярус.

4. Наконец, входящие стрелки только от операторов 1-го, 2-го и 3го ярусов имеет только оператор H. Помещаем этот оператор на четвертый ярус.

Ярусно-параллельная форма для программы примера 1 Уровень готовности операторов Ярусы ЯПФ устанавливают между операторами отношение предшествования — к моменту начала вычислений на (к+1)-м ярусе должны быть закончены вычисления на к-м ярусе.

Меры ярусно-параллельных форм

• Высотой ЯПФ называется количество ее ярусов.

• Шириной яруса ЯПФ называется количество операторов на этом ярусе.

• Шириной ЯПФ называется максимальная из ширин ярусов данной ЯПФ.

• ЯПФ данного алгоритма, имеющая минимальную высоту, называется минимальной ЯПФ или максимально-параллельной ЯПФ.

• Ширина минимальной ЯПФ называется шириной алгоритма, а ее высота – высотой алгоритма.

Особенности распараллеливание выражений Выражение – это ациклический процесс

В выражениях не всегда указан порядок действий:

a*b*c = (a*b)*c = a*(b*c) Задача распараллеливания выражений ставится следующим образом: построить алгоритм, который каждому выражению ставит в соответствие эквивалентное ему с минимальной высотой ЯПФ.

Три закона эквивалентности

• ассоциативность a * (b * c) = (a * b) * c,

• коммутативность a * b = b * a,

• дистрибутивность a * (b + c) = a * b + a * c.

Пример Пример Распараллеливание циклических фрагментов программ Основная работа, которую обычно производит ЭВМ, это обработка циклов и других повторяющихся участков программ.

Пространство итераций Положим, что параметрами цикла данного гнезда циклов являются i1=1,r1; i2=1,r2;.....;in=1,rn. Тогда пространством итераций данного гнезда циклов называется множество n-мерных целочисленных векторов I={i1=1,r1; i2=1,r2;.....;in=1,rn}. В терминах пространства итераций задача распараллеливания цикла ставится как задача разбиения множества I на подмножества I1, I2,...,Is такие, что вычисления тела цикла в каждом из них могут быть выполнены одновременно (с сохранением информационных связей исходного цикла, естественно). Оси координат пространства итераций цикла соответствуют параметрам цикла i1, i2,...,in.

Пример FOR i1=1,r1 DO FOR i2=1,r2 DO …..

FOR in=1,rn DO T(i1, i2, … in), где T – тело цикла, тогда Пространство итерации гнезда циклов = 1, 2, …, | 1, 1, Таким образом Задача распараллеливания гнезда циклов ставится как задача разбиения множества I на подмножества 1, 2, …, такие, что вычисления тела цикла T в каждом из них могут быть выполнены одновременно (с сохранением информационных связей исходного цикла, естественно) Распараллеливание циклов производится распараллеливающим компилятором Общая структура распараллеливающего компилятора

–  –  –

Генерация Распараллеливание Оценка качества Генерация машинного параллельной Синтаксический анализ циклов распараллеливания кода программы Этап синтаксического анализа

• производится синтаксический анализ последовательной программы;

• проверяется выполнение некоторых ограничений на тела циклов (линейность индексных выражений, отсутствие операторов и обращений к подпрограммам и т.п.);

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

Этап распараллеливания циклов

• проверяется выполнение всех необходимых ограничений на тела циклов;

• производится выбор метода распараллеливания;

• для вложенных циклов анализ производится, начиная с внутренних циклов.

• для циклов, которые не распараллеливаются, компилятором выдается информация о конкретных причинах невозможности распараллеливания.

Этап оценки качества распараллеливания

• оценивается степень распараллеливания каждого из циклов;

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

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

На этапе генерации параллельной программы генерируется программа на параллельном ЯВУ.

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

Методы распараллеливания циклов (в зависимости от 1, 2, …, )

–  –  –

метод метод метод пирамид параллелепипедов гиперплоскостей Ограничений на операторы тела цикла при распараллеливании

• тело цикла не содержит условных и безусловных переходов вне тела;

• внутри тела цикла передача управления осуществляется только вперед;

• тело цикла не содержит операторов ввода-вывода и обращений к подпрограммам;

• все индексные выражения линейны, т.е. отсутствуют индексы вида X(I*J*K);

• отсутствует косвенная адресация вида X(N(I));

• индексы не изменяются в теле цикла;

• выполнено условие Рассела – в теле цикла не используется простая неиндексированная переменная раньше, чем этой переменной в теле цикла присваивается некоторое значение Пример выполнения условия Рассела FOR i=1,N S:=S+X(i) Метод параллелепипедов Метод параллелепипедов распараллеливания циклов целесообразно использовать в случае, когда пространство итераций цикла представляет собой, вообще говоря, многомерный параллелепипед со сторонами, параллельными осям координат пространства итераций цикла. Идея метода состоит в разбиении указанного параллелепипеда плоскостями, параллельными координатным плоскостям, на совокупность параллелепипедов, итерации в каждом из которых можно производить параллельно.

Пример FOR i =2,5 FOR j = 2,4 X(i,j)=X(i-1,j-1)**2 Разбивка пространства итераций на параллелепипеды Вариант а) parbegin X(2,2):= X(1,1)**2;

X(2,3):= X(1,2)**2;

X(2,4):= X(1,3)**2 parend;

parbegin X(3,2):= X(2,1)**2;

X(3,3):= X(2,2)**2;

X(3,4):= X(2,3)**2 parend;

……………………………….

Вариант б) parbegin X(2,2):= X(1,1)**2;

X(3,2):= X(2,1)**2;

X(4,2):= X(3,1)**2;

X(5,2):= X(4,1)**2 parend;

parbegin X(2,3):= X(1,2)**2;

X(3,3):= X(2,2)**2;

X(4,3):= X(3,2)**2;

X(5,3):= X(4,2)**2 parend;

..............

Метод гиперплоскостей Идея метода гиперплоскостей распараллеливания циклов состоит в отыскании в пространстве итераций I такого семейства гиперплоскостей, чтобы любые две лежащие в одной из этих гиперплоскостей точки p1, p2 были информационно и конкуренционно не связаны.

Пример FOR i=1, l DO FOR j=2, m DO FOR k=2, n DO x(j,k):= f(x(j + 1, k),x(j, k + 1),x(j - 1, k),x( j, k - 1));

Здесь пространство итераций (является трехмерным), p1=(i1,j1,k1), Особенности В рассматриваемой программе в каждой точке p=(i,j,k) вычисление значения x(p) производится с использование значений x в 4-х соседних точках. Причем соседи x(j-1,k), x(k,k-1) точки x(j,k), которые ближе к началу координат, лежат в плоскости i, а соседи этой точки x(j+1,k), x(k,k+1), которые расположены дальше от начала координат, лежат в плоскости i-1. Другими словами, при вычислении x(j,k) при i=i* значения x(j-1,k), x(k,k-1), уже вычислены при этом i, а значения x(j+1,k), x(k,k+1), — еще не вычислены, т.е.

являются "старыми", вычислены при i=i*-1.

Особенности Например, при вычислении x(3,3) при i=2 используются точки a=x(4,3), b=x(3,4), которые еще не пересчитаны при данном I (т.е. лежат на плоскости i=1), а также точки c=x(2,3), d=x(3,2), которые уже пересчитаны при данном i (т.е. лежат в плоскости i=1).

Пространство итераций – плоскости, проходящие через прямые + = + = 2 где const=3,4,5… Метод пирамид Метод пирамид распараллеливания циклов ориентирован на многопроцессорные вычислительные системы, в которых синхронизация и обмен данными требуют больших накладных расходов (слабосвязанные МВС). Целью распараллеливания при этом является формирование полностью независимых друг от друга ветвей.

Схема алгоритма формирования ветвей

1. В цикле выбираются все результирующие итерации, т.е.

итерации, "вырабатывающие" переменные, не используемые далее в теле цикла. Каждая такая итерация послужит основой для формирования отдельной параллельной ветви и будет последней итерацией в этой ветви.

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

Пример FOR j=1, n DO FOR k=2, 5 DO x(j, k):= x(j + 1, k) + x(j, k - 1));

Итерации j k x(j, k) 1 2 x(1,2) = x(2,2) + x(1,1) 1 3 x(1,3) = x(2,3) + x(1,2) 1 4 x(1,4) = x(2,4) + x(1,3) 1 5 x(1,5) = x(2,5) + x(1,4) 2 2 x(2,2) = x(3,2) + x(1,1) 2 3 x(2,3) = x(3,3) + x(1,2) 2 4 x(2,4) = x(3,4) + x(1,3) 2 5 x(2,5) = x(3,5) + x(1,4).........

Организайия ветвей

• При вычислении x(1,2) последней итераций является итерация x(1,2) = x(2,2) + x(1,1).

Поэтому в методе пирамид первая ветвь имеет вид x(1,2) = x(2,2) + x(1,1)

• При вычислении x(1,3) последней итераций является итерация x(1,3) = x(2,3) + x(1,2), в которой используется ранее вычисленная переменная x(1,2). Поэтому вторая ветвь имеет вид x(1,3) = x(2,3) + x(2,2) + x(1,1)

• Аналогично, для третьей ветви x(1,4) = x(2,4) + x(2,3) + x(2,2) + x(1,1)

• и четвертой ветви x(1,5) = x(2,5) + x(2,4) + x(2,3) + x(2,2) + x(1,1)

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



Похожие работы:

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ Филиал в г.Самаре Кафедра математических и естестве...»

«Министерство образования Республики Беларусь БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра электронной техники и технологии Г.М. Шахлевич, А.А. Костюкевич, В.Ф. Холенков, Г.В....»

«Глава 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 3.1. Задача математического программирования В предыдущей главе мы познакомились с линейным программированием. Приведенные примеры показывают, что многие практические проблемы можно формулировать математически как задачу линейного программирования. Однако им...»

«УДК 519.6 ЗАДАЧА ШТЕЙНЕРА ДЛЯ АЦИКЛИЧЕСКОГО ГРАФА Ильченко А. В. Таврический национальный университет им. В.И. Вернадского факультет математики и информатики пр-т Вернадского, 4, г. Симф...»

«Министерство образования и науки Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Северный (Арктический) федеральный университет имени M B. Ломоносова» СМ. Потапенко Задачи регионального содержания 1 как фактор активизации познаватель...»

«Московский Государственный Университет им. М.В. Ломоносова Факультет Вычислительной Математики и Кибернетики Кафедра Математических Методов Прогнозирования Метод статистической верификации регрессионных моделей, основанный на перестановочных тестах. Дипломная работа выполнил Дзыба Дмитрий Сергеевич Научн...»

«Сравнительный анализ качества вероятностных и возможностных моделей измерительно-вычислительных преобразователей Д. А. Балакин, Т. В. Матвеева, Ю. П. Пытьев, О. В. Фаломкина Рассмотрены компьютерное модел...»

«ГОСУДАРСТВЕННЫЙ НАУЧНЫЙ ЦЕНТР РОССИЙСКОЙ ФЕДЕРАЦИИ ИНСТИТУТ ФИЗИКИ ВЫСОКИХ ЭНЕРГИЙ ИФВЭ 201224 ОУК В.П. Воеводин Эволюция понятия и показателей надёжности вычислительных систем Протвино 2012 УДК 004.41 М-24 Аннотация Воеводин В.П. Эволюция понятия и показателей надёж...»





















 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

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