автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Анализ дискретных параллельных систем на основе графа условно-достижимых состояний F-сетевых моделей

ол

На правах рукописи

10

Беленко Вячеслав Сергеевич

Анализ дискретных параллельных систем на основе графа условно-достижимых состояний Р-сетевых моделей

специальность 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей»

диссертации на соискание ученой степени кандидата технических наук

АВТОРЕФЕРАТ

С.-Петербург 1999

Работа выполнена в Санкт-Петербургском государственном университете азрокосмического приборостроения

Научный руководитель - кандидат техн. наук, доц. A.B. Гордеев

Официальные оппоненты: д.т.н., доц. Малыхина Г.Ф.

к.т.н., доц. Сабинин О.Ю.

Ведущая организация: Институт информатики и автоматизации Российской Академии Наук.

Защита диссертации состоится 22 декабря 1999 г. в _ часов на

заседании диссертационного совета Д 063.21.02 в Санкт-Петербургском Государственном университете азрокосмического приборостроения по адресу ул. Большая Морская, 67

С диссертацией можно ознакомиться в библиотеке

Автореферат разослан "_"__199_ г.

Ученый секретарь совета ' f-"' Фильчаков B.B.

Подписано в печать 16.11.99. Печать - ризография. Бумага офсетная. Тираж 80 экз. Заказ 511. Формат 60^ЭО'/,,

Отпечатано в ООО "Политехника-сервис" 191011, Сзнет-Петербург, ул. Инженерная, 6

Общая характеристика работы

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

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

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

целью выбора оптимальной конфигурации проектируемой системы, определения ее недостатков и преимуществ.

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

Основные задачи. В процессе выполнения исследований по вопросам диссертационной работы решались следующие основные задачи:

□ изучение существующих методов анализа свойств Р-сетей и выявление их недостатков

□ разработка усовершенствованного метода анализа свойств Р-сетей на базе множества достижимых состояний модели

□ реализация алгоритма анализа свойств Р-сетей на базе множества достижимых состояний модели

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

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

□ метод представления пространства состояний Р-сети с помощью построения графа условно достижимых состояний

□ метод анализа Р-сетей на основании графа условно достижимых состояний

□ алгоритм построения графа условно достижимых состояний. Практическая значимость. Использование предлагаемых в данной

диссертационной работе подходов позволяет расширить круг моделей,

анализ которых может производиться с помощью F-сетей. В частности, разработаны следующие средства:

□ модуль построения графа условно достижимых состояний для F-сетевых моделей;

□ структуры данных для эффективного машинного представления графа условно достижимых состояний.

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

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

□ метод и алгоритм построения графа условно достижимых состояний для F-сетевой модели

□ метод анализа F-сетей на основании графа условно достижимых состояний.

Внедрение результатов. Основные результаты диссертационной работы использованы в следующих организациях:

□ Санкт-Петербургский государственный университет аэрокосмического приборостроения

□ LG ТСМ S/W Laboratory (г. Санкт-Петербург) для проведения исследований по проекту "Speech processing system" Использование результатов диссертационной работы подтверждено

соответствующими актами

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях и семинарах:

□ "Диагностика, информатика и метрология - 95" - научно-техническая конференция, СПб, 4-6 июля 1995 года

□ "Автоматизация процессов управления соединениями и частями ПВО, информационные технологии" - научная военно-техническая конференция, СПб, 15-16 мая 1996 года

Публикации. По результатам диссертационной работы опубликовано 4 печатные работы и доклада.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы (55 наименований). Объем основной части - 118 страниц машинописного текста.

Краткое содержание работы по главам

1. Анализ дискретных параллельных систем

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

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

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

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

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

позволяет полностью решить задачи достижимости и покрываемое™, хотя доказано, что данные задачи разрешимы.

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

В последнем разделе данной главы описаны основные подходы к анализу Я-сетевых моделей. Среди них указан метод, использующий граф достижимости (дерево достижимости) Р-сети, Такой граф может быть сильноветвящимся и иметь большую мощность, что затрудняет процесс его построения, а, следовательно, и процесс анализа модели. Существует метод для решения задач достижимости и покрываемости, основанный на использовании начальной и конечной (искомой) маркировок. Данный метод позволяет найти все последовательности срабатывания переходов, переводящих сеть из начальной маркировки в искомую маркировку, и затем выделить конечное множество последовательностей срабатывания переходов, удовлетворяющее заданным условиям. Такой метод теоретически позволяет решить

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

