Об исследовании сетей Петри с помощью ЭВМ

| 1. Специализированные программные средства.

К настоящему времени разработано большое количество программных систем автоматизированного анализа сетей Петри, реализующих различные аспекты их использования: анализ общих сетей Петри и имитация их функционирования, ориентация на различные расширения этих сетей, использование средств машинной графики для ввода и редактирования сетей и др. Методы анализа общих и частных свойств сетей Петри - безопасность, ограниченность, консервативность, живость переходов, достижимость, наличие тупиков и циклов - также успешно реализуются на ЭВМ. Некоторые из этих программных систем являются автономными системами анализа сетей Петри (как, например, самая развитая и полная интерактивная система OVIDE [25]), в других сеть Петри используется в качестве имитационной модели, позволяющей провести верификацию и определить динамические характеристики реального моделируемого объекта (коммуникационных протоколов, систем с управлением потоком данных, логических схем, параллельных систем и др.).

Промышленные программы, предназначенные для анализа реальных вычислительных систем с помощью сетей Петри, обычно имеют дело с десятками и сотнями тысяч позиций и переходов и требуют соответствующих вычислительных ресурсов. Так, для моделирования процессора большой ЭВМ CDC 6600 потребовалась сеть Петри, содержащая около 500тысяч позиций и переходов [8].Более скромная система, реализуемая на персональном компьютере, описана в статье [19J.

Как уже упоминалось в п. 2.2, для анализа систем с помощью CPN создан специальный язык моделирования CPN ML[10]. Также приобрели популярность программные средства, разработанные под руководством проф. К. Йенсена в Ааруском университете (Дания).

Отметим, в частности, программу CPN Tools (http; vww.daimi.a u.dk/CPnets/CPN2000). Она распространяется по лицензиям, которые могут свободно получить университеты и академические организации. Программа работает в операционной среде Windows, обладает удобным графическим интерфейсом и может использоваться для моделирования различных систем. Краткая инструкция по работе с этой системой приведена в приложении А.

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

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

Ниже рассмотрен один из возможных подходов к распараллеливанию процесса построения дерева маркировки обыкновенной сети Петри [26].

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

Проблему можно попытаться решить, если распараллеливать вычисления по мере роста дерева, т.е. обрабатывать каждую новую ветку на отдельном потоке. Таким образом, получится, что каждый узел кластера будет обрабатывать свое собственное поддерево.

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

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

0_Писанные проблемы являются, возможно, наиболее значимыми, и при их эффективном решении нахождение остальных характеристик сети Петри будет базироваться на полученных данных.

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

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

Для ограниченных сетей Петри общее возможное количество маркировок конечно (хоть и может быть весьма значительным [9]), в частности, для безопасных сетей оно равно 2 ", где п - число позиций в сети. Таким образом, в начале работы алгоритма количество новых маркировок будет расти, а затем, по мере заполнения списка маркировок, это количество начнет сокращаться. При отсутствии на очередном шаге алгоритма новых маркировок вычислительный процесс останавливается.

Глава 3. Моделирование вычислительных Процессов с помощью цепей Маркова

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

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

свойствах этих процессов.

В настоящей главе рассматривается один класс моделей вычислительных систем, основанный на концепции состояния.

При этом, как отмечалось в первой главе, вычислительный процесс может рассматриваться как некоторая динамическая система (автомат) [7, 11, 12], имеющая набор разрешенных состояний, входные и выходные сигналы, а также преобразователь входных сигналов в выходные.

Одним из распространенных классов класс моделей такого типа являются цепи Маркова, названные так по имени известного русского математика А.А. Маркова, разработавшего теорию в 1907 году. Большой вклад в теорию цепей Маркова внес академик А.Н. Колмогоров. Возможности теории цепей

Маркова далеко выходят за рамки моделирования вычислительных процессов и систем. Эта теория широко применяется в физике, биологии, социологии, экономике, технике и целом ряде других наук [13].

В конце главы рассмотрен ряд задач, решение которых возможно при совместном использовании методологии сетей Петри и цепей Маркова.