Microcode compaction with timing constraints

ABSTRACT

At present, microcode compaction with timing constraints (abbreviated as MCTC) is still an open problem. Complex timing relation between microoperations greatly affects the optimization result of microcode. This paper begins with a survey of MCTC problems, then presents a formal description of MCTC and, on the basis of a systematic study of the characteristics of MCTC, presents a generally-oriented heuristic algorithm— CAS, which has a high success rate of scheduling and promises good optimization result. Preliminary experiments indicate that CAS is better than other existing MCTC algorithms.

REFERENCES

• 1: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• 2: Cy Dale Ardoin, An approach to phase-coupled resource allocation and code reorganization for a class of pipeline architectures, University of Southwestern Louisiana, Lafayette, LA, 1988
• 3: J.A.Fisher. The Optimization of Horizontal Microcode vithin and Beyond Basic Blocks: An Application of Processor Scheduling vith Resources.U.S. Department of Energy Report, C00-3277-161. Oct.1979.
• 4: J.A.Fisher. Trace Scheduling: A Technique for Globai Microcode Compaction. IEEE Trans. on Computers, pp478-479. C-30, 1981.
• 5: J.A.Fisher, et al. Microcode Compaction: Looking Backward and Looking Forward. National Computer Conference, 1981.
• 6: D.Hoste, et al. Am29500 Application Note. AHD. Inc. 1985.
• 7: Thomas R. Gross , John L. Hennessy, Optimizing delayed branches, Proceedings of the 15th annual workshop on Microprogramming, p.114-120, October 05-07, 1982, Palo Alto, California, United States
• 8: 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]
• 9: D.Landskov. et al. Some Experiments in Local Microcode Compaction for Horizontal Machines. IEEE Trans. on Computers, Vol.C-30, July.1981.
• 10: L. Manasiev , A. Petkov , K. Boyanov, A formal approach to the problems of microcode compaction caused by transient data resources of the microarchitectures, ACM SIGMICRO Newsletter, v.17 n.3, p.8-12, Dec. 1986 [doi>10.1145/378741.378753]
• 11: M. Mezzalama , P. Prinetto , G. Filippi, Microcode compaction via microblock definition, Proceedings of the 15th annual workshop on Microprogramming, p.134-142, October 05-07, 1982, Palo Alto, California, United States
• 12: R.A.Mueller. Horizon Compiler Hypothetical Micro-Architecture 2. Technical Report MAD-86- 19, CSU. Sept. 1986.
• 13: Michael D. Poe , Ross Goodell , Simon Steely, Jr., Issues of the design of a low level microprogramming language for global microcode compaction, Proceedings of the 14th annual workshop on Microprogramming, p.88-94, December 01-01, 1981, Chatham, Massachusetts, United States
• 14: 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
• 15: B.Su. Basic Idea of Compaction Algorithm with Timing. Private communication, Aug. 1986.
• 16: B. Su , S. Ding , J. Xia, URPR—An extension of URCR for software pipelining, Proceedings of the 19th annual workshop on Microprogramming, p.94-103, October 15-17, 1986, New York, New York, United States
• 17: Robert.E.Tarjan. Shortest Path Algorithms in "Graph Theory with Application to Algorithms and Computer Science, ed. by Y.Alavi. etc. John Wilet & Sons, Inc. 1985.
• 18: Mario Tokoro , Eiji Tamura , Kazuhiko Takase , Kiichiro Tamaru, An approach to microprogram optimization considering resource occupancy and instruction formats, Proceedings of the 10th annual workshop on Microprogramming, p.92-108, October 05-07, 1977, Niagara Falls, New York, United States
• 19: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982
• 20: C.C.Tang. Fast Algorithms for Bounding the Performance of Multiprocessor Systems. Proc. of 1976 International Conference Parallel Processing.