Improved instruction formation in the exhaustive local microcode compaction algorithm

ABSTRACT

An algorithm has been developed to compact the micro-operations of horizontal microcode into optimal segments of straight-line microinstructions. The Quine modified (QM) algorithm generates solutions for 24 micro-operations in 2 sec. of VAX processing time. It generates a small number of solutions. A Pascal program that models the algorithm has been developed. A proof that the algorithm produces a minimal solution is given.

References

1. 1.Agerwala, "Microprogram Optimization: A Survey," IEEE Trans. Comp., vol. C-25, Oct. 1976.]]
2. 2.R. Atkins, "An Automatically Retargetable Microcode Compiler," in Entity-Relationship Approach to Software Engineering, (eds.) Carl G. Davis, Sushil Jajodia, Peter A. Ng, Raymond T. Yeh, Sept. 1983.]]
3. 3.S. Davidson, D. Landskov, B. Shriver, and P. Mallett, "Some Experiments in Local Microcode Compaction for Horizontal Machines," IEEE, 1981.]]
4. 4.D.J. Dewitt, "A Control Word Model for Detecting Conflicts Between Micro-operations," Proc. 8th Workshop on Microprogramming, Oct. 1975.]]
5. 5.S. Even, Graph Algorithms, Computer Science Press, 1979.]]
6. 6.J.A. Fisher, "Trace Scheduling: A Technique For Global Microcode Optimization," IEEE Trans. Comp., vol. C-30, no. 7, July 1981.]]
7. 7.Husson, Microprogramming: Principles and Practice, Englewood Cliffs, NJ: Prentice-Hall, 1970.]]
8. 8.R.L. Kleir and C.V. Ramamoorthy, "Optimization Strategies for Microprograms," IEEE Trans. Comp., vol. C-20, July 1971.]]
9. 9.R.L. Kleir, "A Representation for the Analysis of Microprogram Operation," Micro-7, 1974.]]
10. 10.D. Landskov, S. Davidson, B. Shriver, and P. Mallett, "Local Microcode Compaction Techniques," ACM Computing Surveys, vol. 12, no. 3, pp. 2651-2694, Sept. 1980.]]
11. 11.A. Nijenhuis and H. Wilf, Combinatorial Algorithms for Computers and Calculators, Academic Press, 1978.]]
12. 12.D. Patterson, K. Lew, and R. Tuck, "Toward an Efficient, Machine-Independent Language for Microprogramming," Proc. 12th Annual Microprogramming Workshop, pp. 22-35, November 1979.]]
13. 13.R. A. Mueller, Automated Microcode Synthesis, UMI Research Press, 1984.]]
14. 14.M. D. Poe, "Heuristics for the Global Optimization of Microprograms," IEEE, 1980.]]
15. 15.B.R. Rau, C.D. Glaeser, and R.L. Picard, "Efficient Code Generation for Horizontal Architectures: Compiler Techniques and Architectural Support," Proc. 9th Annual Symposium on Computer Arch., April 1982.]]
16. 16.M. Ruschitzka and R. Fabray, "A Unifying Approach to Scheduling," Comm. of the ACM, vol. 20, no. 7, July 1977.]]
17. 17.R.J. Sheraga and J.L. Gieser, "Experiments in Automatic Microcode Generation," IEEE Trans. Comp., vol. C-322, no. 6, June 1983.]]
18. 18.M. Tokoro, E. Tamura, and T. Takizuka, "Optimization of Microprograms," IEEE Trans. Comp., vol. C-30, July 1981.]]
19. 19.M. Tokoro, E. Tamura, K. Takase, and K. Tamuru, "An Approach to Microprogram Optimization Considering Resource Occupancy and Instruction Formats," Micro-10, 1977.]]
20. 20.M. Tokoro, T. Takizuka, E. Tamura, and I. Yamaura, "A Technique of Global Optimization of Microprograms," Micro-11, 1978.]]
21. 21.M. Tsuchiya and M. Gonzalez, "Toward Optimization of Horizontal Microprograms," IEEE Trans. Comp., vol. C-25, no. 10, Oct. 1976.]]
22. 22.M. Tsuchiya and M. Gonzalez, "An Approach to Optimization of Horizontal Microprograms," Micro-7, 1974.]]
23. 23.G. Wood, "On the Packing of Micro-operations into Micro-instruction Words," Proc. 11th Workshop on Microprogramming, Niagra Falls, NY, Sept. 1978.]]
24. 24.S. Yau, A. Schowe, and M. Tsuchiya, "On Storage Optimization for Horizontal Microprograms," Micro-7, 1974.]]

Index Terms

• Hardware

  • Electronic design automation

    • Logic synthesis

      • Circuit optimization

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Retargetable compilers