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

ВВЕДЕНИЕ

1 Разработка параллельных программ

1.1 Парадигмы параллельного программирования.

1.2 Особенности вычислительной среды для параллельных программ.

1.2.1 Выбор языка программирования.

1.2.2 Межпроцессное взаимодействие на уровне операционной системы.

1.2.3 Специализированные библиотеки и расширения языков для параллельного программирования.

1.3 Проблемы параллельного программирования.

1.3.1 Масштабируемость и эффективность.

1.3.2 Повторное использование текста программ.

1.3.3 Корректность.

1.3.4 Тестирование и отладка.

1.4 Сети Петри в проектировании и анализе параллельных программ. Постановка задачи.

• Актуальность.

Вычислительная техника с момента зарождения до наших дней миновала уже множество стадий развития, в том числе и стадии смены элементной базы, ранее называвшиеся поколениями; и развитие архитектуры микропроцессоров, появление персональных компьютеров; и развитие локальных вычислительных сетей. Компьютеры становились меньше по размерам, быстрее, мощнее и, наконец, дешевле. В настоящее время большому кругу потребителей открылась новая возможность - использование суперкомпьютеров и кластеров, собранных на базе стандартных интегральных схем - модулей. В отличие от суперкомпьютеров недалекого даже прошлого современная вычислительная техника не имеет строгих ограничений в ресурсной области, так как объём памяти, производительность, объём дискового пространства может быть расширен экстенсивным образом, не меняя принципиальной схемы работы кластера, если речь идёт не о нескольких порядках раз. В связи с этим расширяется также и круг задач, которые могут быть решены с использованием суперкомпыотерной техники. Задачи, называемые "grand challenges", перестают быть задачами фундаментальной науки. Среди них можно упомянуть такие задачи, как построение полупроводниковых приборов, разработка фармацевтических препаратов, транспортные задачи, распознавание и синтез речи, распознавание изображений, эффективность систем сгорания топлива. Однако программирование параллельных вычислительных комплексов остаётся областью деятельности высококвалифицированных специалистов. Не последнюю роль в этом играет качество средств для разработки параллельных программ и сложность их отладки. Если последовательные императивные языки программирования можно считать уже устоявшимися, поскольку все они предоставляют примерно одинаковый набор семантических конструкций, то параллельные языки программирования в настоящее время активно развиваются, что свидетельствует о незаконченности их конструктивной базы. В связи с этим следует отметить исследования, проведенные под руководством академика В.В. Воеводина, по адаптации последовательных программ для современных векторно-конвейерных и массивно-параллельных суперЭВМ, а также исследования в области методов и средств автоматического или автоматизированного конструирования прикладных параллельных программ для мультикомпыотеров, проводимые под руководством В.Э. Малышкина. В этой области разработаны теоретические основы сборочной технологии параллельного программирования, ориентированные в первую очередь на параллельную реализацию численных моделей большого размера в физике. Также следует упомянуть такие перспективные направления, как параллельное программирование с помощью "типовых алгоритмических структур"и динамическое управление загрузкой суперкомпьютеров. Но несмотря на значительные успехи в развитии технологии параллельного программирования, область специфицирования взаимодействий 1 пока что является недостаточно формализованной. В качестве иллюстрации достаточно привести классическую задачу об обедающих философах, для программирования которой приходится использовать такие средства, как MPI, PVM и.т.д., в которых необходимо явно указывать способ и стороны взаимодействия, что может привести к скрытым ошибкам, выявление которых сравнимо по сложности с самим программированием. С другой стороны формальные средства спецификации распределенных систем (CCS,SDL,ceTH Петри) уже имеют достаточную базу для описания параллельных программ и обнаружения ошибок в этих описаниях.

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

