Параллельные вычисления

• Название: Параллельные вычисления
• Дата: 06.05.2019
• Размер: 1.75 Mb.
• Имя файла: [Bakanov_V.M.]_Parallelnuee_vuechisleniya__Uchebno(z-lib.org).pdf
• Тип: Учебное пособие; #76301
• страница: 10 из 16

огущих быть выполненными независимо друг от друга и то- чек (моментов) в программе, в которых необходима синхронизация выполне- ния этих блоков (для ввода или обмена данными). Только для простейших алгоритмов эта задача может быть выполнена ‘в уме’, в большинстве случае требуется (достаточно сложный) анализ структуры алгоритма. В некоторых случаях целесообразно провести эквивалентные преобразования алгоритма
(замена данного алгоритма – или его части – на алгоритм, гарантирующий получение такого же конечного результата на всех наборах входных данных, причем желательно без снижения точности расчетов).
3.1 Представление алгоритма графовой структурой
Принято и удобно представлять алгоритм в виде графовой структуры.
Граф G стандартно обозначается G=(V,E), где V – множество вершин
(vertex), E – множество дуг (edge), дуга между вершинами i и j обозначается как e(i,j). В общем случае вершины графа соответствуют некоторым дейст-
виям программы, а дуги – отношениям между этими действиями.
Простейший граф такого рода описывает информационные зависимости
алгоритма (вершины этого графа соответствуют отдельным операциям ал- горитма, наличие дуги между вершинами i,j говорит о необходимости при выполнении операции j наличия аргументов (операндов), выработанных опе- рацией i; в случае независимости выполнения операций i и j дуга между вер- шинами отсутствует). Такой граф называют графом алгоритма (вычисли-
тельной моделью ‘операторы - операнды’), [1,3]. Даже при отсутствии ус- ловных операторов (что маловероятно) число выполненных операций (а сле- довательно, и общее число вершин графа и, соответственно, число дуг) зави- сит от размеров входных данных, т.е. граф алгоритма (ГА) является пара-

- 69 -
метризованным по размеру входных данных. Ацикличность ГА следует из невозможности определения любой величины в алгоритме через саму себя.
ГА также является ориентированным (все дуги направлены). Различают де-
терминированный ГА (программа не содержит условных операторов) и не-
детерминированный ГА (в противном случае). Для недерминированного ГА не существует взаимно-однозначного соответствия между операциями опи- сывающей его программы и вершинами графа при всех наборах входных па- раметрах; поэтому чаще всего рассматриваются детерминированные алго- ритмы. Не имеющие ни одной входящей или выходящей дуги вершины ГА называются входными или выходными вершинами соответственно. Построе- ние ГА не является трудоемкой операцией (чего нельзя сказать о процедурах анализа графа) – любой компилятор (интерпретатор) строит (явно или неяв- но) его при анализе каждого выражения языка программирования высокого уровня
Последовательность вычислений (один из вариантов) нахождения корней полного квадратного уравнения
0
c bx x
a
2
=
+
+
в виде a
2
ac
4
b b
2 2
,
1
x
−
±
−
=
приведена в табл.4 и требует 11 операций высокоуровневого языка програм- мирования (сложение, вычитание, умножение, деление, изменение знака, вычисление квадратного корня и т.п.).
Таблица 4 — Последовательность вычисления значений корней полного квадратного уравнения.
№ оператора
Действие
Примечание
Ввод a, b, c
Операции ввода не нумеруются
0 a2
←
2
×
a а2 – рабочая переменная
1 a4
←
4
×
a а4 – рабочая переменная
2 b_neg
←
neg(b) b_neg
– рабочая переменная, neg – операция изменение знака (‘унар-ный минус’)
3 bb
←
b
×
b bb
– рабочая переменная
4 ac4
←
a4
×
c aс4 – рабочая переменная
5 p_sqr
←
bb-a4 p_sqr
– рабочая переменная
6 sq
←
sqrt(p_sqr) sq
– рабочая переменная, sqrt – операция вычисления квадратного корня
7 w1
←
b_neg+sq w1
– рабочая переменная
8 w2
←
b_neg-sq w2
– рабочая переменная
9 root_1
←
w1/a2 root_1
– первый корень уравнения
10 root_1
←
w2/a2 root_2
– второй корень уравнения

