Reduction of the Microinstruction Length in the designing process of Microprogrammed Controllers

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

Warianty tytułu

PL

Redukcja rozmiaru mikroinstrukcji w procesie projektowania sterowników mikroprogramowanych

• Języki publikacji: EN

Abstrakty

EN

The problem of the microinstruction length reduction is a very important part of the designing process of the microprogrammed controllers. Such a problem is NP-hard, therefore many various algorithms have been developed. Almost all proposed ideas are based on the traditional graph theory and its modifications (heuristics, stochastic, etc.). In the paper, we propose the method of microinstruction length reduction, where the hypergraph theory is applied. A hypergraph permits to store and reduce the information about the compatibility classes in comparison with traditional graphs. The microinstruction length reduction is reached thanks to the calculation of the dual hypergraph and computation of its minimum transversal (minimal vertices cover). All steps that are required in order to perform the microinstruction length reduction of microprogrammed controllers will be shown. The proposed method will be illustrated by way of example and compared with the traditional solution, based on the graph theory.

PL

Problem redukcji rozmiaru mikroinstrukcji jest ważnym etapem w procesie projektowania sterowników mikroprogramowanych. Jest to problem NP-trudny, dlatego też powstało wiele metod poszukujących rozwiązania. Zdecydowana większość zaproponowanych algorytmów bazuje na tradycyjnej teorii grafów. W artykule zaprezentowano nowatorską metodę redukcji rozmiaru mikroinstrukcji sterowników mikroprogramowanych, częściowo opierającą się na rozwiązaniach klasycznych. Metoda bazuje na wykorzystaniu teorii hipergrafów do wyznaczenia klas kompatybilności dla poszczególnych mikrooperacji. Mikrooperacje, które są parami kompatybilne mogą zostać zakodowane z wykorzystaniem mniejszej liczby bitów. Dzięki temu rozmiar pamięci układu mikroprogramowanego może zostać w znacznym stopniu zmniejszony. Zaproponowane rozwiązanie bazuje na wyznaczeniu hipergrafu dualnego, a następnie znalezieniu jego minimalnej transwersali (minimalnego pokrycia wierzchołkowego). Idea metody zostanie zilustrowana przykładem. Pokazane zostaną wszystkie kroki, jakie są niezbędne do zaprojektowania zmodyfikowanego układu pamięci. Zaproponowana metoda zostanie porównana z rozwiązaniami klasycznymi, bazującymi na teorii grafów.

Słowa kluczowe

EN

hypergraph; compatibility; controller; microoperation; microinstruction; length

PL

hipergraf; kompatybilność; sterownik; mikrooperacja; mikroinstrukcja; pamięć

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2009
• Tom: R. 85, nr 7
• Strony: 203--206
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Wiśniewska M.

autor

Wiśniewski R.

autor

Adamski M.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Podgórna 50, 65-001 Zielona Góra,

Bibliografia

• [1] De Micheli G., Synthesis and Optimization of Digital Circuits, McGrawHill (1994).
• [2] Clements A., The principles of computer hardware, Oxford University Press, New Jersey (2000).
• [3] Łuba T., Synteza układów cyfrowych,. Praca zbiorowa pod redakcją prof. Tadeusza Łuby, WKŁ, Warszawa (2003).
• [4] Bolton M., Digital Systems Design with Programmable Logic, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (1990).
• [5] Burskey D., Embedded Logic and Memory Find Home in FPGA, Electronic Design, 14 (1999), 43-56.
• [6] Gajski D., Principles of Digital Design, Prentice Hall, New Jersy (1997).
• [7] Puri R., Gu J., Microword Length Minimization in Microprogrammed Controller Synthesis, IEEE Trans. on Computer-Aided Design (1993).
• [8] Robertson E. L., Microcode bit optimization is NP-complete, IEEE Trans. Comput., C-28 (1979), 316–319.
• [9] Dasgupta S., The Organization of Microprogram Stores, Computing Surveys (1979).
• [10] Hong S. K., Park I. C., Kyung C. M., An O(n3logn) Heuristic for Microcode Bit Optimization, In ICCAD-90 (1990), 180-183.
• [11] Lam J., Delosme J. M., Simulated Annealing: A Fast Heuristic for Partitioning VLSI Networks, In ICCAD-88 (1988), 510-513.
• [12] Aho A. V., Hopcroft J. E., Ullman J. D., The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA (1974).
• [13] Eiter T., Gottlob G., Identifying the Minimal Transversals of a Hypergraph and Related Problems, SIAM Journal on Computing, Volume 24, Issue 6 (1995), 1278 - 1304.
• [14] Berge C., Graphs and Hypergraph, North-Hols.r Mathematical Library, Amsterdam (1976).
• [15] Eiter T., Gottlob G., Hypergraph transversal computation and related problems in logic and AI. LNCS, Springer (2002), 549—564.
• [16] Hoos H.H., Stutzle T., Local Search Algorithms: An Empirical Evaluation, Journal of Automated (2000), 421-481.
• [17] Wilkes M. V., The best way to design an automatic calculating machine, Manchester University inaugural conference, Manchester, England (1951).
• [18] Molski M., Modułowe i mikroprogramowalne układy cyfrowe, WKŁ, Warszawa (1986).
• [19] Sapiecha P., Algorytmy syntezy funkcji i relacji boolowskich w aspekcie metod reprezentacji i kompresji danych, PW, Wydział Elektroniki i Technik Informacyjnych, Warszawa (1998).