On storage optimization of horizontal microprograms

ABSTRACT

The storage requirement of a horizontal microprogram can be reduced by optimal packing of micro-operations into micro-instructions. The purpose of this paper is to examine micro-instruction generation for horizontally microprogrammable computers in order to reduce the number of required micro-instructions for a loop-free segment of micro-operations. Although some methods for solving this problem exist, so far no systematic approach has been used to determine what type of analysis must be performed on each sequential segment of micro-operations. In this paper, the micro-instruction generation process is analyzed and two optimization methods are presented. The first method is algorithmic in that it will always generate the minimum micro-instruction set for a given subblock of micro-operations. The other method is heuristic and does not always result in the minimum micro-instruction set. The methods developed here are shown to achieve better results than those of the existing methods.

REFERENCES

• 1: F. F. Atstopas, and K. I. Plukas, "Method of Minimizing Computer Microprograms," Automatic Control, Vol. 5, No. 4, pp. 10-16, 1971.
• 2: R. Barr, J. Becker, W. Lidinsky, V. Tantillo, "A Research-Oriented Dynamic Microprocessor," IEEE Trans. on Computers, Vol. C-22, pp. 976-985, 1973.
• 3: Francois Robert Broca , Richard E. Merwin, Direct microprogrammed execution of the intermediate text from a high-level language compiler, Proceedings of the annual conference, p.57-63, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805681]
• 4: Robert K. Clark, Mirager, the "best-yet" approach for horizontal microprogramming, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800193.569972]
• 5: P. C. Goldberg, "A Comparison of Certain Optimization Techniques," Design and Optimization of Compilers, Ed. Randall Rustin, Englewood Cliffs, N. J.: Prentice-Hall, 1972, pp. 31-50.
• 6: Mitsuhiro Hattori , Michiko Yano , Kiichi Fujino, MPGS: a high-level language for microprogram generating system, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800193.569973]
• 7: R. L. Kleir, and C. V. Ramamoorthy, "Optimization Strategies for Microprograms," IEEE Trans. on Computers, Vol. C-20, pp. 783-794 1971.
• 8: Gérard L. M. NOGUEZ, A standardized microprogram sequencing control with a push down storage, Conference record of the 5th annual workshop on Microprogramming, September 25-26, 1972, Urbana, Illinois [doi>10.1145/776378.776388]
• 9: C. V. Ramamoorthy , M. J. Gonzalez, Subexpression ordering in the execution of arithmetic expressions, Communications of the ACM, v.14 n.7, p.479-485, July 1971 [doi>10.1145/362619.362630]
• 10: C. V. Ramamoorthy, and M. Tsuchiya, "A High-Level Language for Horizontal Microprogramming," IEEE Trans. on Computers. Vol. C-23, August, 1974.
• 11: Paul B. Schneck, A survey of compiler optimization techniques, Proceedings of the annual conference, p.106-113, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805690]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers
      B.1.5 Microcode Applications
          Subjects: Instruction set interpretation

General Terms:
Design, Languages, Performance