- 70 -
При последовательном вычислении граф алгоритма (рис.19) полностью копирует последовательность действий табл.4; имеет 3 входных вершины
(соответствующие вводу коэффициентов a,b и c), две выходные вершины
(вычисленные корни x
1
и x
2
исходного уравнения) и 11 вершин, соответст- вующих операторам алгоритма.
Рисунок 19 — Граф алгоритма (зависимость ‘операции - операнды’) нахождения корней полного квадратного уравнения для последовательного выполнения.
Одним из (неэкономных по использованию памяти при использовании) представлений графа G=(V,E) является квадратная матрицей смежности
(нумерация строк и столбцов соответствует нумерации операторов, булева
‘1’ в (i,j)-той ячейке соответствует наличию дуги e(i,j), ‘0’ – отсутствию
оной):
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
⎡
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
0 0
0 0
0 1
1 0
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
0 0
0 0
0 0
1 1
0 0
0 0
0 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
1 1
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
0 0
1 1
0 0
0 0
0 0
0 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
При начальном анализе время выполнения всех операций принимается одинаковым, более точный анализ требует информации о трудоемкости каж- дой операции (при этом вершинам и дугам графа могут быть сопоставлены веса – величины, пропорциональные трудоемкостям операций вычисления и обмена данными соответственно).
Тот же граф представлен на рис.20 в иной форме, причем одновременно проведен анализ внутренней структуры алгоритма с целью поиска групп операторов, могущих быть выполненными параллельно. Такой граф пред-

- 71 - ставляет
ярусно-
параллельную
форму
(ЯПФ) алгоритма, при- чем количество ярусов определяет длину кри-
тического пути.
В ярусы собираются операторы, требующие для своего выполнения значений
(операндов), которые вычисляются
только на предыдущих
ярусах (всего на рис.20 выделено 6 ярусов); т.о. параллельное выполне- ние данного алгоритма требует последователь- ного 6-разового выпол- нения блоков парал- лельных операций (в каждом из которых за- пускаются 4,1,1,1,2,2 независимых процесса соответственно, причем ярусы 2,3,4 вырождают- ся в последовательное выполнение алгоритма).
Граф рис.20 позволяет уже сделать некие конкретные выводы о альтерна- тивах распараллеливания. Заметим, что ярус 1 перегружен операциями (3 умножения и 1 изменение знака), часть из них (кроме операции 2) можно пе- ренести на более нижние ярусы (варианты: операцию 4 на ярус 2, операцию 3 на ярусы 2,3 или 4, операцию 1 на ярусы 2,3,4 или 5); конкретный вариант должен выбираться исходя из дополнительных данных (например, время вы- полнения конкретных операций, число задействованных вычислительных модулей, минимизация времени обменов данными между модулями).
Выявление этих ярусов представляет собой один из уровней анализа
внутренней структуры алгоритма. Нижеприведена упрощенная последова- тельность действий по выявлению могущих выполняться параллельно ярусов графа алгоритма (вдумчивый читатель самостоятельно произведет необходи- мые уточнения и оптимизацию):
Рисунок 20 — Граф алгоритма (зависимость ‘операции - операнды’) для нахождения корней полного квадратного уравнения с группировкой операций по ярусам

