Minimum register requirements for a modulo schedule

ABSTRACT

Modulo scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present a combined approach that schedules the loop operations for minimum register requirements, given a modulo reservation table. Our method determines optimal register requirements for machines with finite resources and for general dependence graphs. This method demonstrates the potential of lifetime-sensitive modulo scheduling and is useful in evaluating the performance of lifetime-sensitive modulo scheduling heuristics.

REFERENCES

• 1: B. Ramakrishna Rau , Joseph A. Fisher, Instruction-level parallel processing: history, overview, and perspective, The Journal of Supercomputing, v.7 n.1-2, p.9-50, May 1993 [doi>10.1007/BF01205181]
• 2: P Y Hsu, Highly concurrent scalar processing, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• 3: B. Ramakrishna Rau , Christopher D. Glaeser , Raymond L. Picard, Efficient code generation for horizontal architectures: Compiler techniques and architectural support, Proceedings of the 9th annual symposium on Computer Architecture, p.131-139, April 26-29, 1982, Austin, Texas, United States
• 4: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 5: Nancy J. Warter , Grant E. Haab , Krishna Subramanian , John W. Bockhaus, Enhanced modulo scheduling for loops with conditional branches, Proceedings of the 25th annual international symposium on Microarchitecture, p.170-179, December 01-04, 1992, Portland, Oregon, United States
• 6: Nancy Jeanne Warter, Modulo scheduling with isomorphic control transformations, University of Illinois at Urbana-Champaign, Champaign, IL, 1993
• 7: P. Tirumalai , M. Lee , M. Schlansker, Parallelization of loops with exits on pipelined architectures, Proceedings of the 1990 conference on Supercomputing, p.200-212, October 1990, New York, New York, United States
• 8: B. R. Rau , M. Lee , P. P. Tirumalai , M. S. Schlansker, Register allocation for software pipelined loops, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.283-299, June 15-19, 1992, San Francisco, California, United States
• 9: William Mangione-Smith , Santosh G. Abraham , Edward S. Davidson, Register requirements of pipelined processors, Proceedings of the 6th international conference on Supercomputing, p.260-271, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143419]
• 10: Richard A. Huff, Lifetime-sensitive modulo scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.258-267, June 21-25, 1993, Albuquerque, New Mexico, United States
• 11: Janak H. Patel , Edward S. Davidson, Improving the throughput of a pipeline by insertion of delays, Proceedings of the 3rd annual symposium on Computer architecture, p.159-164, January 19-21, 1976
• 12: C. Eisenbeis , W. Jalby , A. Lichnewsky, Squeezing more CPU performance out of a Cray-2 by Vector block scheduling, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.237-246, November 12-17, 1988, Orlando, Florida, United States
• 13: Qi Ning , Guang R. Gao, A novel framework of register allocation for software pipelining, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158519]
• 14: J. Ramanujam, Optimal Software Pipelining of Nested Loops, Proceedings of the 8th International Symposium on Parallel Processing, p.335-342, April 01, 1994
• 15: F.S. Hillier and G. J. Lieberman, Introduction to Mathematical Programming, McGraw-Hill, 1990.
• 16: James C. Tiernan, An efficient search algorithm to find the elementary circuits of a graph, Communications of the ACM, v.13 n.12, p.722-726, Dec. 1970 [doi>10.1145/362814.362819]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

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

General Terms:
Design, Performance