8.6. Графы UCLA

Сеть Петри является графовой моделью параллельных вычислений. Другая графовая модель разработана в Калифорнийском университете в Лос-Анджелесе под руководством профессора Эстрина. Эта модель является сложной билогической графовой моделью вычислений (или графовой моделью UCLA) [19, 23, 302, 105, 49]. В этой модели системы представляются графом со сложными ориентированными дугами. Сложная дуга — это дуга с (потенциально) многими источниками и назначениями.

Комбинационная логика управляет последовательностью операций в вершинах. Если входной логикой вершины является

(кликните для просмотра скана)

логика то для того, чтобы разрешить действия, фишки должны присутствовать на каждой входной дуге. При логике ИЛИ {-И фишки необходимы только на какой-либо одной входной дуге полнение вершины удаляет разрешающие фишки на входных дугах и помещает фишки на выходные дуги в соответствии с выходной логикой. При выходной логике И фишки помещаются на все выходные дуги, тогда как при логике ИЛИ фишки помещаются на какую-либо одну выходную дугу.

Рис. 8.15. Представление основных элементов графа UCLA в сети Петри.

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

На рис. 8.14 приведен пример графа UCLA. Заметим, что некоторые дуги имеют несколько источников (окончаний) и назначений (начал). Кроме того, отметим, что логика каждой пары дуга-вершина помечена в графе либо для логики И, либо для логики ИЛИ. Степень дуги указывается числом там, где дуга соединяется с вершиной. Степень опускается, если она равна единице, так же, как и обозначение логики, когда только одна дуга является входом в вершину. В приведенном примере вершина а может быть запущена, как только дуга 5 имеет фишки. Когда вершина а запускается, она удаляет фишку из дуги и помещает фишки на дугу А и дугу В (логика И). Вершина с другой стороны, будет помещать фишки либо на дугу либо на дугу (логика ИЛИ). Вершина является разрешенной, когда присутствуют две фишки на дуге или одна фишка на дуге К.

Определение 8.1. Граф UCLA есть шестерка где множество вершин; множество дуг; входное и выходное отображения логики на вершины графа; входная и выходная степень каждой пары

(кликните для просмотра скана)

Рис. 8.17. (см. скан) Сеть Петри, эквивалентная графу UCLA, на рис. 8.14.

дуга-вершина; начальная дуга; конечная дуга.

Дуги графа определяются как упорядоченные пары множеств вершин. Первая компонента пары есть множество входных вершин, а вторая компонента — множество выходных вершин. Начальная дуга имеет пустое множество входных вершин, а конечная дуга — пустое множество выходных вершин.

Преобразование графа UCLA в сеть Петри достаточно просто из-за подобности этих систем. Каждая дуга в графе UCLA представляется позицией в сети Петри. Кроме того, представим вершину и позицией и двумя переходами и Первый переход представляет инициирование операции, связанной с вершиной а второй переход представляет завершение этой операции.

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

Это схематично изображено на рис. 8.15 (моделирование вершин графа UCLA переходами инициирования и завершения не строго обязательно, но удобно). На рис. 8.16 показано как входная и выходная логики графов UCLA представляются эквивалентными сетями Петри. Степень больше единицы моделируется несколькими дугами между позициями и переходами в сети Петри.

На рис. 8.17 граф UCLA с рис. 8.14 преобразован в эквивалентную сеть Петри. Это преобразование показывает, что мощность моделирования графов UCLA вкладывается в мощность моделирования сетей Петри. Очевидно, что сеть Петри может быть преобразована в эквивалентный граф UCLA посредством представления позиций дугами графа UCLA, а переходов — вершинами с входной и выходной логикой И. Таким образом, эти две модели эквивалентны по своей мощности моделирования. На рис. 8.18 показана модифицированная иерархия моделей.