Automatyczny system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów

• Autorzy: Wiśniewska M.

Warianty tytułu

EN

CAD system for automatic decomposition of discrete systems based on hypergraphs

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowany został autorski system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów. Narzędzie Hippo składa się ze zbioru bibliotek, realizujących najważniejsze operacje z zakresu teorii grafów i hipergrafów (m. in. kolorowanie, pokrycie, dopełnienie, dualizm, itd.), które zostały zrealizowane pod kątem ich zastosowania w dekompozycji systemów dyskretnych. Głównym zadaniem systemu jest usprawnienie oraz automatyzacja procesu dekompozycji systemów dyskretnych stosowanych m.in. w projektowaniu zaawansowanych układów cyfrowych (redukcja rozmiaru pamięci, selekcja klas kompatybilności, minimalizacja funkcji logicznych, dekompozycja automatów cyfrowych). Opracowany system Hippo umożliwia przeprowadzenie automatycznego procesu dekompozycji z zastosowaniem różnych algorytmów (zarówno grafowych, jak i hipergrafowych), w efekcie pozwalając wybrać użytkownikowi najkorzystniejsze rozwiązanie.

EN

In the paper a dedicated CAD system Hippo for automatic decomposition of discrete systems is presented. The tool consists of a set of libraries. Each library was designed as a separate module to solve the particular problem from the field of the graph and hypergraph theories (among others: vertex coloring, vertex covering, transversal computation, dualism, computation of the graph and hypergraph complement). The main task of the system is to improve the process of decomposition of discrete systems (for example: reduction of the microinstruction length, selection of the compatibility classes, decomposition of concurrent automata). The Hippo system consists of eight main modules:- complement -calculation of graph/hypergraph complement;- coloring - five methods of coloring of graph and hypergraph (four greedy and one backtracking);- transversal - four methods of transversals computation (fast reduction algorithm, greedy, backtracking, mixed fast reduction and greedy);- exact transversals - the calculation of the exact transversals is based on the Knuth DLX algorithm, the main advantage of such a solution is polynomial computational time in case of exact hypergraphs;- dualism (only for hypergraphs) - calculates the dual hypergraph;- converting graph to hypergraph;- converting hypergraph to graph;- conversion of the graph/hypergraph description to the TeX format.In the paper particular libraries are described in detail. Moreover, the stand-alone application (Hippo) is shown. Finally, an example of automatic decomposition of the discrete system is presented. All steps and required operations are described.

Słowa kluczowe

PL

graf; hipergraf; dekompozycja systemów dyskretnych; projektowanie wspomagane komputerowo; dekompozycja automatyczna; Hippo; sieć Petriego

EN

graph; hypergraph; decomposition of discrete system; CAD system; Hippo; automatic decomposition; Petri Nets

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 7
• Strony: 726--728
• Opis fizyczny: Bibliogr. 9 poz., rys.,

Twórcy

autor

Wiśniewska M.

• Uniwersytet Zielonogórski, ul. Licealna 9, 65-417 Zielona Góra,

Bibliografia

• [1] De Micheli G.: Synthesis and Optimization of Digital Circuits. McGrawHill, 1994.
• [2] Łuba T.: Synteza układów cyfrowych. Praca zbiorowa pod redakcją prof. Tadeusza Łuby, Warszawa: WKŁ, 2003.
• [3] Maxfield C.: The Design Warrior's Guide to FPGAs. Orlando, FL, USA: Academic Press, Inc., 2004.
• [4] Berge C.: Graphs and Hypergraph. Amsterdam: North-Hols.r Mathematical Library, 1976.
• [5] Wiśniewska M.: Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych, PAK, Nr 8, s. 575-577, 2009.
• [6] Wiśniewska M., Wiśniewski R., Adamski M., Halang W.: Application of hypergraphs in microcode lenght reduction of microprogrammed controllers, Second International Workshop on Nonlinear Dynamics and Sychronization – INDS’09. Klagenfurt, Austria, 2009, ss. 106-109.
• [7] Wiśniewska M., Wiśniewski R., Adamski M.: Usage of hyper-graph theory in decomposition of concurrent automata. PAK,. 2007, nr 7, s. 66-68.
• [8] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI, LNCS, pp. 549-564, Springer, 2002.
• [9] Aho A. V., Hopcroft J. E., Ullman J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.