Zastosowanie transwersali hipergrafów w minimalizacji pojemności pamięci systemów dyskretnych

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

Warianty tytułu

EN

Application of hypergraph transversals to memory size minimisation

• Języki publikacji: PL

Abstrakty

PL

Algorytm redukcji pojemności pamięci systemów dyskretnych bazuje na wyznaczeniu i selekcji klas kompatybilności poszczególnych mikrooperacji. Proces selekcji klas kompatybilności jest zaliczany do problemów z klasy NP-trudnych. W artykule zaprezentowano metodę selekcji klas kompatybilności opierającą się o wyznaczenie transwersali hipergrafów. Proponowane rozwiązanie zostało gruntownie przeanalizowane oraz porównane z metodami tradycyjnymi, bazującymi na przekształceniach macierzowych.

EN

The problem of memory size minimisation is a very important part of the design process of a discrete system. Very often the volume of the prototyped memory exceeds the size of memory blocks offered by programmable devices (like FPGAs or CPLDs). One of the most popular solution to this problem is memory size minimisation. The reduction of the memory is achieved thanks to selection of the compatibility classes of the microoperations. Such a problem is NP-hard, therefore many various algorithms have been developed. Most of them are based on the graph and matrix theories. In the paper there is proposed a method for memory size reduction in which the hypergraph theory is applied. A hypergraph permits to store and reduce information about the compatibility classes in comparison with the traditional graphs. The memory size minimisation is reached thanks to the computation of its transversal (vertices cover). Any known transversal algorithm can be used in order to calculate the selection of compatibility classes. Four different covering methods of hypergraphs are presented and compared. All steps that are required in order to perform the microinstruction length reduction of discrete systems are shown. The proposed method is compared with the traditional solution. Finally, the detailed results of experiments are presented and discussed.

Słowa kluczowe

PL

hipergraf; transwersala (pokrycie wierzchołkowe hipergrafu); klasa kompatybilności; mikrooperacja; mikroinstrukcja; minimalizacja pojemności pamięci

EN

hypergraph; hypergraph transversal; compatibility class; microoperation; microinstruction; memory size minimization

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 777--779
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wzory

Twórcy

autor

Wiśniewska M.

autor

Wiśniewski R.

autor

Adamski M.

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

Bibliografia

• [1] De Micheli G.: Synthesis and Optimization of Digital Circuits. McGrawHill, 1994.
• [2] Maxfield C.: The Design Warrior's Guide to FPGAs, Academic Press, Inc., Orlando, FL, USA, 2004.
• [3] Łuba T.: Synteza układów cyfrowych. Praca zbiorowa pod redakcją prof. Tadeusza Łuby, WKŁ, Warszawa, 2003.
• [4] Puri R., Gu J.: Microword Length Minimization in Microprogrammed Controller Synthesis. IEEE Trans. on Computer-Aided Design, 1993.
• [5] Robertson E. L.: Microcode bit optimization is NP-complete. IEEE Trans. Comput., vol. C-28, pp. 316-319, Apr. 1979.
• [6] Dasgupta S.: The Organization of Microprogram Stores. Computing Surveys, 1979.
• [7] Hong S. K., Park I. C., Kyung C. M.: An O(n3logn) Heuristic for Microcode Bit Optimization. In ICCAD-90, pp. 180-183, 1990.
• [8] Aho A. V., Hopcroft J. E., Ullman J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
• [9] Berge C.: Graphs and Hypergraph. North-Hols.r Mathematical Library, Amsterdam 1976.
• [10] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI. LNCS, pp. 549-564, Springer, 2002.
• [11] Sapiecha P.: Algorytmy syntezy funkcji i relacji boolowskich w aspekcie metod reprezentacji i kompresji danych. PW, Wydział Elektroniki i Technik Informacyjnych, Warszawa, 1998.
• [12] Tkacz J., Adamski M.: Projektowanie sekwencyjnych układów cyfrowych z wykorzystaniem logiki sekwentów Gentzena, Przegląd Elektrotechniczny, R. 85, nr 7, pp. 196-199, 2009.
• [13] Wisniewska M.: Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych, PAK, Nr 8, s. 575-577, 2009.