ABSTRACT
Fisher's trace scheduling procedure for global compaction has proven to be able to produce significant reduction in execution time of compacted microcode, however extra space may be sometimes required during bookkeeping, and the efficacy of compaction of microprogram loop is lower than that of hand compaction.
This paper introduces an improved trace scheduling compaction algorithm to mitigate the drawbacks mentioned above. The improved algorithm is based on a modified menu of moving microoperations, an improved trace scheduling algorithm, and a special loop compaction algorithm. Preliminary tests indicate that this global compaction algorithm gives shorter execution time and less space requirement in comparison with Fisher's algorithm.
- 1.A. V. Aho and J. D. Ullman, Principles of Compiler Design. Reading, MA: Addison-Wesley, 1977. Google ScholarDigital Library
- 2.S. Davidson, D. Landskov, B. D. Shriver, and P. W. Mallett, "Some Experiments in Local Microcode Compaction for Horizontal Machine," IEEE Trans. Comput., vol.C-30, pp.460-477, July 1981.Google ScholarDigital Library
- 3.J. A. Fisher, "The Optimization of Horizontal Microcode Within and Beyond Basic Block: An Application of Processor Scheduling with Resource," Courant Math. Comput. Lab., New York University, U.S. Dep. of Energy Rep.C00-3077-161, Oct. 1979.Google Scholar
- 4.J. A. Fisher, "Trace Scheduling: A Technique for Global Microcode Compaction," IEEE Trans. Comput., vol.C-30, pp.478-490, July 1981.Google ScholarDigital Library
- 5.J. A. Fisher, "Very Long Instruction Word Architecture and the ELI-512," Research Report YALEU/DCS/RR-253, April 1983.Google Scholar
- 6.J. A. Fisher, D. Landskov, and B.D. Shriver, "Microcode Compaction: Looking Backward and Looking Forward," AFIPS National Conference, pp.95-102, 1981.Google Scholar
- 7.R. Grishman and Su Bogong, "An Preliminary Evaluation of Trace Scheduling for Global Microcode Compaction," Dept. of Computer Science, Courant Inst. of Math. Science, NYU, Report No.042, May 1982.Google Scholar
- 8.R. Grishman and Su Bogong, "An Preliminary Evaluation of Trace Scheduling for Global Microcode Compaction," IEEE Trans. Comput., vol.C-32, pp.1191-1194, Dec. 1983.Google ScholarDigital Library
- 9.T. R. Gross and J. L. Hennessy, "Optimizing Delayed Branches," In 15th Annual Workshop on Microprogramming, pp.114-120, ACM Special Interest Group on Microprogramming, Oct. 1982. Google ScholarDigital Library
- 10.J. Lah and E. Atkin, "Tree Compaction of Microprograms," In 16th Annual Workshop on Microprogramming, pp.23-33, ACM Special Interest Group on Microprogramming, Oct. 1983.Google Scholar
- 11.D. Landskov, S. Davidson, B. D. Shriver, and P. W. Mallett, "Local Microcode Compaction Techniques," Computing Survey, pp.261-294, Sept. 1980. Google ScholarDigital Library
- 12.J. L. Linn, "SRDAG Compaction - A Generalization of Trace Scheduling to Increase the Use of Global Context Information," In 16th Annual Workshop on Microprogramming, pp.11-22, ACM Special Interest Group on Microprogramming, Oct. 1983.Google Scholar
Index Terms
- An improvement of trace scheduling for global microcode compaction
Recommendations
An improvement of trace scheduling for global microcode compaction
MICRO 17: Proceedings of the Seventeenth Annual Microprogramming WorkshopFisher's trace scheduling procedure for global compaction has proven to be able to produce significant reduction in execution time of compacted microcode, however extra space may be sometimes required during bookkeeping, and the efficacy of compaction ...
A Preliminary Evaluation of Trace Scheduling for Global Microcode Compaction
Fisher has recently described a new procedure for global microcode compaction which he calls "trace scheduling." We have implemented this procedure and tested it on several microcode sequences. We report in this correspondence on the relative ...
Trace scheduling optimization in a retargetable microcode compiler
MICRO 20: Proceedings of the 20th annual workshop on MicroprogrammingWe discuss the integration of a trace scheduling optimizer into a retargetable optimizing microcode compiler that handles complex timing relations. The trace scheduler requires no special treatment when retargeting the compiler, being constructed from ...
Comments