В работе используется формальный аппарат сетей Петри, который на протяжении длительного времени применялся и развивался для описания и изучения структурной динамики программ. В этом направлении было предложено и реализовано множество расширений сетей Петри. Например, в работах Котова В.Е. определены регулярные и иерархические сети Петри, Куртом Енсеном определены раскрашенные сети Петри, а Айком Бэстом проведены исследования, завершенные созданием алгебры сетей Петри, на основе которой разработан язык спецификации конкурирующих процессов. В последнее десятилетие в России. в коллективе Непомнящего В.А., реализованы методы трансляции и анализа параллельных алгоритмов, выполненных на языке Estelle и SDL в терминах временных раскрашенных сетей Петри, а в трудах Соколова В.А. и Ломазовой И.А. исследуются свойства рекурсивных параллельных программ.

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

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

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

- определении операций синхронизации цветных сетей Петри, позволяющих передачу данных между синхронизируемыми сетями;

2) разработать схему трансляции параллельных программ, описанных сетями Петри, в исполняемое представление;

3) разработать автоматизированную среду построения и трансляции параллельных программ в терминах сетей Петри.

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

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

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

Материалы диссертационной работы использовались в учебном процессе на кафедре программного обеспечения ЭВМ Института математики и компьютерных наук ДВГУ, в рамках лекционных курсов по архитектуре операционных и вычислительных систем, а также курса по параллельным вычислительными методам. Предложенные методы и инструментальные средства внедрены в Дальневосточном государственном университете и Институте вычислительной математики РАН. что подтверждено соответствующими документами.

• Связь с планами отраслей наук и народного хозяйства. Представленные в диссертации исследования проводились в рамках следующих программ:

1. В рамках научно-исследовательских тем Института автоматики и процессов управления ДВО РАН:

Формальные методы и средства разработки программного обеспечения распределенных вычислительных систем", N гос. регистрации 01.9.50 00G912;

Методы и средства технологии автоматизированной обработки знаний, специфицирования и анализа программного обеспечения распределенных вычислительных систем, обработки и визуализации графической информации с применением параллельных вычислений", N гос. регистрации № 01.99.00 05772.

2. В рамках проектов Российского фонда фундаментальных исследований:

Основы композициональной теории сетей Петри", грант 93013 17372;

Композициональпые методы разработки сетевых протоколов", грант 96-01-00177;

Построение сред разработки параллельных программ на основе сетей Петри для вычислительных кластеров и многомашинных комплексов", грант 01 01 9G903;

3. В рамках подпрограммы "Перспективные информационные тех-нологиии"федеральной целевой НТ программы "Исследования и разработки по приоритетным направлениям развития науки и техники гражданского назначения" проект №0201.01.225. Миннауки РФ "Разработка средств повышения эффективности программ для вычислительных систем параллельной архитектуры."

• Апробация работы. Основные научные и практические результаты работы докладывались и обсуждались на следующих международных и отечественных конференциях: международные конференции: международная конференция "Организационные структуры, управление и моделирование в бизнес системах и секторах" (Каунас,Литва, 1998г.), "Инженерные теории построения программного обеспечения" (Марктобердорф, Германия, 2000г.), "Анализ и надёжность систем"(Марктобердорф, Германия, 2001г.), "Параллельные вычислительные технологии "(Новосибирск, Россия, 2001); всероссийские конференции, школы и семинары: "Высокопроизводительные вычисления и их приложения"(Москва, 2000г.), Третий сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ-98 Новосибирск, 1998), Дальневосточная математическая школа имени академика Золотова (Владивосток, 1998, 1999, 2000г.); семинары Института автоматики и процессов управления ДВО РАН в 199G 2001 гг; объединенные семинары факультета компьютерных наук ИМиКН ДВГУ и отдела экспертных систем ИАПУ ДВО РАН в 2001 гг.

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

Основные выводы, результаты и рекомендации, полученные в диссертации:

1. Разработан язык "сети Петри для программирования", совмещающий описание структуры программы и параллельного алгоритма в терминах цветных сетей Петри и описание типов данных, методов преобразования данных в терминах императивных языков програмирования. Конкретный синтаксис сетей Петри для программирования реализован на основе XML.

