Redukcja rozmiaru mikroinstrukcji w projektowaniu sterowników mikroprogramowanych

• Autorzy: Wiśniewska M.

Warianty tytułu

EN

Microinstruction length reduction in design of microprogrammed controllers

• Języki publikacji: PL

Abstrakty

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 przedstawiono nową metodę redukcji rozmiaru mikroinstrukcji pamięci sterowników mikroprogramowanych. Algorytm bazuje na reprezentacji klas kompatybilności mikrooperacji z zastosowaniem teorii hipergrafów, a redukcja rozmiaru mikroinstrukcji obliczana jest na podstawie najmniejszej transwersali hipergrafu.

EN

A microprogrammed controller (also called microprogrammed control unit) consisting of two main parts is one of realizations of the control unit. The first part is responsible for addressing microinstructions that are kept in the control memory. The role of the second part is to hold and generate adequate microinstructions. Typically, the control memory is implemented as a ROM or RAM memory. Many controllers have a long microinstruction width. It may cause serious problems in the prototyping process. If the design is realized as a System-On-Programmable-Chip (SoPC), the memory can be implemented with dedicated memory blocks of Field Programmable Gate Arrays (FPGAs). However, if the microinstruction length exceeds the length of the dedicated memory block offered by an FPGA, the controller's memory ought to be decomposed. In case of controllers implemented as a System-On-Chip (SoC), the memory is treated as an independent module. It means that each additional bit in the microinstruction width increases the total cost of the memory and the whole device. Therefore, the microinstruction length reduction is a very important part of the designing process of the microprogrammed controllers in a digital system. In the paper, we propose the method of microinstruction length reduction, where the hypergraph theory is applied. The microinstruction length reduction is reached thanks to the calculation of the dual hypergraph and computation of its minimum transversal (minimal vertices cover).

Słowa kluczowe

PL

hipergraf; klasa kompatybilności; sterownik (układ) mikroprogramowany; mikrooperacja; mikroinstrukcja; redukcja rozmiaru pamięci

EN

hypergraph; compatibility class; microprogrammed controller (control unit); microoperation; microinstruction; reduction of the microinstruction length

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 575--577
• Opis fizyczny: Bibliogr. 19 poz., rys., tab., wzory

Twórcy

autor

Wiśniewska M.

• Uniwersytet Zielonogórski,

Bibliografia

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