2. Анализ Р-сетевых моделей с помощью графа условно достижимых состояний

Вторая глава данной работы посвящена разработке и применению методов анализа имитационных моделей к Р-сетевым моделям.

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

Во втором разделе данной главы приводится описание формализма Р-сетей. В третьем разделе данной главы рассматривается существующий метод построения графа достижимости Р-сети и его недостатки. Данный метод базируется на исходном алгоритме для обычных сетей Петри. Различия обусловлены главным образом учетом времени и наличием вероятностных альтернатив срабатывания переходов Р-сети.

Определение 2.1. Состоянием Р-сети называется двойка э=<М,0>, где М - вектор, описывающий маркировку позиций, а О - вектор, отражающий состояния переходов. Формализм Р-сетей предполагает пребывание каждого из переходов сети в одном из трех состояний: пассивном, активном и блокированном. Состояние одного перехода описывается элементом с1, принадлежащим множеству {Ы V {0} V {у}}.

Здесь {Ы V {0}} - множество натуральных чисел и 0; {у} - множество, состоящее из признака блокирования перехода у. Пассивному состоянию перехода соответствует 0, блокированному - признак у, активному - время

Процесс построения дерева достижимости даже для простой сети может потребовать немало вычислительных ресурсов. Например, для простой Я-сети с циклом, граф которой приведен на рисунке 2.1, число вершин в дереве достижимости можно оценить как к", где: к - число вариантов срабатывания перехода 11 по времени

п - соотношение между временами срабатывания переходов Т1 и тг, определяемое формулой тг=пт1+г

Тем не менее, с точки зрения качественного анализа поведения сети вполне удовлетворительные результаты можно получить с помощью графа, описывающего возможные состояния Р-сети. На этом графе вершины помечены вектором О', каждый элемент которого содержит признак пассивности (0), либо активности (*) соответствующего перехода.

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

Определение 2.2. Редуцированным состоянием Р-сети называется двойка б'=<М, 0'>, где М - вектор, описывающий маркировку позиций, а О' - вектор, отражающий состояния переходов. Каждый элемент с!' вектора Э' принадлежит множеству {а, р, у). Здесь а - признак активности перехода, )3 - признак пассивности перехода, у - признак блокирования перехода. Редуцированным пространством состояний Б' для Р-сети называется множество всех возможных ее редуцированных состояний.

Утверждение 2.1. Мощность редуцированного пространства состояний для Р-сети меньше или равна мощности пространства состояний этой же сети.

Отношение мощностей пространств указанных состояний можно оценить как

с^.с^и^О.^) (21)

С.ир{8') С,цр({0'}) 3" 1

Для моделей реальных систем, как правило, выполняется условие 1|»1. Поэтому для вышеприведенного соотношения верно следующее:

С^=С^})=П^+2)>>Л(1 + 2)= | >1>|и111П (2.2)

С.„р(5') С.цр<{0'}) 3" У 3

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

Определение 2.3. Множеством порождающих переходов Т9(з) будем называть множество переходов, каждый из которых по отдельности или

в сочетании с другими может своим срабатыванием перевести сеть из состояния в в другое состояние. Каждый переход 1еТа(в) называется порождающим переходом в состоянии э.

Утверждение 2.2. Число всех возможных вариантов сочетаний порождающих переходов для множества Т9(з) мощности п равно 2"-1.

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

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

Определение 2.4. Ординальной функцией для пары переходов сети называется отображение

Огс! (11,12): ТхТ->{<, >, =, <, >, ?}, Ъ, 12бТ, (2.3)

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

Для двух порождающих переходов <1 и принципиально может существовать несколько вариантов временных диаграмм их взаимного срабатывания, исчерпываемых следующими схемами:

Работа перехода <1

А_

£

Работа перехода Ь

_ГС.

л ф

У

XI >11

У

2 Работа перехода Ь

4-

