Модификации сетей Петри и их свойства

2. СЕТЕВЫЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

2.1. Модификации сетей Петри и их свойства

            2.1.1. Свойства сетей Петри

            Основные определения и обозначения, используемые при описании сетевых моделей, соответствуют работам [26,46].

            Определение 2.1. Сеть Петри (СП) - это двудольный ориентированный мультиграф N = (P, T, I, O, ), где P - конечное непустое множество элементов, называемых позициями; T - конечное непустое множество элементов, называемых переходами;  I:P´T®{0,1,2...} и O:P´T®{0,1,2...} - функции инцидентности; :P®{0,1,2...} - начальная разметка.

            Обозначим через  n и m мощности множеств P и T соответственно, т.е. n=½P½, m =½T½ . СП обычно представляют в виде геометрического объекта. При этом позиции изображают кружками, переходы - черточками или прямоугольниками. Дуга проводится от позиции  pi к переходу tj, если I(pi, tj) > 0, и от перехода tj к позиции  pi, если O( pi, tj) > 0. Кратность дуги, соединяющей входную позицию  pi с переходом tj, определяется величиной I(pi, tj). Аналогично кратность дуги, соединяющей переход tj с выходной позицией  pi, определяется величиной O(pi, tj). Кратность рассматривается как возможность дублирования дуги, соединяющей вершины  pi и tj (или tj и  pi ), I(pi, tj) (или O(pi, tj)) раз. Если I(pi, tj) > 0, то позицию  pi называют входной к переходу tj, а переход tj - выходным к позиции  pi. Множество входных позиций (pre(tj)) к переходу tj определяется как pre(tj)={p½I(pi, tj) > 0}, а множество выходных переходов (post(pi )) к позиции  pi - как  post(pi)={t ½ I(pi, tj) > 0} .

            Аналогично, если O(pi, tj) > 0 , то переход tj называют входным к позиции  pi, а позицию  pi - выходной к переходу tj . Множество входных переходов к позиции  pi определяется как pre(pi)={t | O(pi, tj) > 0}, а множество выходных позиций к переходу tj - как post(tj)={p | O(pi, tj) > 0}. Входная позиция pi  к переходу tj называется головной, если pre(pi) = Æ . Аналогично выходная позиция pi к переходу tj  называется хвостовой, если post(pi) = Æ .

            Для ссылок на столбцы, строки и элементы матриц I и O будем использовать следующие обозначения:

            I(p,t) (O(p,t)) - элемент матрицы I (O), указывающий на наличие дуги между вершинами  p и t ;

Рекомендуемые материалы

            I(*,t) (O(*,t)) - столбец матрицы I (O), указывающий на множество входных (выходных) позиций относительно перехода t;

            I(p,*) (O(p,*)) - строка матрицы I (O), указывающая на множество выходных (входных) переходов относительно позиции  p.

            Введем понятие элементарной сети.

            Определение 2.2. Элементарной сетью t называется СП N = (P, T, I, O, ), для которой T={t}; P={p',p''}; pre(t)={p'}, post(t) = {p''}; = (0,0).

            При функционировании СП переходит от одной разметки к другой. Каждая разметка представляет собой функцию m: P®{0,1,2...}. Переход может сработать при разметке m, если он активен. Переход tj является активным, если

"pi Î pre(tj): m(pi ) >= I( pi, tj) .

            В результате срабатывания перехода tj разметка меняется в соответствии со следующим правилом:

"pi Î (pre( tj) È post(tj)): m‘(pi ) = m(pi ) - I(pi, tj) + O( pi, tj) .

            В этом случае говорят, что разметка m‘ достижима от разметки m в результате срабатывания перехода tj, а разметка m предшествует m‘. СП останавливается, если при некоторой разметке не может сработать ни один из ее переходов. Такая разметка называется тупиковой. Таким образом, СП моделируют некоторую структуру и динамику ее функционирования.

            Обозначим через T* множество слов в алфавите T. Если разметка m‘ достижима от разметки m в результате срабатывания последовательности переходов n = (t1, t2, ..., tk), где n - слово из множества T* , то это обозначается как

’ или ’ .

            Разметка m достижима в сети N , если m0  ® m . Множество всех достижимых разметок в сети N обозначим через R(N). Тогда переход t достижим от разметки m (m ® t) в сети N , если

$m¢(m¢Î R(N) & m ® m¢): m¢ m¢¢ , где m“Î R(N).

            Переход t достижим в сети N , если m0  ® t .

            Переход t живой, если он достижим от любой разметки из R(N), т.е.

"m Î R(N): m  ® t .

            СП живая, если живы все ее переходы:

