Compacting MIMOLA microcode

ABSTRACT

We address the problem of reducing the word length of microprograms. Two techniques are described: overlaying of fields and encoding of the microprogram. Formal analyses are presented of different encoding methods, assuming a VLSI implementation. A maximal encoding strategy appears to be the most area-efficient. Field overlaying is formulated as a clique-partitioning problem, and an efficient and practical clique-partitioning algorithm is presented. Based on these results, a microword compaction strategy that consists of field overlaying followed by maximal encoding has been implemented for the MIMOLA synthesis system (a design tool that generates excessively long microinstructions). Some considerations that are relevant to MIMOLA, and probably general to other similar tools, are discussed.

REFERENCES

• AGER76: Agerwala, T. "Microprogram optimization: a survey", IEEE Trans. Computers, C-25, 10, Oct 1976, pp962-973.
• BAER77: Baer, J.L., and Koyama, B. On the minimization of the width of the control memory of microprogrammed processors, Tech. Rep. #77-08-01, Dept. Computer Science, Univ. of Washington, Seattle, 1977.
• BHAS87: Bhasker, J., and Samad, T. "A better clique partitioning algorithm", in preparation.
• DAS69: Das, S.R., and Sheng, C.L. "On finding maximal compatibles", Proc. IEEE, 57, April 1969, pp674-675.
• DAS73: Das, S.R., Banerji, D.K., and Chattopadhay, A. "On control memory minimization in microprogrammed digital computers", IEEE Trans. Computers, C-22, 9, Sept 1973, pp845-848.
• DASG76: Dasgupta, S., and Tartar, J. "The identification of maximal parallelism in straight line microprograms", IEEE Trans. Computers, C-25, 10, Oct 1976, pp986-992.
• DASG79: Subrata Dasgupta, The Organization of Microprogram Stores, ACM Computing Surveys (CSUR), v.11 n.1, p.39-65, March 1979 [doi>10.1145/356757.356761]
• GRAS70: Grasselli, A., and Montanari, U. "On the minimization of read-only memories in microprogrammed digital computers", IEEE Trans. Computers, C-19, 11, Nov 1970, pp1111-1114.
• JAYA76: Jayasri, T., and Basu, D. "An approach to organizing microinstructions which minimizes the width of control store words", IEEE Trans. Computers, C-25, 5, May 1976, pp514-521.
• MEAD80: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• MONT74: Montangero, C. "An approach to the optimal specification of read-only memories in microprogrammed digital computers", IEEE Trans. Computers, C-23, 4, April 1974, pp375-389.
• NEWK83: Newkirk, J., and Mathews, R. The VLSI Designer's Library. Addison Wesley, 1983.
• PENN72: Penny, W.M., and Lau, L. (Eds.) MOS Integrated Circuits, Chapter 7. Robert E. Krieger Publishing Company, Malabar, Florida, 1972.
• RAMA74: Ramamoorthy, C.V., and Tsuchiya, M. "A highlevel language for horizontal microprogramming", IEEE Trans. Computers, C-23, 8, Aug 1974, pp791-801.
• SAMA87: Samad, T., and Bhasker, J. "Some old and new results in clique partitioning", submitted for publication.
• SCHW68: Schwartz, S.J. "An algorithm for minimizing read-only memories for machnie control", Proc. IEEE 10th Annual Symp. on Switching and Automata Theory, 1968, New York, pp28-33.
• SYSL83: Maciej Syslo , Narsingh Deo , Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, Prentice Hall Professional Technical Reference, 1983
• TSEN84: Chia-Jeng Tseng, Automated synthesis of data paths in digital systems (design space), 1984
• TSUC74: M. Tsuchiya , M. J. Gonzalez, Jr., An approach to optimization of horizontal microprograms, Conference record of the 7th annual workshop on Microprogramming, p.85-90, September 30-October 02, 1974, Pal Alto, California, United States [doi>10.1145/800118.803846]
• UNGE69: Stephen H. Unger, Asynchronous Sequential Switching Circuit, Krieger Publishing Co., Inc., Melbourne, FL, 1983
• YAU74: S. S. Yau , A. C. Schowe , M. Tsuchiya, On storage optimization of horizontal microprograms, Conference record of the 7th annual workshop on Microprogramming, p.98-106, September 30-October 02, 1974, Pal Alto, California, United States [doi>10.1145/800118.803848]

INDEX TERMS

Keywords:
clique partitioning, compaction, microprogramming, synthesis