2. Разработана схема транслирования параллельных программ, описанных сетями Петри, в исполняемое процессами традиционной архитектуры представление программы:

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

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

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

Заключение

1. Анисимов Н.А. Формализация сервиса вычислительной сети на основе алгебраического подхода /'/' Одиннадцатый Всесоюзный семинар по вычислительным сетям (Рига, октябрь 1986), - М.;Рига: ВИНИТИ, 198G, ч.2, с.14-19.

2. Анисимов Н.А. Алгебра структур протоколов на основе теории сетей Петри // Автоматика и вычислительная техника, 1987, N 1, с.9-15.

3. Анисимов Н.А. Рекурсивное определение протоколов на основе теории сетей Петри // Автоматика и вычислительная техника, 1987, N 5, с.З-7.

4. Анисимов Н.А. Формальная модель для разработки и формального описания протоколов // Автоматика и вычислительная техника, 1988, N G, с.3-10.

5. Анисимов Н.А., Бузин A.M., Голенков Е.А. Технологические принципы разработки программного обеспечения информационно вычислительных сетей // Управляющие системы и машины, 1988, N 4, с.86-91.

6. Анисимов Н.А. Рекурсивное определение иерархии протоколов на основе сетей Петри // Четырнадцатая Всесоюзная школа семинар по вычислительным сетям (Минск, 1989), - М.; Минск: ВИНИТИ, 1989, ч.2, с.101-106.

7. Анисимов Н.А., Голенков Е.А., Кишинский К.П., Коваленко А.А. Графический LOTOS на базе сетей Петри и средства его обработки // Технология программирования 90-х / Тез. докл. межд. конф. (Киев, 14-17 мая, 1991), Киев: ИК АН УССР, 1991, с.97-98.

8. Анисимов Н.А., Коваленко А.А., Поступальский П.А., Симанчук А.С. Графический редактор протоколов сетей ЭВМ на базе сетей Петри / / Семнадцатая Международная школа семинар по вычислительным сетям (Алма-Ата, 1992), М.; Алма-Ата: ВИНИТИ, 1992, ч.2, с.З 8.

9. Анисимов Н.А., Мельников В.Е., Тарасов Г.В., Харитонов Д.И., Хро-ленко П.В., Ваулин Ю.В., Инзарцев А.Ф., Щербатюк А.Ф. Использование графического языка для формирования программы задания АПР. Сборник Морские технологии, ИПМТ ДВО РАН. 1998.

10. Анисимов Н.А.,Голенков Е.А., Харитонов Д.И. Композициональный подход к разработке параллельных и распределенных систем на основе сетей Петри. "Программирование"}^, 2001г, стр. 30-43.

11. Ахо А., Сети Р., Ульман Д., Компиляторы/ Принципы, технологии, инструменты, М.: Вильяме, 2001.

12. А. С. Антонов, Вл. В. Воеводин. Эффективная адаптация последовательных программ для современных векторно-конвейерпых и массивно-параллельных Супер-ЭВМ.// Программирование, 1996 г. № 4. С. 37-51.

13. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск: Наука, 1990, С.252

14. Бандман O.J1. Проверка корректности сетевых протоколов с помощью сетей Петри. /'/' Автоматика и вычислительная техника, 1986, N 6, с.82-91.

15. Д. Ван Тассел, Стиль, разработка, эффективность, отладка и испытание программ, М.: Мир, 1985.

16. Вайнгартен Ф., Трансляция языков программирования, М.: Мир, 1977.

17. Вальковский В.А., Малышкин В.Э. Отв.ред. В.Е.Котов. Синтез параллельных программ и систем на вычислительных моделях Дополнительное название В надзаг.: АН СССР Сиб.отд.ВЦ Издательство Новосибирск: Наука Год издания 1988

18. Воеводин Вл.В., Теория и практика исследования параллелизма последовательных программ. Программирование. 1992. N 3. С. 38-53.

19. Воеводин Вл.В., Математические модели и методы в параллельных процессах, М.: Гл. ред. физ.-мат. лит., 198С.

