Анализ дискретных параллельных систем на основе графа условно-достижимых состояний F-сетевых моделей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Беленко, Вячеслав Сергеевич

• Беленко, Вячеслав Сергеевич
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Беленко, Вячеслав Сергеевич

Введение.

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-сетей. В частности, разработаны следующие средства:

• алгоритм построения графа условно достижимых состояний для 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 (г. Санкт-Петербург).

Список литературы диссертационного исследования кандидат технических наук Беленко, Вячеслав Сергеевич, 1999 год

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 с.