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

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.

---

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