20. Вольфегаген В.Э., Конструкции языков программирования, М.: АО "Центр ЮрИнфоР", 2001.

21. Голенков Е.А., Левин В.А., Тарасов Г.В., Харитонов Д.И. Трансляция параллельных программ , описанных сетями Петри. / Материалы всероссийской научной конференции "Высокопроизводительные вычисления и их приложения". Москва, 2000г.

22. Гудман С., Хидет^иеми С., Введение в разработку и анализ алгоритмов, М.: Мир, 1981.

23. Ершов А.П. Комплексное развитие системного программного обеспечения: постановка проблемы. Новосибирск, 1983. 20 с. (Препр./АН СССР, ВЦ СО, N 469).

24. Зайцев С.С., Кравцунов М.И., Ротанов С.В. Сервис открытых информационно вычислительных сетей: Справочник. - М.: Радио и связь, 1990. - 240 с.

25. Кормен Т., Лейзерсон Ч., Риверс Р., Алгоритмы/ построение и анализ. М.: МЦМНО, 1999.

26. Котов В.Е. Алгебра регулярных сетей Петри. // Кибернетика, 1980, N 5, с.10-18.

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

28. Котов В.Е., Сабельфельд В.Н. Теория схем программ. М., Наука, 1989.

29. Ломазова И.А. Моделирование мультиагентных динамических систем вложенными сетями Петри // Программные системы: Теоретические основы и приложения. М.: Наука. Физматлит, 1999. С. 143-156.

30. Ломазова И.А. Некоторые алгоритмы анализа для многоуровневых вложенных сетей Петри /'/' Известия РАН. Теория и системы управления, 2000, 6. С. 134-143.

31. Ломазова И.А. Рекурсивные вложенные сети Петри: анализ семантических свойств и выразительность // Программирование, 2001, 4. С. 21-35.

32. Майерс Г., Надёжность программного обеспечения, М.: Мир, 1980.

33. Мельников В.Е., Харитонов Д.И. О применении цветных точек доступа для специфицирования атономного объекта. В кн.: Третий сибирский конгресс по прикладной и индустриальной математике ИНПРИМ-98, Новосибирск, 1998.

34. Непейвода Н.Н., Прикладная логика, Новосибирск: Издательство Новосибирского университета, 2000.

35. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ, -М.: Радио и связь, 1988.

36. Непомнящий В.А., Ануреев И.С., Михайлов И.Н., Промский А.В. На пути к верификации С-программ. Язык C-light. /7 Тезисы докладов. Конференция, посвященная 90-летию со дня рождения Алексея Андреевича Ляпунова. Новоссибирск. 2001 г.

37. Себеста Р.У., Основные концепции языков программирования, М.: Вильяме, 2001.

38. Советов Б.Я., Яковлев С.А. Построение сетей интегрального обслуживания. Л: Машиностроение, 1990.

39. Соколов В.А., Кушнаренко О.Б. Рекурсивно-параллельное программирование и сети Петри: моделирование, анализ и верификация программ /'/' Моделирование и анализ информационных систем", N2. Ярославль, Изд-во ЯрГУ, 1994. С. 91 97.

40. Таль А.А., Юдицкий С.А. Иерархия и параллелизм в сетях Петри I, II //Автоматики и телемеханика, 1982, N 7, с. 113-122, N 9, с.83-88.

41. Таха Х.А., Введение в исследование операций, М.: Вильяме, 2001.

42. Хоар Ч. Взаимодействующие последовательные процессы, М.: Мир, 1989. - 264 с.

43. Якубайтис Э.А. Архитектура вычислительных сетей. М.: Статистика, 1980. - 279 с.

44. Якубайтис Э.А. Информационно-вычислительные сети. М.: Финансы и статистика, 1984. - 232 с.

45. N.A.Anisimov. A Notion of Petri Net Entity for Communication Protocol Design (Institute for Automation and Control Processes, 1989).

