A loop optimization technique based on scheduling table

ABSTRACT

Loop optimization is an important aspect of microcode compaction to minimize execution time. In this paper a new loop optimization technique for horizontal microprograms is presented, which makes use of the cyclic regularity of loops. We have extended the concept of reservation table, which is used to develop a pipeline control strategy, so that both data dependencies and resource conflicts are taken into account. Based on the analysis of the extended reservation table, or scheduling table, an optimal schedule can be obtained. The iterations of a loop are then rearranged to form a new loop body, whose length may be greater than that of the original one. But the average initiation latency between iterations is minimal.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Kai Hwang, "Computer Architecture and Parallel Processing", McGraw-Hill Book Company, 1984.
• 3: J.A. Fisher, "Trace Scheduling: A technique for Global Microcode Compaction", IEEE Transactions on Computers, Vol C-30, No. 7, pp. 478-490, July 1981.
• 4: Peter M. Kogge, "The Architecture of Pipelined Computers", McGraw-Hill Book Company, 1981
• 5: J. Lah and D.E. Aktin, "Tree Compaction of Microprograms", The Proc of 16th Workshop on Microprogramming, 1983.
• 6: 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]
• 7: D. Liu, "A Proposal on a Retargetable Microcode Generation System", Technical Report, GMD-TUB FIRST, May 1988.
• 8: R. A. Mueller , B. Su , M. R. Duda , B. L. Plomondon, A case study in signal processing microprogramming using the URPR software pipelining technique, Proceedings of the 19th annual workshop on Microprogramming, p.104-115, October 15-17, 1986, New York, New York, United States
• 9: 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

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Optimization

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.5 Microcode Applications
          Subjects: Direct data manipulation**
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Pipeline

General Terms:
Design, Languages