36 Вопрос. Эквивалентные преобразования программ. Преобразования циклов (перестановка, распределение).

У эквивалентных программ должны быть изоморфные графы алгоритмов.

Перестановка циклов.

for (i=0; i<n; i++)

for (j=0;j<n;j++)

a[i,j]=a[i,j]+a[i,j-1]

for (j=0; j<n; j++)

for (i=0;i<n;i++)

a[i,j]=a[i,j]+a[i,j-1]

Данные циклы эквивалентны с точки зрения конечного результата

Распределение циклов.

for (i=0,i<n;++i) {

a[i]=a[i-1]+b;

c[i]=a[i]+c[i]+e;

}

for (i=0,i<n;++i)

a[i]=a[i-1]+b;

for (i=0,i<n;++i)

c[i]=a[i]+c[i]+e;

37 Вопрос. Виды параллелизма

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

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

1. Конечный

Количество независимых ветвей строго? При любых значениях входных данных.(Компьютеры, опирающиеся на машинные команды, суперскалярные комп.)

2. Массовый (опирается на независимость отдельных срабатываний) Важен на практике

For (i=0, i<n) a[i]=b[i]+c

• Координатный здесь можно сразу просто сказать, что внешний цикл по i можно распараллелить - видно, что "существенно" лишь изменение переменной j (след шаг по j зависит от предыдущего) for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=A[i][j-1]/2

• Скошенный: A[i][j]=(A[i-1][j]+A[i][j-1])/2 зависимость по i и по j от предыдуших шагов по тем же переменным. Если нарисовать граф алгоритма для данного случая, то будет видно, что вершины, лежащие на "диагоналях", будут информационно независимы. минус скошенного параллелизма: для распараллеливания сперва надо преписать циклы: внешний - перебор ярусов, внутртенний - перебор вершин на ярусе

38 вопрос. Ярусно-параллельная форма графа алгоритма, высота, ширина. Каноническая

ЯПФ.

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

мультиграф. Верно и обратное. Если задан ориентированный ациклический мультиграф,

то его всегда можно рассматривать как граф некоторого алгоритма. Для этого каждой

вершине нужно поставить в соответствие любую однозначную операцию, имеющую

столько аргументов, сколько дуг входит в вершину. Поэтому между алгоритмами и

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

Утверждение 4.1

Пусть задан ориентированный ациклический граф, имеющий n вершин. Суще-

ствует число s < n, для которого все вершины графа можно так пометить одним из

индексов 1, 2, ..., s, что если дуга из вершины с индексом i идет в вершину с индексом j, то

i<j.

Выберем в графе любое число вершин, не имеющих предшествующих, и пометим

их индексом 1. Удалим из графа помеченные вершины и инцидентные им дуги.

Оставшийся граф также является ациклическим. Выберем в нем любое число вершин, не

имеющих предшествующих, и пометим их индексом 2. Продолжая этот процесс, в конце

концов, исчерпаем весь граф. Так как при каждом шаге помечается не менее одной

вершины, то число различных индексов не превышает числа вершин графа.

Отсюда следует, что никакие две вершины с одним и тем же индексом не связаны

дугой. Минимальное число индексов, которым можно пометить все вершины графа, на 1

больше длины его критического пути. И, наконец, для любого целого числа s, не

превосходящего общего числа вершин, но большего длины критического пути,

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

Граф, размеченный в соответствии с утверждением 4.1, называется строгой

параллельной формой графа. Если в параллельной форме некоторая вершина помечена

индексом k, то это означает, что длины всех путей, оканчивающихся в данной вершине,

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

путей, оканчивающихся в вершине с индексом k, равна k-1. Для этой параллельной формы

число используемых индексов на 1 больше длины критического пути графа. Среди

подобных параллельных форм существует такая, в которой все входные вершины нахо-

дятся в группе с одним индексом, равным 1. Эта строгая параллельная форма называется

канонической. Для заданного графа его каноническая параллельная форма единственна.

Группа вершин, имеющих одинаковые индексы, называется ярусом параллельной формы,

а число вершин в группе — шириной яруса. Число ярусов в параллельной форме

называется высотой параллельной формы, а максимальная ширина ярусов — ее шириной. Параллельная форма минимальной высоты называется максимальной.