Usage of Hypergraph Theory in Decomposition of Concurrent Automata

• Autorzy: Wiśniewska M. , Wiśniewski R. , Adamski M.

Warianty tytułu

PL

Równoległa dekompozycja automatów współbieżnych z wykorzystaniem hipergrafów

• Języki publikacji: PL

Abstrakty

PL

Hipergrafy są dogodnym narzędziem matematycznym, umożliwiającym zwartą reprezentację relacji współbieżności lub relacji następstwa w przestrzeni stanów lokalnych cyfrowego automatu współbieżnego. Z tego względu zaproponowano ich wykorzystanie w projektowaniu rekonfigurowanego sterownika logicznego. Hipergraf pozwala w przejrzysty sposób opisywać nie tylko relację współbieżności miedzy stanami lokalnymi, lecz także poglądowo przedstawia ich przynależność do tego samego stanu globalnego. Ułatwia to dekompozycję diagramu SFC lub równoważnej mu interpretowanej sieci Petriego sterowania, na moduły, na przykład szeregowe lub równoległe. W artykule przedstawiono sposób dekompozycji równoległej cyfrowych układów współbieżnych, opisanych z wykorzystaniem sieci Petriego przeprowadzanej za pośrednictwem dekompozycji hipergrafów. Celem dekompozycji jest podział rekonfigurowanego sterownika logicznego na współbieżne moduły, z których każdy może być optymalizowany i syntezowany wykorzystaniem klasycznej teorii automatów cyfrowych. Sposób dekompozycji sieci Petriego z wykorzystaniem kolorowania grafu współbieżności lub wyszukiwania pokrycia klikami dopełnienia grafu współbieżności (a tym samym grafu niewspółbieżności, czyli grafu następstwa), jest już znany. Opracowując nową metodę, wzięto pod uwagę fakt, że hipergraf współbieżności miejsc sieci Petriego oprócz informacji o relacji między każdą parą miejsc przekazuje dodatkowe dane o istniejących w nim klikach, odpowiadających wcześniej wyznaczonym stanom globalnym. Metoda dekompozycji równoległej automatów współbieżnych zostanie zilustrowana przykładem. Pokazane zostaną niezbędne kroki, jakie są niezbędne do wykonania podziału sterownika logicznego z wykorzystaniem hipergrafów.

EN

Hypergraphs are useful mathematical tools for a compact representation of relations among local states in the state space of distributed, concurrent control automata (concurrent state machines). Therefore, application of hypergraphs is more efficient and intuitive than traditional solutions. For this reason we propose their application during the design process of reconfigurable logic controllers. It makes it possible to decompose an SFC or a related control interpreted Petri net into parallel or sequentially

Słowa kluczowe

PL

transwersala; stany lokalne automatu; sieć Petriego

EN

hypergraph; transversals; local states of automata; Petri nets

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2007
• Tom: R. 53, nr 7
• Strony: 66--68
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Wiśniewska M.

autor

Wiśniewski R.

autor

Adamski M.

• Instytut Informatyki i Elektyroniki, Uniwersytet Zielonogórski,

Bibliografia

• [1] G. De Micheli: Synteza i optymalizacja układów cyfrowych. Wydawnictwo Naukowo-Techniczne, Warszawa 1998.
• [2] C. Berge: Graphs and Hypergraph. North-Hols.r Mathematical Library, Amsterdam 1976.
• [3] T. Luba: Synteza układów Iogicznych. Wyższa Szkoła Informatyki Stosowanej i Zarządzania, Warszawa 2000.
• [4] Z. Banaszak, J. Kuś, M. Adamski: Sieć Petriego. Modelowanie, sterowanie i synteza systemów dyskretnych. Wydawnictwo Wyższej Szkoły Inżynierskiej, Zielona Góra 1993.
• [5] R. David, H. Alla: Petri Nets & Grafcet. Tools for modelling discrete event systems. Prentice Hall, New York, 1992.
• [6] M. Adamski, A. Karatkievich, M. Wegrzyn (ed.): Design of Embeded Control Systems. Springer Science (USA), 2005.
• [7] K. Biliński, M. Adamski, J.M. Saul, E.L. Dagless: Petri-net-based algorithms for parallel-controller synthesis. IEE Proceedings - Computers and Digital Techniques, 1994, Vol. 141, no 6, s. 405-412.
• [8] M. Adamski, M. Chodań: Modelowanie układów sterowania dyskretnego z wykorzystaniem sieci SFC. Wydawnictwo Politechniki Zielonogórskiej, Zielona Góra, 2000.