Модели функционирования параллельных программ
Другим возможным способом моделирования состояний и функционирования параллельной программы является использование математических
моделей и методов исследования дискретных систем, разработанных в рамках теории
сетей Петри [13]. При таком подходе в качестве модели программы может быть использована
сеть Петри, представляемая размеченным ориентированным графом (изложение материала осуществляется
в соответствии с работой [13] за исключением приведения системы обозначений к
виду, принятому в данном пособии):
1. Множество вершин сети V разделено на два взаимно пересекающихся подмножества вершин-переходов P и вершин-мест R
,
.
Вершины-места обычно изображаются кружками, вершины-переходы представляются в виде прямоугольников или линий-барьеров.
2. Граф сети является "двудольным"
по отношению к подмножествам вершин P и R, т.е. каждое ребро
соединяет вершину P с вершиной R. Задание ребер графа может быть выполнено, например,
при помощи функций инцидентности
,
,
ненулевые значения которых задают
множество ребер E (при сеть содержит ребро вида
, при
сеть содержит ребро вида
).
3. Функция
определяет собой начальную разметку сети, по которой для каждой вершины-места ставится в соответствие целое неотрицательное число (разметка места). При графическом изображении разметка сети показывается соответствующим числом точек (фишек) внутри кружков-мест.
Рис. 5.6. Пример сети Петри
Для пояснения введенных понятий на рис. 5.6 показан пример сети Петри с тремя переходами и четырьмя вершинами мест.
Главной отличительной особенностью многопроцессорной вычислительной системы является ее производительность, т.е. количество операций, производимых системой за единицу времени. Различают пиковую и реальную производительность. Под пиковой понимают величину, равную произведению пиковой производительности одного процессора на число таких процессоров в данной машине. При этом предполагается, что все устройства компьютера работают в максимально производительном режиме.