Algorytm równoległy wyznaczania blokad i pułapek w sieciach Petriego

• Autorzy: Węgrzyn A.

Warianty tytułu

EN

Parallel algorithm for computation of deadlocks and traps in Petri nets

• Konferencja: Konferencja Informatyka - Sztuka czy Rzemiosło( 19-22 czerwca 2006; Złotniki Lubanskie; Polska)
• Języki publikacji: PL

Abstrakty

PL

W artykule została przedstawiona metoda równoległa wyznaczania blokad i pułapek w sieciach Petriego. Metoda ta bazuje na sekwencyjnym algorytmie obliczania zbiorów blokad i pułapek opisanym w [15]. Sekwencyjna metoda ma złożoność obliczeniową wykładniczą, dlatego istotna jest modyfikacja algorytmu w ten sposób, aby czas obliczania zdecydowanie zredukować. Rozpatrywana metoda wykorzystuje algorytm Thelena [13] - wyznaczania implikantów prostych na podstawie generowania i przeszukiwania drzewa.

EN

In the paper the method of computation all deadlocks and traps in the Petri net is presented. This method is based on Thelen method [13] and it was proposed in [15]. Methods of calculation of all deadlocks and traps in Petri nets are very time consuming. Therefore it is very important to optimize of a computation. The parallel computation method for the time reduction is proposed. Experimental results of presented method are discussed, as well.

Słowa kluczowe

PL

sieci Petriego; analiza; blokady; pułapki; klaster

EN

Petri nets; analysis; deadlock; traps; cluster

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2006
• Tom: R. 52, nr 6 bis
• Strony: 23--25
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Węgrzyn A.

• Instytut Inormatyki i Elektroniki, Uniwesytet Zielonogórski,

Bibliografia

• [1] E. R. Boer, T. Murata, Generating Basis Siphons and Traps of Petri Nets using the Sign Incidence Matrix, IEEE Transaction on Circuits and Systems, Fundamental Theory and Applications, Vol. 41, 1994.
• [2] A. Barak, O. La’adan. The MOSIX Multicomputer Operating System for High Performance Cluster Computing. Journal of Future Generation Computer Systems, 13(4-5):361–372, March 1998.
• [3] K. Barkaoui, M. Minoux, “A polynomial-time graph algorithm to decide liveness of some basic classes of bounded Petri nets”, Lecture Notes in Computer Science, Springer Verlag, Berlin, Vol. 616, 1992, pp. 62-75
• [4] C. Girault, R. Valk, Petri nets for systems engineering, Springer-Verlag Berlin Heilderberg, 2003.
• [5] A. Karatkevich, M.Adamski, M.Węgrzyn, “Rapid correctness analysis for sequential function chart”, 45th International Scientific Coloquium, 04-06.10.2000, Ilmenau, ss. 679-684, 2000
• [6] E.Koтoв, Сети Петри, М.: Наука, Главная редакция физико-математической литературы, 1984.
• [7] H. J. Mathony, Universal logic design algorithm and its application the synthesis of two-level switching circuits, IEE Proceedings, Vol. 136, Pt.E, No. 3, 1989.
• [8] M. Minoux, K. Barkaoui, Deadlocks and traps in Petri nets as a Hornsatisfability solutions and some related polynomially solvable problems Discrete Applied Mathematics, Elsevier Science Publishers (North Hol-land), Vol. 29, 1990, pp. 195-210
• [9] T. Murata, Petri Nets: Properties, Analysis and Applications, Proceedings of the IEEE, Vol. 77, No. 4, ss. 541-580, April 1989
• [10] J. L. Peterson, Petri Net Theory and The Modeling of Systems, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1981
• [11] W. Reisig, Sieci Petriego. Wprowadzenie, Wydawnictwa Naukowo-Techniczne, Warszawa, 1988
• [12] P. H. Starke, Sieci Petri - podstawy, zastosowania, teoria, PWN, Warszawa, 1987
• [13] B. Thelen, Investigations of algorithms for computer-aided logic design of digital circuits, PhD dissertation, ITIV, Univ. of Karlsruhe, 1981
• [14] R. Valette, “Analysis of Petri nets by stepwise refinements”, Journal of Computer and System Science, Vol. 18, ss. 35-36, 1979
• [15] A. Węgrzyn, Symboliczna analiza układów sterowania z wykorzystaniem wybranych metod analizy sieci Petriego, Rozprawa doktorska, Politechnika Warszawska, 2003