- 72 -
Пункт
Действие
Примечание
а)
Задать список вершин, зависящих только
от входных данных
; занести его в список
list_1
Начальные данные для работы алгоритма задаются вручную б)
Найти вершины, зав
и
симые по дугам от вершин, входящих только в список list_1 и предыдущие списки (если они есть); занести их в список list_2
Наиболее трудоемкий пункт, тре- бующий просмотра матрицы смежности для каждого элемента списка в)
Если список list_2 не пуст, скопировать его в list_1 и идти к пункту б); иначе за- кончить работу
Цикл по ярусам, пока
о
ные могут быть выявлены
Вариант (с целью достижения наибольшей прозрачности оптимизации не производилось) реализации алгоритма на языке С приведен ниже (исходные данные - квадратная булева матрица смежности
MS[ ][ ]
размерности
N_MS
, одномерные целочисленные массивы
LIST_1[ ]
и
LIST_2[ ]
длиной
N_L1
и
N_L2
соответственно):
001 do {
// по ярусам сколько их будет выявлено
002
N_L2=0;
003 for (ii=0; ii// цикл по вершинам в списке LIST_1 004 i_ii=LIST_1[ii];
// i_ii – номер вершины из списка LIST_1 005 for (j=0; j// цикл по столбцам MS (j – номер вершины,
// к которой направлено дуга)
006 if (MS[i_ii][j]) {
// нашли какую-то дугу i_ii
→
j
007 j1 = j;
// запомнили вершину, к которой идет дуга от i_ii
008 for (i1=0; i1// по строками MS = исходящим вершинам
009 if (MS[i1][j1]) {
// нашли какую-то дугу i1
→
j1 010 flag=false;
011 for (k=0; k// цикл по списку LIST_1 012 if (LIST_1[k] == i1)
// если вершина j1 входит в LIST_1…
013 flag=true;
// при flag=true вершина i1 входит в список LIST_1 014
}
// конец блока if (MS[i1][j1])
015 if (flag)
// …если i1 входит в список LIST_1 016
LIST_2[N_L2++] = j1;
// добавить вершину j1 в список LIST_2 017
}
// конец блока if (MS[i_ii][j])
018
}
// конец блока for (ii=0; ii019 for(i=0; i// копируем LIST_2 в LIST_1 020
LIST_1[i] = LIST_2[i];
021
N_L1 = N_L2;
022
} while (N_L2);
// …пока список LIST_2 не пуст
Время t
j
выполнения операций каждого яруса определяется временем ис- полнения наиболее длительной операции из расположенных на данном ярусе
(
)
ji
max(
j
t
t
=
, где j – номер яруса, i – номер оператора в данном ярусе). При планирования выполнения параллельной программы необходимо учитывать ограниченность по числу процессоров (
Pmax
P
≤
), поэтому может быть вы- годно объединение двух и более быстровыполняемых операторов для после- довательного исполнения в рамках одного яруса. Как показано ниже в теку- щем разделе, подобная задача по трудоемкости относится к NP-полным зада-

- 73 - чам (точное решение невозможно получить за разумное время). Однако и в этом случае получение решения, значимо (в несколько раз) повышающее производительность, является ценным и должно быть использовано.
Усложняет проблему необходимость учета конвейерности, присущей практически каждому современному процессору, причем в разной степени
(разработчиками заявлено, что процессор IBM Power5 способен выполнять за такт четыре операции с плавающей точкой, процессоры AMD Opteron и Intel
Xeon EM64T - две операции с плавающей точкой за такт (*).
Конечно, в реальности распараллеливание на уровне отдельных операто- ров полезно в лучшем случае для параллельных компьютеров с общей памя- тью (SMP-систем, многоядерных процессоров); рациональнее в роли отдель- ного оператора рассматривать группу операторов, могущую выполняться по- следовательно без обмена данными с другими (возможно, параллельно вы- полняющимися) подобными группами команд (гранула, зерно распараллели-
вания, см. подраздел 1.3). Однако выявить гранулы (зерна) параллелизма
(вручную или автоматически) очень непросто.
Одним из эмпирических методов проектирования алгоритмов наименьшей
высоты (с минимальным числом ярусов) является процесс сдваивания. Для задачи вычисления произведений n чисел
a
a
a
n
,
2 1
алгоритм последователь- ного вычисления для n=8 представляется так (по работе [1]): исходные данные:
a
a
a
a
a
a
a
a
8 7
6 5
4 3
2 1
ярус 1:
a
a
2
1
×
ярус 2:
a
a
a
3
2
1
)
(
×
ярус 3:
a
a
a
a
(
4
3
2
1
)
×
ярус 4:
a
a
a
a
a
5
4
3
2
1
)
(
×
ярус 5:
a
a
a
a
a
a
(
6
5
4
3
2
1
)
×
ярус 6:
a
a
a
a
a
a
a
7
6
5
4
3
2
1
)
(
×
ярус 7:
a
a
a
a
a
a
a
a
8
7
6
5
4
3
2
1
)
(
×
Высота этой схемы (число ярусов) равна 7, ширина (число операций на каждом ярусе) равна 1. Алгоритм может быть реализован на многопроцес- сорной вычислительной системе, но все кроме одного процессоры будут про- стаивать.
Использование другого алгоритма решения той же задачи (используется свойство ассоциативности умножения) приводит к схеме: исходные данные:
a
a
a
a
a
a
a
a
8 7
6 5
4 3
2 1
*
Антонов А.С. Далеко ли до пика? //Журнал ‘Открытые системы’, № 06, 2006.

- 74 - ярус 1:
)
(
)
(
)
(
)
(
a
a
a
a
a
a
a
a
8
7
6
5
4
3
2
1
×
×
×
×
ярус 2:
)
(
)
(
)
(
)
(
a
a
a
a
a
a
a
a
8
7
6
5
4
3
2
1
×
×
ярус 3:
)
(
)
(
a
a
a
a
a
a
a
a
8
7
6
5
4
3
2
1
×
Высота такой схемы равна 3, ширина – те же самые 4. Для произвольного n
(в этом случае высота равна
)
(
n
log
ceil
2
такой алгоритм реализуется на
ceil(n/2) процессорах (но загрузка процессоров бинарно уменьшается от яру- са к ярусу). Процесс сдваивания (известен и применяется также процесс ре-
куррентного сдваивания) позволяет проектировать алгоритмы минимальной высоты для любой ассоциативной (сочетательной) операции, но ширина по- лученного алгоритма чрезмерна (на первых ярусах).
Для рассмотренных алгоритмов размер гранулы (определенный трудоем- костью выполнения операций высокоуровневого языка программирования) столь мизерен, что его применение оправдано только для SMP-систем (мно- гопроцессорных вычислительных систем с общей памятью); эффективное распараллеливание в МВС с локальной памятью требуют использование гра-
нул параллелизма намного большего размера.
Подобный подход к проектированию параллельных схем выполнения ал- горитмов является изящным, однако абстрагирование от числа процессоров и параметров коммуникационной среды конкретной вычислительной систе- мы делает его практическую применимость весьма ограниченной (напр., для рассмотренного примера при
103
≈
n
на первом ярусе необходимо задейство- вать 500 процессоров, а на последнем – всего 2!). Подход, основанный на иг- норировании архитектуры МВС и количественных параметров ее компо- нентов, получил название концепции неограниченного параллелизма.
При операторном подходе в любой программе различают два типа дейст- вия – преобразователи (осуществляют переработку информации, напр., операторы присваивания) и распознаватели (определяют последовательность срабатывания преобразователей при работе программы, напр., условные опе- раторы, переключатели и др.). Всего имеются четыре основные (традицион- ные) модели (см. табл.5) представления алгоритмов в виде графов (
*
):
Таблица 5 — Основные модели графового представления алгоритмов.
№№
Название
Вершины графа
Д
у
ги графа
Примечание
1
Граф управ- ления
Соответствуют экземплярам опе- раторов- преобразователей
Передача управления
(наличие направленной дуги между вершинами соответствует выпол-
Граф не зависит от входных дан- ных и создается непосредственно
*
Ершов А.П. Современное состояние теории схем управления. // Проблемы кибернетики,
-М.: 1973, № 27, c.87
÷
110.

- 75 - или распознавате- лей нению операторов не- посредственно один за другим) по тексту про- граммы
2
Информаци- онный граф
Cоответствуют экземплярам только преобразо- вателей
Информационные связи между операторами
(это и есть ранее рас-
смотренный граф ал-
горитма
).
То же самое
3
Операционно- логическая история
Cоответствуют каждому срабаты- ванию (оно необя- зательно является единственным) каждого операто- ра
Cоответствуют переда- чам управления
Граф зависит от входных данных и требует для по- строения отсле- живания выпол- нения всех опера- торов
4
История реа- лизации
Соответствуют каждому срабаты- ванию оператора- преобразователя
Соответствуют переда- чам информации
То же самое
На самом деле традиционные графы зависимостей устроены излишне сложно - в каждую вершину входит слишком большое число дуг, к тому же зависящее от значений внешних переменных. Для таких графов трудно полу- чить приемлемое аналитическое представление и поэтому с их помощью трудно решать сложные содержательные задачи.
В НИВЦ МГУ ряд лет для изучения структуры алгоритмов используют т.н. мини-
мальные графы зависимостей
[1]. Эти графы являются подграфами традиционных гра- фов зависимостей, однако принципиально отличаются от последних тем, что в каждую вершину такого графа входит лишь конечное число д