Графовые модели параллельных вычислений. Графы параллельных алгоритмов

Основные понятия теории графов. Графом называется геометрическая фигура, состоящая из вершин (точек, узлов) и линий между ними, которые называются дугами (ребрами) графа. Например:
- граф транспортной сети района: вершины – населенные пункты, дуги – дороги;
- граф производства: участки конвейера и связи между ними.

Понятие "граф" введено Эйлером в 1736 году.

Основные свойства вершин и дуг графа. Основными свойствами вершин и дуг графа являются следующие:
- вершины одной дуги называются смежными;
- дуга с совпадающими смежными вершинами называется петлей;
- две вершины могут иметь несколько дуг;
- дуги с одинаковыми смежными вершинами называются кратнымиили параллельными;

- дуга, представленная прямой, называется ребром;
- дуга, представленная вектором, называется ориентированным ребром;
- ориентированное реброимеет начальную и конечную вершину;
- ребро инцидентно своим вершинам;

- вершины ввода данных не имеют входных дуг;
- вершины вывода данных не имеют выходных дуг;
- число ребер, инцидентных вершине, называется степеньювершины; вершина степени 1 называется висячей, степени 0 –изолированной.

Связь между дугами и вершинами связного графа (см. ниже) определяется известной формулой Эйлера: n – m + l = 2,
где: n –число вершин;
m –число дуг;
l –число односвязных областей.

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

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

г) Простой граф не содержит петель и кратных ребер. Ориентированный граф (орграф) содержит ориентированные ребра. Ациклический (бесконтурный) графне имеетциклов (контуров). Мультиграф содержит кратные ребра. Псевдограф содержит и петли и кратные ребра. Пустой граф не имеет ребер.

д) Граф называется изоморфным, если между множеством его вершин и дуг можно установить однозначное соответствие, сохраняющее смежность и ориентацию. Изоморфные графы отличаются только расположением вершин и начертанием дуг. Установить изоморфизм графов в общем случае довольно трудно.

е) Гомоморфизм (свертка) графа – процесс слияния вершин и соответствующего изменения дуг графа (используется, в частности, в параллельных алгоритмах).
ж) Граф называется решетчатым, если его вершины находятся в узлах целочисленной прямоугольной решетки.
з) Граф называется регулярным, если из каждой его вершины выходит одинаковое число дуг.
и) Граф называется взвешенным, если его ребра и вершины имеют определенные веса.

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

Графы параллельных алгоритмов. Формализованную модель предметной области решаемой задачи можно представить в виде ориентированного графа, вершины которого – выполняемые операции, а дуги – информационные связи между операциями. Решение задачи сводится к нахождению вершины (или множества вершин) и (или) ребра (множества ребер), удовлетворяющим определенным условиям.

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

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

Пример №2. Пусть проекции ребер ориентированного графа не нулевые и направлены в одну сторону. Тогда эти проекции определяют некоторую параллельную форму алгоритма, в которой:
- ярус параллельной формы содержит вершины, которые проектируются в одну точку;
- все вершины одного яруса находятся в гиперплоскости, перпендикулярной к проекциям ребер.

Графы параллельных алгоритмов находят применение при проектировании вновь создаваемых ПВМ или определении архитектуры уже существующих ПВМ. При этом решаются две основные задачи параллельных вычислений.

1) Задача проектирования ПВМ. Дан ориентированный граф, описывающий параллельный алгоритм и указан перечень (спецификация) операций, отождествляемых с его вершинами. Известна номенклатура функциональных устройств (ФУ), могущих выполнять операции параллельного алгоритма.

Необходимо выбрать состав ФУ (в пределах выделенных лимитов), построить ориентированный граф проектируемой ПВМ и выбрать (разработать) программу или множество программ, обеспечивающих реализацию параллельного алгоритма за минимальное время.

2) Задача использования существующей ПВМ. Дан ориентированный граф, описывающий параллельный алгоритм и указан перечень (спецификация) операций, отождествляемых с его вершинами. Дан ориентированный граф, описывающий ПВМ, и указана спецификация ФУ, отождествляемых с его вершинами.

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