An approach to optimization of horizontal microprograms

ABSTRACT

Detection of concurrently executable microoperations is an important consideration for effective horizontal microprogramming. Since it is highly machine-dependent and requires knowledge of highly intricate features of a machine, only limited effort has been made so far to derive an algorithm for detection of microprogram parallelism to enable optimization of horizontal microprograms. In this paper, problems involved in optimization of horizontal microprograms are described. Existing techniques are applied to detect microprogram parallelism in a sequential source microprogram to allow subsequent optimization of the microprogram in a horizontal format. An algorithm for optimization of horizontal microprograms is derived. An upper bound for microprogram execution time is determined. The results derived in this paper are very general so that they are applicable to any machine with a horizontal microinstruction format (including a vertical format which is a special case of a horizontal format). An example is given to illustrate the algorithm.

REFERENCES

• 1: Schwartz, S. J., "An Algorithm for Minimizing Read Only Memories for Machine Control," 1968 IEEE 10th Annual Symp. on Switching and Automata Theory..
• 2: Grasseli, A. and Montanari, U., "On the Minimization of Read Only Memories in Microprogrammed Digital Computer," IEEE-TC, Vol. C-19, pp. 1111-1114, November, 1970.
• 3: Das, S. R., Banerji, D. K., and Chattopadhyay, A., "On Control Memory Minimization in Microprogrammed Digital Computers," IEEE-TC, Vol. C-22, pp. 845-848, September, 1973.
• 4: Montangero, C., "An Approach to the Optimal Specification of Read-Only Memories in Microprogrammed Digital Computers," IEEE-TC, Vol. C-23, pp. 375-389, April, 1974.
• 5: Allen, F. E., "Program Optimization," Annual Review in Automatic Programming, Vol. 5, New York: Pergamon, pp. 239-307.
• 6: Kleir, R. L. and Ramamoorthy, C. V., "Optimization Strategies for Microprograms," IEEE-TC, Vol. C-20, pp. 783-794, July, 1971.
• 7: Ramamoorthy, C. V. and Tsuchiya, M., "A High-Level Language for Horizontal Microprogramming," IEEE-TC, Vol. C-23, No. 8, August, 1974.
• 8: Hu, T. C., "Parallel sequencing and assembly line problems," Oper. Res., 9,6, 841-848, November, 1961.
• 9: Coffman, E. G., Jr. and R. L. Graham, "Optimal Scheduling Strategies for two-processor system," Acta Informatica, 1, 3, pp. 200-213, 1972.
• 10: Ramamoorthy, C. V., K. M. Chandy, and M. J. Gonzalez, "Optimal scheduling and strategies in a multiprocessor system," IEEE-TC, Vol. C-21, 2, pp. 137-146, February, 1972.
• 11: Ramamoorthy, C. V. and M. J. Gonzalez, "A survey of techniques for recognizing parallel processable streams in computer programs," Proc. FJCC, 1-15, 1969.
• 12: M. R. Garey , R. L. Grehem, Bounds on scheduling with limited resources, Proceedings of the fourth ACM symposium on Operating system principles, p.104-111, January 1973

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.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Performance