Register allocation for software pipelined multidimensional loops

ABSTRACT

This article investigates register allocation for software pipelined multidimensional loops where the execution of successive iterations from an n-dimensional loop is overlapped. For single loop software pipelining, the lifetimes of a loop variable in successive iterations of the loop form a repetitive pattern. An effective register allocation method is to represent the pattern as a vector of lifetimes (or a vector lifetime using Rau's terminology [Rau 1992]) and map it to rotating registers. Unfortunately, the software pipelined schedule of a multidimensional loop is considerably more complex and so are the vector lifetimes in it.

In this article, we develop a way to normalize and represent the vector lifetimes, which captures their complexity, while exposing their regularity that enables a simple solution. The problem is formulated as bin-packing of the multidimensional vector lifetimes on the surface of a space-time cylinder. A metric, called distance, is calculated either conservatively or aggressively to guide the bin-packing process, so that there is no overlapping between any two vector lifetimes, and the register requirement is minimized. This approach subsumes the classical register allocation for software pipelined single loops as a special case. The method has been implemented in the ORC compiler and produced code for the IA-64 architecture. Experimental results show the effectiveness. Several strategies for register allocation are compared and analyzed.

REFERENCES

• 1: Alexander Aiken , Alexandru Nicolau , Steven Novack, Resource-Constrained Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, v.6 n.12, p.1248-1270, December 1995 [doi>10.1109/71.476167]
• 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: Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989400]
• 5: 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
• 6: Steve Carr , Chen Ding , Philip Sweany, Improving Software Pipelining With Unroll-and-Jam, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.183, January 03-06, 1996
• 7: Gregory Chaitin, Register allocation and spilling via graph coloring, ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989403]
• 8: Wei-Kai Cheng , Youn-Long Lin, Code generation of nested loops for DSP processors with heterogeneous registers and structural pipelining, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.231-256, July 1999 [doi>10.1145/315773.315776]
• 9: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 10: A. Darte , Y. Robert, Constructive Methods for Scheduling Uniform Loop Nests, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.814-822, August 1994 [doi>10.1109/71.298207]
• 11: 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]
• 12: Douillet, A. and Gao, G. R. 2005. Register pressure in software-pipelined loop nests: Fast computation and impact on architecture design. In The 18th International Workshop on Languages and Compilers for Parallel Computing (LCPC'05). Hawthorne, NY, 17--31.
• 13: Alban Douillet , Guang R. Gao, Software-Pipelining on Multi-Core Architectures, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.39-48, September 15-19, 2007 [doi>10.1109/PACT.2007.64]
• 14: K. Ebcioğlu , Toshio Nakatani, A new compilation technique for parallelizing loops with unpredictable branches on a VLIW architecture, Selected papers of the second workshop on Languages and compilers for parallel computing, p.213-229, May 1990, Urbana, Illinois, United States
• 15: Gao, G. R., Ning, Q., and Dongen, V. V. 1993. Software pipelining for nested loops. ACAPS Tech Memo 53, School of Computer Science, McGill Univ., Montréal, Québec.
• 16: Laurie J. Hendren , Guang R. Gao , Erik R. Altman , Chandrika Mukerji, A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs, Proceedings of the 4th International Conference on Compiler Construction, p.176-191, October 05-07, 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: Intel. 2001. Intel IA-64 Architecture Software Developer's Manual. Vol. 1: IA-64 Application Architecture. Intel Corporation, Santa Clara, CA.
• 19: 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
• 20: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 21: Lawler, E. L., Lenstra, J. K., Khan, A. H. G. R., and Shmoys, D. B. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons.
• 22: Soo-Mook Moon , Kemal Ebcioğlu, Parallelizing nonnumerical code with selective scheduling and software pipelining, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.853-898, Nov. 1997 [doi>10.1145/267959.269966]
• 23: Kalyan Muthukumar , Gautam Doshi, Software Pipelining of Nested Loops, Proceedings of the 10th International Conference on Compiler Construction, p.165-181, April 02-06, 2001
• 24: J. Ramanujam, Optimal Software Pipelining of Nested Loops, Proceedings of the 8th International Symposium on Parallel Processing, p.335-342, April 01, 1994
• 25: 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]
• 26: 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]
• 27: Rau, B. R., Lee, M., Tirumalai, P. P., and Schlansker, M. S. 1992. Register allocation for modulo scheduled loops: Strategies, algorithms and heuristics. HP Labs Tech. rep. HPL-92-48, Hewlett-Packard Laboratories, Palo Alto, CA.
• 28: Hongbo Rong , Alban Douillet , R. Govindarajan , Guang R. Gao, Code Generation for Single-Dimension Software Pipelining of Multi-Dimensional Loops, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.175, March 20-24, 2004, Palo Alto, California
• 29: Rong, H. and Govindarajan, R. 2007. Advances in software piplining. In The Compiler Design Handbook: Optimization and Machine Code Generation, 2nd Ed. Y. N. Srikant and P. Shankar, Eds. CRC, Chapter 20.
• 30: Rong, H., Tang, Z., Govindarajan, R., Douillet, A., and Gao, G. R. 2007a. Single-dimension software pipelining for multi-dimensional loops. CAPSL Technical Memo, Department of Electrical and Computer Engineering, University of Delaware, Newark, DE. In ftp://ftp.capsl.udel.edu/pub/doc/memos/memo049.ps.gz.
• 31: Hongbo Rong , Zhizhong Tang , R. Govindarajan , Alban Douillet , Guang R. Gao, Single-dimension software pipelining for multidimensional loops, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.1, p.7-es, March 2007 [doi>10.1145/1216544.1216550]
• 32: Turkington, K., Masselos, K., Constantinides, G. A., and Leong, P. 2006. FPGA based acceleration of the linpack benchmark: A high level code transformation approach. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL). Madrid, Spain. IEEE, 1--6.
• 33: Jian Wang , Guang R. Gao, Pipelining-Dovetailing: A Transformation to Enhance Software Pipelining for Nested Loops, Proceedings of the 6th International Conference on Compiler Construction, p.1-17, April 24-26, 1996

INDEX TERMS

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

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

General Terms:
Algorithms, Languages

Keywords:
Software pipelining, register allocation