46. N. A. Anisimov. A Petri Net Entity as a Formal Model for LOTOS, a Specification Language for Distributed and Concurrent Systems, in: Parallel Computing Technologies, ed. N. N. Mirenkov (World Scientific, 1991), 440-450.

47. N. A. Anisimov. An Algebra of Regular Macronets for Formal Specification of Communication Protocols. Computers and Artificial Intelligence, 10 (1991), 541 5G0.

48. N. A. Anisimov, A. A. Kovalenko, P. A. Postupalski,A. S. Simancuk, A Graphical Petri Net Based Editor for Visualization of Distributed and Parallel Systems. Lecture Notes in Computer Science, 631 (Springer-Verlag, 1992) 847-848.

49. N. A. Anisimov. A Disabling of Event Structures, in: PARLE'93, Parallel Architectures and Language Europe, ed. A. Bodem M. Reeve, G. Wolf, Lecture Notes in Computer Science, 694 (Springer-Verlag, 1993) 724728.

50. N.A.Anisimov, A.A.Kovalenko, P.A.Postupalski,. Compositional Petri Net Environment, in: Proc. of the 1994 IEEE Symposium on Emerging Technologies к Factory Automation: ETFA '94, November 6-10, 1994, Tokyo, Japan, 420-427.

51. Anisimov N.A., Kovalenko A.A., Towards Petri Net Calculi based on Synchronization via Places, Proc. of the 1995 IEEE Symposium on Parallel Algorithms/Architecture Synthesis, March 15-17, 1995, Aizu. Japan, 264-270.

52. Anisimov N., Koutny M., On Compositionality and Petri Nets in Protocol Engineering, Protocol Specification, Testing and Verification XV, P.Dembiniski, M.Sredniawa eds. (Chapman к Hall, 1995), pp.71-86

53. N.Anisimov, M.Koutny, Compositional Petri Nets in Protocol Engineering. Technical Report, 1997.

54. Anisimov N.A., Kharitonov D.I., Melnikov V.E. Design of Program for AUV using Graphical Language Environment. In: Proc. Special

55. Conference Organizational Structures, Managment, Simulation of Buisiness Sectors and Systems, the International Federation of Operational Research Societies, September 10-12, 1998, Kaunas, Lithuania.

56. J.C.M. Baeten, W.P. Weijland, Process Algebra,. Cambridge Tracts in Theoretical Computer Science, 18, Cambridge University Press, 1990.

57. J. С. M. Baeten, J. A. Bergstra, Non Interliving Process Algebra, in: Proc. CONCUR'93, ed. E. Best, Lecture Notes in Computer Science, 715 (Springer-Verlag, 1993) 308-323.

58. K. A. Bartlett, R. A. Scantlebury, and P. T. Wilkinson, A Note on Reliable Full Duplex Transmission over Half Duplex Lines, Communication of the ACM, 12 (1969) 260-265.

59. Bjorn Victor, Faron Moller, The Mobility Workbench. A Tool for the ж-Calculus.

60. G. Coulouris, J.Dollimore, T.Kinderberg, Distributed systems, Addison-Wesley, London, 1994

61. R. De Nicola, Extensional Equivalences for Transition Systems, Acta, Injormatica, vol. 24, 1987, pp.211-237.

62. J.-C.Fernandez, An Implementation of an Efficient Algorithm for Bisimulation Equivalence, Science of Computer Programming, vol.13, 1989/90.

63. A.Geist, A.Beguelin, J.Dongarra, W.Jiang, R.Manchek, V.Sunderam, Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing., MIT press, 1994.

64. R.J.Van Glabbeek, The Linear Time — Branching Time Spectrum, in: CONCUR'90, Theories of Concurrency: Unification and Extension, ed. J.C.M.Baeten, J.W.Klop, Lecture Notes in Computer Science, vol.458, Springer-Verlag, 1990.

65. S.Gorlatch. Send-Recv Considered Harmful? Myths and Truths about Parallel Programming, in: Parallel Computing Technologies, ed. V.Malyshkin (Springer, 2001), P.243-257.

