Single-dimension software pipelining for multidimensional loops

ABSTRACT

Traditionally, software pipelining is applied either to the innermost loop of a given loop nest or from the innermost loop to outer loops. This paper proposes a three-step approach, called single-dimension software pipelining (SSP), to software pipeline a loop nest at an arbitrary loop level that has a rectangular iteration space and contains no sibling inner loops in it. The first step identifies the most profitable loop level for software pipelining in terms of initiation rate, data reuse potential, or any other optimization criteria. The second step simplifies the multidimensional data-dependence graph (DDG) of the selected loop level into a one-dimensional DDG and constructs a one-dimensional (1D) schedule. Based on the one-dimensional schedule, the third step derives a simple mapping function that specifies the schedule time for the operation instances in the multidimensional loop. The classical modulo scheduling is subsumed by SSP as a special case. SSP is also closely related to hyperplane scheduling, and, in fact, extends it to be resource constrained. We prove that SSP schedules are correct and at least as efficient as those schedules generated by traditional modulo scheduling methods. We extend SSP to schedule imperfect loop nests, which are most common at the instruction level. Multiple initiation intervals are naturally allowed to improve execution efficiency. Feasibility and correctness of our approach are verified by a prototype implementation in the ORC compiler for the IA-64 architecture, tested with loop nests from Livermore and SPEC2000 floating-point benchmarks. Preliminary experimental results reveal that, compared to modulo scheduling, software pipelining at an appropriate loop level results in significant performance improvement. Software pipelining is beneficial even with prior loop transformations.

REFERENCES

• 1: Alexander Aiken , Alexander Nicolau, Fine-grain parallelization and the wavefront method, Selected papers of the second workshop on Languages and compilers for parallel computing, p.1-16, May 1990, Urbana, Illinois, United States
• 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: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 5: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 6: Steve Carr , Kathryn S. McKinley , Chau-Wen Tseng, Compiler optimizations for improving data locality, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.252-262, October 05-07, 1994, San Jose, California, United States
• 7: 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
• 8: 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]
• 9: Alain Darte , Robert Schreiber , B. Ramakrishna Rau , Frédéric Vivien, Constructing and exploiting linear schedules with prescribed parallelism, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.1, p.159-172, January 2002 [doi>10.1145/504914.504921]
• 10: Paul Feautrier, Automatic Parallelization in the Polytope Model, The Data Parallel Programming Model: Foundations, HPF Realization, and Scientific Applications, p.79-103, January 1996
• 11: Gao, G. R., Ning, Q., and Van Dongen, V. 1993. Software pipelining for nested loops. ACAPS Tech Memo 53, School of Computer Science, McGill Univ., Montréal, Québec.
• 12: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 13: R. Govindarajan , Erik R. Altman , Guang R. Gao, A Framework for Resource-Constrained Rate-Optimal Software Pipelining, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1133-1149, November 1996 [doi>10.1109/71.544355]
• 14: 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
• 15: Intel. 2001. Intel IA-64 Architecture Software Developer's Manual, Vol. 1: IA-64 Application Architecture. Intel Corporation, Santa Clara, CA.
• 16: Ken Kennedy , Kathryn S. McKinley, Optimizing for parallelism and data locality, Proceedings of the 6th international conference on Supercomputing, p.323-334, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143427]
• 17: 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
• 18: 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]
• 19: 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]
• 20: 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
• 21: Nelson Luiz Passos , Edwin Hsing-Mean Sha, Achieving Full Parallelism Using Multidimensional Retiming, IEEE Transactions on Parallel and Distributed Systems, v.7 n.11, p.1150-1163, November 1996 [doi>10.1109/71.544356]
• 22: Darin Petkov , Randolph E. Harr , Saman P. Amarasinghe, Efficient Pipelining of Nested Loops: Unroll-and-Squash, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.136, April 15-19, 2002
• 23: J. Ramanujam, Optimal Software Pipelining of Nested Loops, Proceedings of the 8th International Symposium on Parallel Processing, p.335-342, April 01, 1994
• 24: 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]
• 25: 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]
• 26: 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
• 27: Hongbo Rong , Zhizhong Tang , R. Govindarajan , Alban Douillet , Guang R. Gao, Single-Dimension Software Pipelining for Multi-Dimensional Loops, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.163, March 20-24, 2004, Palo Alto, California
• 28: Hongbo Rong , Alban Douillet , Guang R. Gao, Register allocation for software pipelined multi-dimensional loops, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 29: Rong, H., Tang, Z., Govindarajan, R., Douillet, A., and Gao, G. R. 2007. Single-dimension software pipelining for multi-dimensional loops. CAPSL technical memo, Department of Electrical and Computer Engineering, University of Delaware, Newark, Delaware. January. In ftp://ftp.capsl.udel.edu/pub/doc/memos/memo049.ps.gz.
• 30: 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
• 31: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 32: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France

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, loop transformation, modulo scheduling