"m"t(t Î T & m Î R(N)): m  ® t .

            В приложении к моделированию систем проблема достижимости разметки m0  из m интерпретируется как возможность достижения определенного состояния системы. Анализ СП модели на свойство живости позволяет выявить события, которые могут произойти в моделируемой системе.

            Позиция p  в СП N называется ограниченной, если существует целое число k, такое, что m(p) <= k для любой разметки из множества R(N):

"m Î R(N): m(p)£ k .

            СП является ограниченной, если ограничены все позиции сети:

" p"m ( p Î P & m Î R(N): m(p)£ k .

            Если k=1 , то СП называется безопасной.

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

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

            2.1.2. Модификации сетей Петри

            Иерархические сети. Иерархические сети (ИСП) [26] являются обобщением СП и служат для моделирования иерархических систем, которые наряду с неделимыми, атомарными компонентами содержат составные компоненты, представляющие собой отдельные подсистемы. Для определения ИСП множество переходов разбивается на подмножества простых и иерархических переходов (ИПР). Простым переходам соответствуют элементарные сети. ИПР представляет собой некоторый фрагмент СП.

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

            Ингибиторные сети. В рассмотренных СП недостатком является то, что нельзя отметить срабатыванием перехода факт изменения разметки с ненулевого значения на нулевое. Таким образом из двух альтернатив m(p) ¹ 0 и m(p) = 0, содержащихся в операторе условного вычитания единицы, в СП можно представить только одну, первую, но нельзя отразить проверку на ноль, так как сеть не может реагировать непосредственно на отсутствие метки в позиции. В результате было показано, что СП не могут моделировать машины Минского и Тьюринга [26].

            Флинн и Аджервала [59] модифицировали СП, введя в них специальные ингибиторные дуги, осуществляющие проверку на нулевую разметку, и показали, что получаемое обобщение дает класс сетей равномощных машине Тьюринга. Ингибиторная сеть представляет собой СП, дополненную специальной функцией инцидентности FI:P´T®{0,1}, которая вводит ингибиторные дуги для тех пар (p,t), для которых FI(p,t) = 1. Ингибиторные дуги связывают только позиции с переходами и на рисунках изображаются заканчивающимися не стрелками, а маленькими кружочками. Правило срабатывания перехода в ингибиторной сети модифицируется следующим образом:

"  pi Î pre(tj): m(  pi ) ³ I( pi, tj) & m(  pi )*FI(p,t) = 0 .              (2.1)

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

            Модифицируем определение СП следующим образом. Введем множество PR, элементы которого частично упорядочены отношением "£" (меньше или равно). С каждым переходом t СП свяжем его приоритет pr(t), принадлежащий множеству PR. Правило срабатывания перехода дополним следующим условием: переход t может сработать при разметке m , если для любого другого перехода t' этой сети, который также может сработать при разметке m, pr(t')£pr(t). Другими словами, если несколько переходов готовы сработать, то срабатывает такой переход, приоритет которого не меньше приоритетов остальных готовых к срабатыванию переходов. Такую модификацию СП называют приоритетными сетями. В работе [26] показано, что класс приоритетных СП является строго мощнее СП и равномощен классам машин Тьюринга и Минского.

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

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

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

            Обозначим {P(n)} - семейство матриц размерностью n ´ n , где P(n) = [pij(n)], i,j={1,2,...,n} и pij (n) - условная вероятность смены разметки mi на  mj при срабатывании переходов подмножества n Î T* . Очевидно, что

,                                                                       (2.2)

т.е. P(n) - стохастическая матрица. С учетом введенных обозначений объект NS=(N,{P(n)}) назовем стохастической СП (СТСП).

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

            Среди данных расширений можно выделить раскрашенные СП [68,75], Е-сети [50], PROT-сети [62], предикатные (интерпретируемые, конструируемые) СП [60], СП для описания процедур принятия решений (нейронные, нечеткие, числовые, абстрактные) [77] и другие.

            2.1.3. Примеры СП-моделей параллельных вычислительных систем

            В качестве примеров рассмотрим СП, описывающие некоторые структуры параллельных ВС в соответствии с классификацией Флинна.

ОКОД (один поток команд - один поток данных). Представителями подобной организации архитектуры являются обычные ЭВМ фон Неймана, ЭВМ CDC 6600, ЭВМ CDC 7600 с конвейерной арифметикой, ЭВМ AMDAHL 470/6 с конвейерной обработкой команд. На рис.2.1,а изображен синхронный конвейерный процессор с архитектурой типа ОКОД, а на рис.2.2,а - асинхронный конвейерный процессор с архитектурой аналогичного типа.

            СП, моделирующая синхронный конвейерный процессор, представлена на рис.2.1,б. При этом позиции и переходы получили следующую интерпретацию:

