Improved spill code generation for software pipelined loops

ABSTRACT

Software pipelining is a loop scheduling technique that extracts parallelism out of loops by overlapping the execution of several consecutive iterations. Due to the overlapping of iterations, schedules impose high register requirements during their execution. A schedule is valid if it requires at most the number of registers available in the target architecture. If not, its register requirements have to be reduced either by decreasing the iteration overlapping or by spilling registers to memory. In this paper we describe a set of heuristics to increase the quality of register-constrained modulo schedules. The heuristics decide between the two previous alternatives and define criteria for effectively selecting spilling candidates. The heuristics proposed for reducing the register pressure can be applied to any software pipelining technique. The proposals are evaluated using a register-conscious software pipeliner on a workbench composed of a large set of loops from the Perfect Club benchmark and a set of processor configurations. Proposals in this paper are compared against a previous proposal already described in the literature. For one of these processor configurations and the set of loops that do not fit in the available registers (32), a speed-up of 1.68 and a reduction of the memory traffic by a factor of 0.57 are achieved with an affordable increase in compilation time. For all the loops, this represents a speed-up of 1.38 and a reduction of the memory traffic by a factor of 0.7.

REFERENCES

• 1: A. Aiken and A. Nicolau. A realistic resourceconstrained software pipelining algorithm. Advances in Languages and Compilers for Parallel Processing, pages 274-290, 1991.
• 2: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 3: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 4: E. Ayguadd, C. Barrado, A. Gonzelez, J. Labarta, J. Llosa, D. L6pez, S. Moreno, D. Padua, F.Reig, Q. Riera, and M. Valero. Ictineo: a tool for instruction level parallelism research. Technical Report UPC-DAC- 96-61, Universitat Politacnica de Catalunya, December 1996.
• 5: D. Bernstein , M. Golumbic , y. Mansour , R. Pinter , D. Goldin , H. Krawczyk , I. Nahshon, Spill code minimization techniques for optimizing compliers, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.258-263, June 19-23, 1989, Portland, Oregon, United States
• 6: M. Berry, D. Chen, P. Koss, and D. Kuck. The Perfect Club benchmarks: Effective performance evaluation of supercomputers. Technical Report 827, Center for Supercomputing Research and Development, November 1988.
• 7: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 8: 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]
• 9: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 10: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 11: A. Charlesworth. An approach to scientific array processing: The architectural design of the AP120B/FPS- 164 family. Computer, 14(9):18-27, 1981.
• 12: James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
• 13: James C. Dehnert , Ross A. Towle, Compiling for the Cydra 5, The Journal of Supercomputing, v.7 n.1-2, p.181-227, May 1993 [doi>10.1007/BF01205184]
• 14: Alexandre E. Eichenberger , Edward S. Davidson, Stage scheduling: a technique to reduce the register requirements of a modulo schedule, Proceedings of the 28th annual international symposium on Microarchitecture, p.338-349, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 15: C. Eisenbeis, S. Lelait, and B. Marmol. The meeting graph: a new model for loop cyclic register allocation. In Prec. of the Fifth Workshop on Compilers for Parallel Computers (CPC95), pages 503-516, June 1995.
• 16: L. Hendren, G. Gao, E. Altman, and C. Mukerji. Register allocation using cyclic interval graphs: A new approach to an old problem. ACAPS Tech. Memo 33, Advanced Computer Architecture and Program Structures Group, McGill University, 1992.
• 17: 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
• 18: Suneel Jain, Circular scheduling: a new technique to perform software pipelining, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.219-228, June 24-28, 1991, Toronto, Ontario, Canada
• 19: Monica S. Lam, A Systolic Array Optimizing Compiler, Kluwer Academic Publishers, Norwell, MA, 1989
• 20: Josep Llosa , Mateo Valero , Eduard Ayguadé, Heuristics for register-constrained software pipelining, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.250-261, December 02-04, 1996, Paris, France
• 21: Josep Llosa , Eduard Ayguadé , Mateo Valero, Quantitative Evaluation of Register Pressure on Software Pipelined Loops, International Journal of Parallel Programming, v.26 n.2, p.121-142, April 1, 1998 [doi>10.1023/A:1018743102645 ]
• 22: Josep Llosa , Mateo Valero , Eduard Ayguadé , Antonio González, Hypernode reduction modulo scheduling, Proceedings of the 28th annual international symposium on Microarchitecture, p.350-360, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 23: 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]
• 24: S. Ramakrishnan. Software pipelining in PA-RISC compilers. Hewlett-Packard Journal, pages 39-45, July 1992.
• 25: 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
• 26: 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
• 27: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 28: John Ruttenberg , G. R. Gao , A. Stoutchinin , W. Lichtenstein, Software pipelining showdown: optimal vs. heuristic methods in a production compiler, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.1-11, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 29: Jian Wang , Andreas Krall , M. Anton Ertl , Christine Eisenbeis, Software pipelining with register allocation and spilling, Proceedings of the 27th annual international symposium on Microarchitecture, p.95-99, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192734]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Design, Management, Performance

Keywords:
instruction-level parallelism, register allocation, software pipelining, spill code