8.3. Графы вычислений

Одной из наиболее ранних моделей параллельных вычислений была модель графов вычислений [147]. Ее предложили главным образом для представления параллельного выполнения программ, вычисляющих арифметические выражения.

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

Каждая дуга есть упорядоченная пара узлов представляющая дугу из Каждой дуге сопоставлена четверка Каждая дуга представляет очередь элементов данных, полученных процессором в узле и используемых процессором в узле есть число элементов данных, находящихся первоначально в очереди, соответствующей дуге из Узел подготовлен, если на каждой дуге,

Рис. 8.2. Граф вычислений.

направленной к узлу из каждого узла присутствует не менее элементов данных. называется пороговым значением. При выполнении операции, соответствующей узлу удаляется элементов данных из очереди, соответствующей дуге, направленной к Когда операция, соответствующая завершается, то она помещает элементов данных в очереди, соответствующие каждой дуге направленной из узла к узлу

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

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

Рис. 8.3. Сеть Петри, эквивалентная графу вычислений, изображенному на рис. 8.2.

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

На рис. 8.3 изображена сеть Петри, построенная описанным выше способом для графа вычислений на рис. 8.2.

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

С другой стороны, графы вычислений и конечные автоматы не сопоставимы, как маркированные графы и конечные автоматы. Графы вычислений не могут моделировать принятие решений или условное выполнение — это ограничение справедливо и для маркированных графов. Таким образом, наша иерархия моделей принимает вид, показанный на рис. 8.4.

Карп и Миллер [147] подробно исследовали графы вычислений, особенно проблемы активности и безопасности. В действительности

их интересовало обеспечение и определение условий завершенности графа вычислений (т. е. условия неактивности). Так как дуги (позиции) представляют очереди данных, то исследования ограниченности, проводимые Карпом и Миллером, были направлены на определение максимальной длины очереди. Эти различия в обозначениях и целях, а также отличия в определении моделей между графами вычислений и маркированными графами послужили причиной того, что никто не попытался соотнести результаты и алгоритмы Карпа и Миллера [147] по графам вычислений с работой [54] по маркированным графам.

Рис. 8.4. Добавление графов вычислений к иерархии моделей.