Лекция 2. Моделирование и анализ параллельных вычислений

Модель вычислений в виде графа "операции-операнды". Описание схемы параллельного исполнения алгоритма. Определение времени выполнения параллельного алгоритма. Показатели эффективности параллельного алгоритма.

Понятие графа алгоритма и его свойства

Для описания информационных зависимостей алгоритмов решения задач широко используют модель в виде в виде ациклического ориентированного графа [1-3], называемую графом алгоритма. В этой модели множество операций алгоритма и существующие между операциями информационные зависимости описываются двойкой:

G = (V, E), (2.1)

где V = {1,...,|V|} – множество вершин графа, представляющих операции алгоритма, а E – множество дуг графа, устанавливающих частичный порядок операций. Дуга E_{i, j}= (i, j) принадлежит графу только в том случае, если операция j использует результат выполнения операции i. Свойство ацикличности графа алгоритма состоит в том, что никакая величина не может определяться через саму себя.

Описанная выше модель является направленным графом. Если дугам графа приписать веса , отражающие интенсивность информационного обмена между i-й и j- ветвями программы, такой граф называется взвешенным направленным графом. В общем случае граф алгоритма есть мультиграф, т.е. две вершины могут быть связаны несколькими дугами [2]. При этом в качестве разных аргументов одной операции используется одна и та же величина. Количество вершин графа (не считая вершин ввода) далее будем обозначать . Путь максимальной длины в графе называют критическим.

Для ориентированного ациклического графа с n вершинами существует число s<n , для которого все вершины графа можно так пометить одним из индексов 1,2,…,s, что если дуга из вершины с индексом i идет в вершину с индексом j, то i<j. Покажем это [2].

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

Из схемы разметки следует:

- никакие две вершины с одинаковым индексом не связаны дугой;

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

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

Граф, размеченный в соответствии с описанной схемой, называют строгой параллельной формой графа [2].

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

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

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

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

На рисунках 2.1 и 2.2 в качестве примеров приведены примеры ориентированных графов, описывающих алгоритмы последовательного и каскадного суммирования последовательности 4-х числовых значений. Нетрудно заметить, что ориентированный граф каскадной схемы является одной из возможных строгих параллельных форм.

Рис. 2.1 Граф алгоритма последовательного суммирования	Рис. 2.2 Граф алгоритма каскадного суммирования

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

Задача ставится следующим образом. Параллельный алгоритм представляется графом алгоритма

,

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

Вычислительная система также представляется в виде графа

. (2.2)

Здесь - множество процессоров, - множество дуг, представляющих линии связи между процессорами. Пропускная способность линий связи характеризуется весами дуг графа .

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

. (2.3)

доставляющее экстремум (максимум или минимум) заданному критерию оптимальности .

В рамках общей проблемы отображения обычно решается одна из двух задач:

1. Для данной параллельной программы выбрать решающее поле.

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

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