66. M.Hillerstrom, Verification of CCS-processes, M. Sc. Thesisis, Computer Science Department, Aalborg University, Denmark, 1987.

67. C.A.R.Hoare, Communicating Sequental Processes. Printice-Hall, 1985.

68. D.Hunter, C.Cagle, D.Gibbons, N.Ozu, J.Pinnock, P.Spencer, Begining XML, Wrox Press, USA, 2000.

69. P.Jancar, Decidability Questions for Bisimulation of Petri Nets and Some Related Problems, Report ECS-LFCS-93-2C1, University of Edinburg, 1993, 12 p.

70. R. Janicki, M. Koutny, On Some Implementation of Optimal Simulations. Proceedings of Computer-Aided Verification'90, Lecture Notes in Computer Sciences, 254, Springer Verlag, 1991, pp.166-175.

71. K. Jensen, G. Rozenberg (Eds.) High-level Petri Nets. Theory and Application, Springer-Verlag, 1991, 724 p.

72. P.C.Kanellakis, S.C.Smolka, CCS Expressions, Finite State Processes and Three Problems of Equivalence. In: Proc. of the Second ACM Symposium on Principles of Distributed Computing, 1983.

73. Kharitonov D.I., Visualization of behavior of compositional Petri Nets Proc. of the XXII-nd Far-Eastern Mathematical School-Seminar on Mathematical Modelling & Numerical Analysis, Nakhodka, September 310, 1996.

74. Golenkov E.A., Sokolov A.S., Tarasov G.V. and D.I. Kharitonov "Experimental Version of Parallel Programs Translator from Petri Nets to С ", 67th International Conference, PaCT 2001, Novosibirsk, RUSSIA, September 2001,Preceedings, pp. 226-231.

75. H.P.Korver, The Current State og Bisimulation Tools, Report P9101, Programming Research Group, University of Amsterdam, 1991, 28 p.

76. K.G. Larsen, Context-Dependent Bisimulation Between Processes, Ph.D Thesisis, University of Edinburg, 1986.

77. T.G.Lewis, Foundations of parallel programming. IEEE Computer Society Press, USA, 1993.

78. R.Paige, R.E.Tarjan, Three Partitioning Refinement Algorithms. SIAM Journal of Computing, Vol.16, No.6, 1987, pp.973-989.

79. J.L.Peterson. Petri Net Theory and the Modelling of Systems, Prentice-Hall Inc., 1981

80. Pomello, G. Rosenberg, and C. Simone, A Survey of Equivalence Notions for Net Based Systems, in: Advances in Petri Nets 1992, ed.G. Rozenberg, Lecture Notes in Computer Science, 609, Spririgcr-Verlag, 1992.

81. W.Reisig. Petri Nets: An Introduction. EATCS Monograph on Theoretical Computer Science (Springer-Verlag, 1985).

82. C.Sunshine. A Formal Techniques for Protocol Specification and Verification. Computer, Vol.12, 1979, pp.20 27.

83. E. Best, F. De Cindio, and R. Hopkins, DEMON an ESPRIT Basic Research Action (No.3148), EATCS Bulletin No.41 (1990) 87-103.

84. E.Best, R.Devillers, A.Kiehn, and L.Pomello, Concurrent Bisimulations in Petri Nets. Acta Informatica, vol. 28, 1991, pp.231-261.

85. E. Best, R. Devillers, J. G. Hall, The Box Calculus: a New Causal Algebra with Multi-label Communication, in: Advances in Petri Nets 1992, ed.G. Rozenberg, Lecture Notes in Computer Science, 609 (Springer-Verlag, 1992) 21-69.

86. E. Best (ed), First Year Results of lite Esprit Basic Research WG 6067 CALIBAN (Causal Calculi Based on Nets) Hildesheimer Informatic Berichte 11/93 (Universitat Hildesheim, 1993)

87. E. Best, J. Esparza, Model Checking of Persistent Petri Nets, 35-52