tk1 - синхронизация приема данных процессорными элементами;

ti2 - начало работы i-го ПЭ;

ti3 - окончание работы i-го ПЭ;

t02 - запись результатов работы конвейерного процессора в ОП;

pi1 - признак готовности входных данных для i-го ПЭ;

pi2 - признак приема входных данных i-м ПЭ;

pi3 - признак протекания процесса обработки данных i-м ПЭ;

p01 - признак готовности процессора для записи результатов в ОП;

p02 - признак окончания цикла обработки данных на конвейерном процессоре.

СП-структура, моделирующая асинхронный конвейерный процессор с промежуточными буферами, представлена на рис.2.2,б. Интерпретация вершин СП следующая:

ti1 - считывание данных i-го ПЭ из промежуточного буфера;

ti2 - обработка данных i-м ПЭ;

ti3 - запись результатов работы i-го ПЭ в промежуточный буфер;

t01 - пересылка данных из ОП во входной буфер 1-го ПЭ;

t02 - запись результатов работы конвейерного процессора в ОП;

pi1 - признак нахождения данных во входном буфере i-го ПЭ;

pi2, pi3 - физический смысл данных позиций аналогичен смыслу позиций СП-структуры синхронного процессора;

pi4 - признак готовности i-го ПЭ для считывания новых данных;

p0i(i+1) - признак незанятости буфера между i-м и i+1-м ПЭ;

p01 - моделирование шины обмена данными с ОП;

            p02 - признак окончания цикла обработки данных на конвейерном процессоре.

ОКМД (один поток команд - множественный поток данных или  SIMD-архитектура). На рис.2.3,а представлен процессор с SIMD-архитектурой (один поток команд - множество потоков данных), где УУ - устройство управления, ПЭ - процессорный элемент, МП - модуль памяти, ОП - общая память, ПК - поток команд, ПД - поток данных. Типичными представителями SIMD-архитектуры являются ЭВМ CRAY-1 (конвейерная векторизация), ILLIAC IV (процессорная матрица), параллельный процессор (МРР) НАСА, распределенный матричный процессор (DAP) фирмы ICL, многопроцессорная ВС "Эльбрус-1". Команды и данные в этих системах хранятся в глобальной оперативной памяти. Центральное устройство управления направляет операции всем ПЭ, связывая их глобальной сетью распространения и синхронизируя их работу.

            СП-структура, моделирующая процессор с SIMD-архитектурой, представлена на рис.2.3,б. При этом позиции и переходы СП получили следующую интерпретацию:

t1 - действия УУ при координации всех ПЭ;

t2i - функционирование i-го ПЭ при обработке команд от УУ;

t3i - обращение i-го ПЭ к общей памяти;

t4i - передача данных из общей памяти в локальную память i-го ПЭ;

t5i - выработка признака окончания обработки данных i-м ПЭ;

t6  - выработка признаков окончания обработки команды параллельным процессором;

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

p2i - признак поступления данных на i-й ПЭ;

p3i - признак запроса данных из общей памяти i-м ПЭ;

p4  - арбитр, координирующий обращение ПЭ к участкам общей памяти;

p5i - признак окончания считывания данных из общей памяти i-м ПЭ;

p6i - признак окончания обработки данных i-м ПЭ.

МКМД (множественный поток команд - множественный поток данных или MIMD-архитектура). На рис.2.4,а представлен процессор с MIMD-архитектурой. Представителями MIMD-архитектуры являются ЭВМ Cray X-MP, Cray-2,3,4, Cyber-205, ETA-CF10, МАРС-М.  СП, моделирующая процессор с MIMD-архитектурой, представлена на рис.2.4,б. При этом позиции и переходы СП получили следующую интерпретацию:

ti1 - выдача i-м УУ потока команд;

ti2 - прием i-м ПЭ команды из потока команд;

ti3 - чтение i-м ПЭ данных из ОП, выполнение команды и запись результатов в МП;

ti4 - подготовка i-го ПЭ к приему очередной команды из потока;

Если Вам понравилась эта лекция, то понравится и эта - О законах войны.

ti5 - подготовка i-го ПЭ к приему нового потока команд;

pi1 - признак, сигнализирующий i-му УУ о начале передачи потока команд;

pi2 - признак поступления на вход i-го ПЭ команды из входного потока;

pi3 - признак готовности i-го ПЭ к выполнению операции обмена данными с МП;

pi4 - признак окончания обработки команды i-м ПЭ;

p01 - арбитр, координирующий обращение к ОП параллельных процессов.