Работа перехода ¿г т.-12 . I

3 Работа перехода (1 О

Работа перехода (г 1,-11 _А^

У

1,>Тг

Ф-' Ф

-у-

Рис. 2.2. Диаграммы срабатывания двух переходов.

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

Можно сформулировать следующий алгоритм построения графа условно достижимых состояний. Каждая вершина графа соответствует некоторому редуцированному состоянию сети з'=<М, 0'>, где М -вектор, описывающий маркировку позиций, а О' - вектор, отражающий состояния переходов. Граничной вершиной графа будем называть такую вершину, для которой еще не был произведен процесс порождения дочерних вершин. Пусть X - это текущая рассматриваемая

граничная вершина графа, тогда необходимо выполнить следующие шаги:

Первый шаг. Если в дереве имеется другая вершина У, не являющаяся граничной, и с ней связана то же состояние (с точностью до символов м в маркировке позиций), то вершина X - дублирующая, и она должна быть объединена с У

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

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

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

В шестом разделе данной главы рассматривается метод анализа свойств модели с помощью графа условно достижимых состояний.

Поскольку в графе условной достижимости опускаются конкретные значения времени и вероятности, с его помощью можно решать следующие задачи:

1. Есть ли в модели тупиковые состояния и если да, то по какой трассе в них можно попасть.

2. По какой трассе можно попасть из заданной начальной маркировки в заданную конечную маркировку.

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

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

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

Можно предложить следующий алгоритм определения непротиворечивости пути на графе условно достижимых состояний. Пусть дан некоторый путь УУ на графе, включающий в себя п элементов.

На каждом ¡-ом шаге формирования такого пути (¡=1...п) завершает работу переходов из числа ранее запущенных. Эти т; переходов можно разбить на I классов эквивалентности по следующему принципу: Класс эквивалентности Си - переходы, запущенные на первом шаге формирования пути и завершившие работу на ¡-ом шаге формирования пути

Класс эквивалентности С,? - переходы, запущенные на втором шаге формирования пути и завершившие работу на ¡-ом шаге формирования пути и т.д.

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

Теорема. Предложенный алгоритм является необходимым и достаточным условием непротиворечивости пути на графе условно достижимых состояний.

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

3. Программная реализация алгоритмов моделирования и анализа систем с параллельными процессами с помощью аппарата Р-сетей

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

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

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

Далее в работе следует описание структуры данных программного комплекса, построенной на основе технологий объектно-ориентированного программирования. Базовыми элементами иерархии структур данных являются классы типа "позиция" и "переход". Структура данных и метод описания процедур функционирования переходов положены в основу алгоритма имитационного моделирования параллельных асинхронных систем с помощью Р-сетей, реализующего управление поведением модели на основе событий. Данный алгоритм назван списковым событийным алгоритмом имитационного моделирования.

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

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

В третьем разделе данной главы рассматривается реализация алгоритма построения дерева достижимости для Р-сетевой модели. Эта

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

В четвертом разделе данной главы рассматривается реализация алгоритма построения графа условно достижимых состояний для Р-сэтевой модели. Как было указано ранее, алгоритм построения графа условно достижимых состояний во многом основывается на алгоритме построения дерева достижимости для Р-сети. Блок-схема алгоритма построения графа условно достижимых состояний для Р-сети приведена на рис. 3.1.

Рис.3.1. Блок-схема алгоритма построения графа условно достижимых

состояний

Основные результаты работы

В процессе выполнения работы были решены следующие основные

задачи по теме диссертации:

1. Произведен выбор математического аппарата, который позволяет в полной мере осуществить решение задач моделирования и анализа свойств дискретных параллельных систем. В качестве такого аппарата выбран формализм расширения сетей Петри -формализм F-сетей.

2. Произведено исследование существующих алгоритмов и методов анализа F-сетей и сделан обоснованный вывод об их неприменимости на практике в силу большой сложности по времени и памяти

3. Предложен способ сокращения мощности пространства состояний F-сетевых моделей дискретных параллельных систем с помощью графа условно достижимых состояний. Данный способ предполагает путем сокращения объема информации о состояниях модели существенно повысить эффективность процесса построения множества достижимости модели.

4. Разработан алгоритм построения графа условно достижимых состояний F-сетевой модели

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

6. Предложенный метод анализа дискретных параллельных систем на базе F-сетей реализован в виде модуля, интегрированного в программный комплекс моделирования и анализа "Сети Петри для Windows". Разработанный метод был апробирован при проведения

исследований по проекту "Speech processing system" в LG ТСМ S/W Laboratory (г. Санкт-Петербург) .

Публикации

По результатам диссертационной работы опубликованы следующие

печатные работы:

1. Беленко B.C., Гордеев A.B. Анализ объектов, представленных F-сетями Петри, с помощью дерева достижимости Яезисы докладов научно-технической конференции "Диагностика, информатика и метрология - 95" 4-6 июля 1995 года - СПб.:1995

2. Беленко B.C., Гордеев A.B. Использование F-сетевых моделей для исследования функционирования систем управления //Автоматизация процессов управления соединениями и частями ПВО, информационные технологии. Состояние и перспективы создания единой автоматизированной радиолокационной системы Яезисы докладов научной военно-технической конференции 15-16 мая 1996 года - СПб.: 1996

3. Беленко B.C. Использование F-сетевых моделей для исследования поведения управляющих систем /Сборник научных трудов СПГУАП -СПб.: СПГУАП, 1998

4. Беленко B.C. Анализ F-сетевых моделей с помощью параметризованного графа достижимости /Сборник научных статей СПГУАП "Информационные системы в промышленности и экономике" - СПб.: СПГУАП, 1998

Введение.

1. Анализ дискретных параллельных систем.

1.1 Основные подходы к моделированию дискретных параллельных систем.

1.2 Применение аппарата сетей Петри для имитационного моделирования дискретных параллельных систем.

1.3 Анализ дискретных параллельных систем на базе классического формализма сетей Петри.

1.4 Анализ расширений формализма сетей Петри.

1.5 Подходы к анализу Р-сетевых моделей.

2. Анализ Р-сетевых моделей с помощью графа условно достижимых состояний.

2.1 Постановка задачи имитационного моделирования с помощью аппарата сетей Петри.

2.2 Формальное описание Р-сетей.

2.3 Существующий метод построения графа достижимости Р-сети и его недостатки.

2.4 Граф условно достижимых состояний Р-сети.

2.5 Алгоритм построения графа условно достижимых состояний.

2.6 Анализ свойств модели с помощью графа условно достижимых состояний.

3. Программная реализация алгоритмов моделирования и анализа систем с параллельными процессами с помощью аппарата Р-сетей.

3.1 Машинное представление структур данных Р-сетевых моделей

3.2 Реализация алгоритма имитационного моделирования на основе Р-сетей.

3.3 Реализация алгоритма построения дерева достижимости для Р-сетевой модели.

3.4 Реализация алгоритма построения графа условно достижимых состояний для Р-сетевой модели.

3.5. Анализ Р-сетевых моделей с помощью графа условно-достижимых состояний на примере системы обработки речевых сигналов.

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

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

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

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

Основные задачи. В процессе выполнения исследований по вопросам диссертационной работы решались следующие основные задачи:

• изучение существующих методов анализа свойств Р-сетей и выявление их недостатков;

• разработка усовершенствованного метода анализа свойств Р-сетей на базе множества достижимых состояний модели;

• реализация алгоритма анализа свойств Р-сетей на базе множества достижимых состояний модели.

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

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

• метод представления пространства состояний Р-сети с помощью построения графа условно достижимых состояний;

• метод анализа Р-сетей на основании графа условно достижимых состояний;

• алгоритм построения графа условно достижимых состояний.

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

• алгоритм построения графа условно достижимых состояний для F-сетевых моделей;

• структуры данных для эффективного машинного представления графа условно достижимых состояний.

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

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

• метод и алгоритм построения графа условно достижимых состояний для F-сетевой модели;

• метод анализа F-сетей на основании графа условно достижимых состояний.

Внедрение результатов. Основные результаты диссертационной работы использованы в следующих организациях:

• Санкт-Петербургский государственный университет аэрокосмического приборостроения;

• LG ТСМ S/W Laboratory (г. Санкт-Петербург) для проведения исследований по проекту "Speech processing system".

Использование результатов диссертационной работы подтверждено соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях и семинарах:

• "Диагностика, информатика и метрология - 95" - научно-техническая конференция, СПб, 4-6 июля 1995 года;

• "Автоматизация процессов управления соединениями и частями ПВО, информационные технологии" - научная военно-техническая конференция, СПб, 15-16 мая 1996 года.

Публикации. По теме диссертационной работы Беленко B.C. опубликованы следующие печатные работы:

1. Беленко B.C., Гордеев A.B. Анализ объектов, представленных F-сетями Петри, с помощью дерева достижимости /Тезисы докладов научно-технической конференции "Диагностика, информатика и метрология - 95" 4-6 июля 1995 года - СПб.: 1995, с.113-114;

2. Беленко B.C., Гордеев A.B. Использование F-сетевых моделей для исследования функционирования систем управления. //Автоматизация процессов управления соединениями и частями ПВО, информационные технологии. Состояние и перспективы создания единой автоматизированной радиолокационной системы /Тезисы докладов научной военно-технической конференции 15-16 мая 1996 года - СПб.: 1996, с.42-45;

3. Беленко B.C. Использование F-сетевых моделей для исследования поведения управляющих систем /Сборник научных трудов СПГУАП -СПб.: СПГУАП, 1998, с.23-26;

4. Беленко B.C. Анализ F-сетевых моделей с помощью параметризованного графа достижимости /Сборник научных статей СПГУАП "Информационные системы в промышленности и экономике" - СПб.: СПГУАП, 1998, с.37-38.

Выводы

1. В силу использования объектно-ориентированного подхода к программированию возможна совместная реализация методов анализа свойств модели, как по дереву достижимости, так и по графу условно достижимых состояний, предполагающая использование комбинированного метода при анализе свойств модели

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

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

Заключение

В процессе выполнения работы были решены следующие основные задачи по теме диссертации:

1. Произведен выбор математического аппарата, который позволяет в полной мере осуществить решение задач моделирования и анализа свойств дискретных параллельных систем. В качестве такого аппарата выбран формализм расширения сетей Петри - формализм Р-сетей.

2. Произведено исследование существующих алгоритмов и методов анализа Р-сетей и сделан обоснованный вывод об их неприменимости на практике в силу большой сложности по времени и памяти

3. Предложен способ сокращения мощности пространства состояний Р-сетевых моделей дискретных параллельных систем с помощью графа условно достижимых состояний. Данный способ предполагает путем сокращения объема информации о состояниях модели существенно повысить эффективность процесса построения множества достижимости модели.

4. Разработан алгоритм построения графа условно достижимых состояний Р-сетевой модели

5. Создан новый метод анализа свойств Р-сетевых моделей с помощью графа условно достижимых состояний. Данный подход, в отличие от существующих методов, предлагает практически

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

6. Предложенный метод анализа дискретных параллельных систем на базе F-сетей реализован в виде модуля, интегрированного в программный комплекс моделирования и анализа "Сети Петри для Windows". Разработанный метод был апробирован при проведении исследований по проекту "Speech processing system" в LG ТСМ S/W Laboratory (г. Санкт-Петербург).

1. Advances in Petri nets, 1991: Paper from the 11th 1.tern. Conf. on applications a theory of Petri nets held in Paris in June 1990. IG. Rozenberg (ed.). - Berlin etc.: Springer-Verlag, cop. 1991. -VIII, pp.572.

2. Application and theory of Petri nets, 1993: 14th Intern. Conf., Chicago, Illinois, USA, June 21-25, 1993: Proceedings /Macro Ajmone Marsan (ed.) Berlin etc.: Springer-Verlag, cop. 1993. - IX, pp.591.

3. Attieh A., Brady M., Knottenbelt W., Kritzinger P.S., Functional and Temporal Analysis of Concurrent Systems, Protocol Workshop, 16th International Conference on Theory and Application of Petri nets, Turin, June 1995

4. Ajmone-Marsan M., Stochastic Petri Nets: An elementary introduction, LNCS vol. 424, Springer-Verlag, 1989

5. Bause F., Queuing Petri Nets A formalism for the combined qualitative and quantitative analysis of Systems, 5th Int. Workshop of Petri Nets and Performance Models, Toulouse, France, Oct. 1993

6. Bernardinello L., De Cindio F., A survey of Basic Net Models and Modular Net Classes, LNCS vol. 609, Springer-Verlag, 1992

7. Battiston E., De Cindio F., Mauri G., OBJSA Nets: a class of High-Level Nets having Objects as Domains, In: G. Rozenberg, Advances in Petri Nets 1988, LNCS vol. 340, Springer-Verlag, 1988

8. Burkhardt H. J., Ochsenschlegder P., Prinoth R., Product Nets A formal description technique for cooperating systems, GMD - Studien Nr. 165, Sept. 1989

9. H.Conte G., Balbo G., Ajmone-Marsan M., Chiola G., Generalized Stochastic Petri Nets: A Definition at the Net Level and its Implications, IEEE Transactions on Software Engineering, Vol. 19, 1993

10. Couvillion J., Freire R., Johnson R., Obal W. D., Qureshi M. A., Rai M., Sanders W. H., Tvedt J. E., Performability Modeling with UltraSAN, IEEE Software, Special Issue on Software for Performance Analysis, September 1991

11. Damm W., Dehmen G., AADL: a net based specification method for computer architecture design, in: J. Bakker (ed.) "Languages for parallel architectures: design semantics and implementation models." John Wiley and sons, 1989

12. Dutheillet C., Haddad S., Regular Stochastic Petri Nets, Proc. 10th Int. Conf. on Application and Theory of Petri Nets, Bonn, Germany, June 1989

13. Genrich H. J., Lautenbach K., System Modeling with High-Level Petri Nets, Theoretical Computer Science, vol. 13, 1981

14. Jensen K., Colored Petri Nets: A high-level Language for System Design and Analysis, LNCS vol. 483, Springer-Verlag 1990

15. Kemper P., Bause. F. An efficient polynomial-time Algorithm to Decide Liveness and Boundedness of Free-Choice Nets. In K. Jensen, editor, Application and Theory of Petri Nets 1992, LNCS 616, pp. 263-278, Berlin, Springer-Verlag 1992.

16. Kemper P., Linear time Algorithm to find a minimal deadlock in a strongly connected Free Choice Net. In K. Jensen, editor, Application and Theory of Petri Nets 1994, LNCS 753, pp. 195-214, Berlin, Springer-Verlag 1994.

17. Nutt G. The Formulation and Application of Evaluation Nets //Technical Report 72-07-02, Computer Science Group, University of Washington, Seattle, July 1972, pp.170.

18. Oswald H., Esser R., Mattmann R., An environment for specifying and executing hierarchical Petri Nets, Proc. Int. Conf. on Software Engineering, IEEE, 1990

19. Rozenberg G., Thiagarajan P. S., Petri Nets: Basic Notions, Structure, Behavior, LNCS vol. 424, Springer-Verlag, 1986

20. Schoof S., Sonnenschein M., Wieting R., High-level Modeling with THOR Nets, Proceedings of the 14th International Congress on Cybernetics, Namur, Belgium, August 21-25, 1995

21. Starke P. H., Remarks on Timed Petri Nets, Proc. 9th European Workshop on Application and Theory of Petri Nets, 1988

22. Van Der Aalst W.M.P., Interval Timed Colored Petri nets and their Analysis, LNCS vol. 691, Springer-Verlag, 1993

23. Zuberek W.M., M-timed Petri nets, priorities, preemptions and performance evaluation of systems, LNCS vol. 222, Springer-Verlag, 1986

24. Zuberek W.M., On generation of state space for timed Petri nets, ACM Annual Computer Science Conference, Atlanta, pp.239-248, 1988

25. Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных / Под ред. М. Брейера. М.: Мир, 1979 с.463

26. Анишев П.А. Редуцируемость сетей Петри //Программирование, 1982, №4

27. Бакуман О.Л. Поведенческие свойства сетей Петри (обзор французских работ) //Изв. АН СССР. Техническая кибернетика, 1987, №5, с. 134-150.

28. Балк В.М. Применение сетей Петри для повышения эффективности микропрограмм параллельных вычислительных систем: Автореф. дис. на соиск. учен. степ. канд. техн. наук /Московский институт радиотехники и автоматики М.: 1989 - 13 с.

29. Беликов, Рутнер, Раскрашенные сети Петри и матричный метод //Программирование, 1988, №3

30. Бестужева H.H., Руднев В.В. Временные сети Петри. Классификация и сравнительный анализ //Автоматика и телемеханика, 1990, № 10 с.3-21.

31. Будинас Б.Л. Разрешимость проблемы достижимости для сетей Петри //Автоматика и телемеханика, 1988, № 11 с.3-39.

32. Вальковский В.А. Распараллеливание алгоритмов и программ М.: Радио и связь, 1989

33. Волков С.И., Решетникова H.H. Диагностирование объектов на основе инвариантов сетей Петри //Тезисы докл. X симпозиума по проблеме избыточности в информационных системах Л.: 1989 - ч. 3, с.26-29.

34. Гордеев A.B., Доманский В.Т., Молчанов А.Ю. Использование сетевых моделей для имитационного моделирования системы диспетчерского контроля и управления устройствами электроснабжения железных дорог//Вестник ВНИИЖТ, 1994, №1, с. 38-48.

35. Гордеев A.B., Молчанов А.Ю. Применение сетей Петри для анализа вычислительных процессов и проектирования вычислительных систем: Учебное пособие СПб.: ГААП, 1993.

36. Гордеев A.B., Филиппов С.Г. Введение избыточности в Е-сети для редуцирования имитационных моделей. // X Всесоюзный симпозиум по проблеме избыточности в информационных системах: Тез. докл. /АН СССР Л.: 1989 - ч.З, с.22-25.

37. Грис Д. Наука программирования /Пер. с англ. М.: Мир, 1989.

38. Долгов А.Н., Мацула В.Ф. Современное состояние средств автоматизации имитационного моделирования вычислительных систем реального времени: По данным отечественной и зарубежной печати Л.: ЦНИИ "Румб", 1990.

39. Долгов А.Н., Мацула В.Ф. Средства автоматизации имитационного моделирования встраиваемых вычислительных систем //Управляющие системы и машины, 1990, № 3 с. 110-117.

40. Жаков В.И. Анализ параллельных алгоритмов и синтез программ с использованием символьных сетей: Дис. на соиск учен. степ. канд. техн. наук /Ленинградский институт авиационного приборостроения -Л.: 1991 156 с.

41. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания М.: Высшая школа, 1982.

42. Ильин В.П., Смирнов М.И. Моделирование систем на основе ингибиторных временных сетей Петри //Электронное моделирование, 1990, т.12, №2, с.10-13.

43. Котов В.Е. Сети Петри. М.: Наука, 1984, 160 с.

44. Костин А.Е., Савченко Л.В. Модифицированные Е-сети для исследования систем распределенной обработки информации //Автоматика и вычислительная техника, 1988, №6, с.27-35.120

45. Мамиконов А.Г., Кульба В.В., Швецов А.Р. Модифицированные сети Петри /АН СССР. Институт проблем управления М.: ИПУ, 1991 - 45 с.

46. Молчанов А.Ю. Методы и средства моделирования и анализа на основе Р-сетей. Дис. на соиск учен. степ. канд. техн. наук /Ленинградский институт авиационного приборостроения П.: 1997 -140 с.

47. Мурата Т. Сети Петри: Свойства, анализ, приложения (обзор) //ТИИЭР, 1989, №4, с.41-85.

48. Никонов В.В., Подгурский Ю.Е. Применение сетей Петри //Зарубежная радиоэлектроника, 1986, №11, с. 17-37

49. Питерсон Дж. Теория сетей Петри и моделирование систем М.: Мир, 1984

50. Сигорский В.П. Математический аппарат инженера Киев: Техника, 1975-с. 766

51. Фрир Дж. Построение вычислительных систем на базе перспективных микропроцессоров / Пер. с англ. М.: Мир, 1990 -с.414

52. Шрайбер Т. Д. Моделирование на вРвЭ М.: Машиностроение, 1980-592 с.