88. E. Best, R. Devillers, M. Koutny, Petri Net Algebra, Springer-Verlag, 2001

89. W.Brauer, W.Reisig, G.Rozenberg (eds). Petri Nets. Part I and II. Proc. of an Advanced Course, Bad Honnef. Lecture Notes in Computer Science, vol.254/255, Springer-Verlag, 1987

90. G. V. Bochmann, C. A. Sunshine. Formal Methods in Communication Protocol Design. IEEE Trans. Commun. COM-28 (1980) 624 631.

91. G. Bochmann, Usage of Protocol Development Tools: The Results of a Survey, in: Protocol Specification, Testing, and Verification, VIP Proc. of the IFIP WG 6.1 7th International Symposium, eds. H. Rudin, С. H. West (North-Holland, 1987) 139-161.

92. Т. Bolognesi, Е. Brinksma. Introduction to the ISO Specification Language LOTOS. Computer Network and ISDN Systems 14 (1987), 2529.

93. G.Boocli, Object oriented design with applications, Benjamin/Cummings Publising Co., USA, 1991.

94. S. Budkowski, P. Dembinski, An Introduction to Estelle: A Specification Language for Distributed Systems. Computer Network and ISDN Systems 14 (1987) 3-23.

95. R. H. Cambell, A. N. Habermann, The Specification of Processes Synchronization by Path Expressions. Lecture Notes in Computer Science 16 (Springer Verlag, 1974) 89 102.

96. R.Chandra, R.Menon, L.Dagum, D.Kohr, D.Maydan, J.McDonald, Parallel Programming in OpenMP, Morgan Kaufmann Publishers, 2000.

97. R. Cleaveland, J. Parrow, S. Steffen, A Semantic-Based Tools for the Verivication of Finite-State Systems, in Proc. IFIP Symposium on protocol Specofication, Texting and Verification 287 302 Amsterdam, 1990.

98. R. Cleaveland, On Automatically Distinguished Inequivalent Processes. in Proc. Workshop on Computer-Aided Verification, DIMACS technical report 90-31, 1990.

99. J. D. Day, H. Zimmermann. The OSI Reference Model. Proceedings IEEE 71 (1983) 1334 1340.

100. P. Degano, R. De Nicola, and U. Montanari, A Distibutional Semantics for CCS based on Condition/Event Systems. Acta Informatica, 26 (1988) 59-91.

101. M.Diaz. Modeling and Analysis of Communication and Cooperation Protocols Using Petri Net Based Models, Computer Networks 6 (1982) 419-441.

102. H.Ehrig, B.Mahr, Fundamentals of Algebraic Specifications I (Springer-Verlag, 1985).

103. Espiau В., Simon D., Kapellos K. Formal Verification of Missions and, Tasks. Workshop: Undersea Robotics and Intelligent Control, lisboa, Portugal March 2-3, 1995.

104. U.Goltz and A.Mycroft, On the Relationship of CCS and Petri Nets. Lecture Notes in Computer Science, 172 (Springer Verlag, 1984) 196 208.

105. U.Goltz, A Class of CCS Programs Representable by Finite Petri Nets. Lecture Notes in Computer Science, 324 (Springer-Verlag, 1988) 339-350.

106. J. F. Groote, F. W. Vaandrager. An efficient algorithm for branching bissimulation and stuttering equivalence. In Proceedings 17th IС ALP, Warwick, LNCS, vol. 443, 626-638, 1990.

107. Haddad S., Poitrenand D. Theoretical aspects of recursive Petri nets /'/ Proc. ATPN'99, LNCS 1639. Springer, 1999. P. 228-247.

108. C.A.R.Hoare, Formal Methods in Computer System Design, CERN School of Computing, Oxford, UK, 15-26, CERN Set. Rept. 6 (1989) 1-7.

109. G.Holzmann, Design and Validation of Computer Protocols. (Printice-Hall, 1991) p.500

