Incremental foresighted local compaction

ABSTRACT

Under timing constraints, local compaction may fail because of poor scheduling decisions. Su [SDWX87] uses foresight to avoid some of the poor scheduling decisions. However, the foresight takes a considerable amount of time. In this paper the Incremental Foresight algorithm is introduced. Experiments using four different target architectures show that the Incremental Foresight algorithm works as well as foresight, and saves around 48 percent of the excess time.

REFERENCES

• All86: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• AM87: Vicki H. Allan , Robert A. Mueller, Phase coupling for horizontal microcode generation, Proceedings of the 20th annual workshop on Microprogramming, p.115-125, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255328]
• AM88: V. H. Allen , R. A. Mueller, Compaction with General Synchronous Timing, IEEE Transactions on Software Engineering, v.14 n.5, p.595-599, May 1988 [doi>10.1109/32.6137]
• AWSW89: V.H. Allan, P. Wijaya, B. Su, and J Wang. Foresighted Compaction under Timing Constraints. Technical Report CS-89-10, Department of Computer Science, Utah State University, Logan, Utah, 1989.
• SDWX87: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, Microcode compaction with timing constraints, Proceedings of the 20th annual workshop on Microprogramming, p.59-68, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255314]
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Design, Experimentation