Extending microcode compaction for real architectures

ABSTRACT

Microcode compaction is an essential component of any high-level language compiler that generates microcode for a horizontal architecture machine. Recent research into both local and global compaction has assumed the use of a simple abstract machine. Although this assumption simplifies the effort considerably, it neglects addressing and timing problems brought on by the uncommon operation of some machines. This paper discusses both local and global compaction in terms of the Burroughs D-machine. The D-machine has peculiar timing and an uncommon jump instruction that do not readily fit into proposed compaction algorithms. Methods for handling these problems are presented. In addition, two popular algorithms for performing compaction, list scheduling and trace scheduling, are explained entirely in terms of the D-machine. This should aid the reader in understanding the problem and evaluating any alternatives.

REFERENCES

• ADAM74: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• AHO79: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• ALLE70: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• DAVI81: Davidson, S., Landskov, D., Shriver, B. D., and Mallett, P. W. "Some Experiments in Local Microcode Compaction for Horizontal Machines", IEEE Transactions on Computers C- 32, 7 (July 1981), 460-477.
• DEWI76: David Johns Dewitt, A machine independent approach to the production of optimized horizontal microcode., 1976
• FISH79: Fisher, J. A. The Optimization of Horizontal Microcode Within and Beyond Basic Blocks: An Application of Processor Scheduling With Resources, U.S. Department of Energy Report, Mathematics and Computing C00-3077-161, New York University, Oct. 1979.
• FISH81: Fisher, J. A. "Trace Scheduling: A Technique for Global Microcode Compaction", IEEE Transactions on Computer C-32, 7 (July 1981), 478-490.
• ISOD83: Isoda, S., Kobayaski, Y., and Ishida, T. "Global Compaction of Horizontal Microprograms Based on Generalized Data Dependency Graph", IEEE Transactions on Computers C-32, 10 (Oct. 1983), 922-933.
• KATZ77: Katzan, H. Microprogramming Primer, McGraw-Hill, New York, New York, 1977.
• KNUT71: Knuth, D. E. "An Empirical Study of FORTRAN programs", Software-Practice and Experience 1, 2 (Feb. 1970), 105-133.
• LAH83: Lah, S., and Atkin, D. E. "Tree Compaction of Microprograms", The Proceedings of 16th Annual Workshop on Microprogramming 16, (Oct. 1983), 23-33.
• LAND80: David Landskov , Scott Davidson , Bruce Shriver , Patrick W. Mallett, Local Microcode Compaction Techniques, ACM Computing Surveys (CSUR), v.12 n.3, p.261-294, Sept. 1980 [doi>10.1145/356819.356822]
• LINN83: Linn J. "SRDAG Compaction - A Generalization of Trace Scheduling to Increase the Use of Global Context Information", The Proceedings of 16th Annual Workshop on Microprogramming 16, (Oct. 1983), 11-22.
• SU84: Bogong Su , Shiyuan Ding , Lan Jin, An improvement of trace scheduling for global microcode compaction, Proceedings of the 17th annual workshop on Microprogramming, p.78-85, December 1984
• ULLM73: J. D. Ullman, Polynomial complete scheduling problems, Proceedings of the fourth ACM symposium on Operating system principles, p.96-101, January 1973
• WOOD78: Graham Wood, On the packing of micro-operations into micro-instruction words, Proceedings of the 11th annual workshop on Microprogramming, p.51-55, November 19-22, 1978, Pacific Grove, California, United States