110. ISO, IS 7498. Information Processing Systems Open Systems Interconnection - Basic Reference model, 1983.

111. ISO, IS 9074, Information Processing Systems Open Systems Interconnection "Estelle (Formal Description Technique based on an Extended State Transition Model)", (1988) p.180.

112. K.Jensenl, Coloured Petri Nets/, In: A.Rodony, G.Rozenberg (eds.): Application and Theory of Petri Nets? Informatik-Facliberichte Vo.66, Springer-Verlag 1983, 166-180.

113. K.Jensen et al, Design/CPN: A Tool Supporting Coloured Petri Nets, User Manual, Meta Software Corporation, 150 Cambridge Park Drive, Cambridge MA 02140 (1988).

114. K.Jensen. Coloured Petri nets: Basic Concepts, analysis methods and practical use. Berlin a.o.: Springer-Verlag, 1996. - Vol.2. Analysis methods.

115. K. G. Larsen, Efficient Local Correctness Checking. In Proceedings of Fourth International Workshop on Computer Aided Verification Methods, Montreal, June 1992. Lecture Notes In Computer Science, Springer Verlag, 663, 1992.

116. P.E.Lauer, R.H.Campbel. Formal Semantics of a Class of High-Level Primitives for Coordinating Concurrent Processes. Acta Inform,atica 5 (1975) 297-332.

117. R.Loogen and U.Goltz, A Non-Interleaving Semantic Model for Nondeterministic Concurrent Processes. Aachener Informatik-Derichte 87-15, (RWTH Aachen, 1987).

118. N.A.Lynch, Distributed Algorithms, Morgan Kaufmann Publichers Inc, California, USA, 1996

119. M.Snir, S.Otto, S.Huss-Lederman, D.Walker, J.Dongarra, MPI: The Complete Reference. MIT press, 1996.

120. R.Milner, A Calculus for Communication Systems. Lecture Notes in Computer Science, 92 (Springer-Verlag, 1980) p.170.

121. R.Milner. Communication and Concurrency (Prentice-Hall International, 1989).

122. S.Mullender, Distributed systems, Addison-Wesley, New York, 1993

123. E.-R.Olderog, Operational Petri Nets Semantics for CCSP. in: Advances in Petri Nets 1987, ed. G. Rozenberg, Lecture Notes in Computer Science, 266 (Springer-Verlag, 1987) 196-233.

124. B.Pehrson. Protocol Verification for OSI. Computer Networks and ISDN Systems 18 (1989/90) 185-201.140141142143144145146147

125. K.A.Petri, Kommunication mit Automaten, Schriften des Rheinish, Westfalischen Institutes fur Instrumentelle Mathematik and der Universitat Bonn (1962).

126. Prabhakaran В., Raghavan S., Synchronization Models Multimedia Presentations With User Interaction, ACM Multimedia '93 , pp 157-166, California, USA, June 1993.

127. C.V.Ramamoorthy, Y.Yaw, and W.T.Tsai, A Petri Net Reduction Algorithm for Protocol Analysis, in: Proc. ACM SIGCOM'86 Symp Computer Communication Review 16 (1986) 157-166.

128. R.Saraco, P.A.J.Tilanus, CCITT SDL: Overview of the Language and its Applications, Computer Networks and ISDN Systems 13 (1987) 65-74.

129. A.S.Tanenbaum, Modern Operating System, Prentice Hall Inc, New Jersey, 1992

130. S.T.Vuong, D.D.Cowan. A Decomposition Method for the Validation of Structured Protocols, in: Proc. Conf. INFOCOM'82 (1982) 209-220.

131. Meeting on XML/SGML based Interchange Formats for Petri Nets. Web page available on http://www.daimi.au.dk/pn2000/Interchange.

132. P.Ward and S.Mellor, Structured development for real-time systems, Yourdon Press, USA, 1985.

133. H.Zimmermann. OSI Reference Model the ISO Model of Architecture for Open Systems Interconnection. IEEE Trans. Com,тип. COM—28 (1980) 425-432.