Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów

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

Warianty tytułu

EN

Application of the hypergraph theory to selection of compatibility classes

• Języki publikacji: PL

Abstrakty

PL

Redukcja pojemności pamięci jest istotnym etapem w procesie projektowania systemów dyskretnych. Często pojemność prototypowanej pamięci przekracza rozmiar docelowego bloku pamięci (np. w układach programowalnych FPGA). Najczęściej stosowanym rozwiązaniem jest redukcja rozmiaru mikroinstrukcji w projektowanym systemie. Algorytm bazuje na wyznaczeniu, a następnie selekcji klas kompatybilności poszczególnych mikrooperacji. W artykule zaprezentowane zostaną 2 autorskie algorytmy selekcji klas kompatybilności. Metody opierają się o wykorzystanie teorii hipergrafów (zastosowanie pokrycia wierzchołkowego). Proponowane rozwiązania zostaną gruntownie przeanalizowane oraz porównane z metodą tradycyjną, bazują na przekształceniach macierzowych.

EN

The problem of memory size reduction is a very important part of design process of discrete systems. The prototyped memory size very often exceeds the size of memory blocks offered by programmable devices (in example FPGAs). One of the most popular solutions to this problem is memory size reduction. The reduction process is based on selection of the compatibility classes of microoperations. Three methods of selection of compatibility classes are presented in the paper. The first one is a well-known method of selection, to which the fast reduction algorithm is applied. The algorithm bases on the matrix operations, which can also be represented as reduction of the hypergraph incidence matrix. In each step some vertices and edges are reduced. The reduced matrix holds the final result. The two other solutions introduced in the paper are based on the idea of computation of the minimal transversal (vertices covering) of hypergraphs. Proper microop-erations are represented by the hypergraph vertices, while compatibility classes are described by the hyperedges. Therefore, any method of hypergraph transversal calculation can be applied to achieve the selection. In the paper the authors propose and analyse the effectiveness of backtracking and greedy algorithms. The proposed solutions are compared with the traditional method, which is based on transformation of the hypergraph incidence matrix. The obtained results of experiments are analysed and discussed in detail.

Słowa kluczowe

PL

hipergraf; selekcja klas kompatybilności; transwersale (pokrycie wierzchołkowe) hipergrafu; mikrooperacja; redukcja pojemności pamięci

EN

hypergraph; selection of compatibility classes; transversals (hitting set), microoperation; memory size reduction

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 6
• Strony: 675--678
• Opis fizyczny: Bibliogr. 12 poz.,

Twórcy

autor

Wiśniewska M.

autor

Adamski M.

autor

Wiśniewski 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] Maxfield C.: The Design Warrior's Guide to FPGAs. Orlando, FL, USA: Academic Press, Inc., 2004.
• [3] Łuba T.: Synteza układów cyfrowych. Praca zbiorowa pod redakcją prof. Tadeusza Łuby, Warszawa: WKŁ, 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. Com-puting 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. Amsterdam: North-Hols.r Mathematical Library, 1976.
• [10] Eiter T., Gottlob G.: Hypergraph transversal computation and related problems in logic and AI, LNCS, pp. 549-564, Springer, 2002.
• [11] Wiśniewska M.: Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych, PAK, Nr 8, s. 575-577, 2009.
• [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.