Графовые модели параллельных вычислений
Графом называется геометрическая фигура, состоящая из вершин (точек, узлов) и линий между ними, которые называются дугами (ребрами) графа.
Формализованную модель предметной области решаемой задачи можно представить в виде ориентированного графа, вершины которого – выполняемые операции, а дуги – информационные связи между операциями. Решение задачи сводится к нахождению вершины (или множества вершин) и (или) ребра (множества ребер), удовлетворяющим определенным условиям.
Одной из основных задач параллельных вычислений является анализ особенностей графов алгоритмов с целью определения возможности их распараллеливания и выявления параллельных ветвей.
В качестве примера построим граф ПФ алгоритма, представленного в табл.3.1. Его вершинами являются операции, осуществляемые на соответствующих ярусах (шагах алгоритма). Входными его вершинами являются исходные данные аi (i =1…8), а дугами – информационные связи между операциями (вершинами).
Ярусы Исходные данные
а
1 а2 а3 а4 а5 а6 а7 а8
0
1
2
3
Рис. 3.1. Граф параллельного алгоритма табл.3.1
На рис.3.1 четко прослеживаются две ветви независимых параллельных вычислений (на первых двух шагах) с исходными данными (а1, а2, а, а4) и (а5, а6, а7, а8) соответственно.
Матрицы инциденций и смежности
Графовые модели параллельных алгоритмов в памяти ПВМ обычно представляют в виде двух матричных форм, к которым относятся:
матрицы инциденций;
матрицы смежности.
Прямоугольная матрица A [m, n] c элементами aij называется матрицей инциденций графа параллельного алгоритма, если ее элементы удовлетворяют условиям:
+1, если j -е ребро выходит из i -й вершины;
aij = -1, если j -е ребро входит в i -ю вершину;
0 - в других случаях.
В каждом столбце матрицы инциденций лишь два элемента отличны от нуля и равны +1 и -1.
Квадратная матрица В [n, n] c элементами bij называется матрицей смежности графа параллельного алгоритма, если ее элементы удовлетворяют условиям:
bij = 1, если из i -й вершины в j -ю вершину идет ребро;
bij = 0, если из i -й вершины в j -ю вершину не идет ребро.
Ненулевые элементы матрицы смежности равны единице, а все остальные элементы равны нулю.
В качестве примера рассмотрим помеченный циклический ориентированный граф, представленный на рис.3.2.
Рис.3.2.
Циклический граф
Для указанного графа матрицы инциденций и смежности будут иметь вид:
Табл.
3.2. Матрица инциденций
Табл.
3.3. Матрица смежности
-
В
е
р
ш
и
н
ы
Ребра
В
е
р
ш
и
н
ы
Вершины
1
2
3
4
5
6
1
2
3
4
5
6
1
1
0
0
-1
0
0
1
0
1
0
0
0
0
2
-1
1
0
0
0
0
2
0
0
1
0
0
0
3
0
-1
1
0
0
1
3
0
0
0
1
0
1
4
0
0
-1
0
0
0
4
0
0
0
0
0
0
5
0
0
0
1
-1
0
5
1
0
0
0
0
0
6
0
0
0
0
1
-1
6
0
0
0
0
1
0
Списочное представление матричных моделей
Как видно из таблиц 3.2 и 3.3, матрицы инциденций и смежности имеют в своем составе большое число нулей. Чтобы не загружать память ПВМ нулевыми элементами, матрицы инциденций и смежности графовых моделей параллельных алгоритмов представляют в виде списков инциденций и смежности. На рис.3.4 и 3.5 приведен возможный вариант списочного представления матриц инциденций и смежности.
Вершины
Вершины
1
2
3
4
5
6
1
2
3
4
5
6
1
-1
-2
-3
4
5
2
3
4
0
1
5
-4
2
3
-5
-6
6
6
Вершины
Ребра
Рис.3.4. Списки
инциденций
Рис.3.5. Списки
смежности
Порядок выполнения работы
Расчетно-графическая часть
3.1. Построить параллельную форму алгоритма решения задачи перемножения матриц А и В на 8-процессорной ПВМ, используя ненулевые символьные элементы результирующей матрицы С (см. п.1.5."Лабораторной работы №1").
3.2. Разработать блок-схему (описание) алгоритма построения параллельной формы алгоритма параллельных вычислений.
3.3. Определить основные характеристики полученного алгоритма параллельных вычислений.
3.4. Построить ориентированный граф алгоритма параллельных вычислений.
3.5. Представить полученный граф параллельных вычислений в виде списков инциденций и смежности, не содержащих нулевых элементов.