Software pipelining with register allocation and spilling

ABSTRACT

This paper studies the problem of simultaneous register allocation and software pipelining. We present the Register Requirement Graph to dynamically reflect the register requirement during software pipelining and develop a Register-Pressure-Sensitive (RPS) scheduling technique. Three algorithms—RPS without spilling, RPS with spilling and software pipelining with a limited number of registers—are proposed. The preliminary experimental results show the efficiency of the three algorithms.

REFERENCES

• 1: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 2: A.E. Charlesworth. An approach to scientific array processing: The architecture design of the ap-120b/fps-164 family. Computer, pages 18-27, September 1981.
• 3: Qi Ning and Guang R. Gao. A novel framework of register allocation for software pipelining. Technical Report ACAPS Technical Memo 42, McGill University, 1993.
• 4: 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
• 5: Jian Wang , Christine Eisenbeis , Martin Jourdan , Bogong Su, Decomposed software pipelining: a new perspective and a new approach, International Journal of Parallel Programming, v.22 n.3, p.351-373, June 1994 [doi>10.1007/BF02577737]
• 6: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.0 General

  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:
Algorithms, Experimentation, Measurement, Performance

Keywords:
instruction-level parallelism, loop scheduling, register allocation, register spilling, software pipelining