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 singledimension 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 datadependence graph (DDG) of the selected loop level into a one-dimensional DDG and constructs a Extension of Conference Paper based on Single-Dimension Software Pipelining for MultiDimensional Loops, by H. Rong, Z. Tang, R. Govindarajan, A. Douillet, and G. R. Gao, which appears in CGO'04 Proceedings of the International Symposium on Code Generation and Optimization, IEEE Computer Society, Washington, D.C. This version extends scheduling to imperfect loop nests, introduces scheduling with multiple initiation intervals, connects the method with hyperplane scheduling, implements it in a production-quality open-source compiler, and reports additional performance numbers. There is a major addition in Section 5.1 and 5.2. Sections 5.4, 6 and 7 are new. Authors' addresses: Hongbo Rong, Microsoft, Redmond, Washington 98052; email: hongbor@ microsoft.com. Zhizhong Tang, Tsinghua University, Beijing, China; email: tzz-dcs@tsinghua. edu.cn. R. Govindarajan, Indian Institute of Science, Bangalore, India; email: govind@serc.iisc. ernet.in. Alban Douillet, Hewlett-Packard Co., Palo Alto, California 56225; email: alban.douillet@hp.com. Guang R. Gao, University of Delaware, Newark, Delaware 19716; email: ggao@capsl.udel.edu. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 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.
Rong et al. REF propose a method to construct a software pipeline from an arbitrarily deep loop nest, whereas the traditional one is applied to the innermost loop or from the innermost to outer loops.
Single-dimension software pipelining for multidimensional loops
TACO
Computer Science