Single-Dimension Software Pipelining for Multi-Dimensional Loops

• Main Authors: Rong, Hongbo, Tang, Zhizhong, Govindarajan, R., Douillet, Alban, Gao, Guang R.
• Format: Conference Proceeding
• Language: English
• Subjects: Software and its engineering > Software notations and tools > General programming languages > Language features > Patterns; Software and its engineering > Software organization and properties > Contextual software domains > Operating systems > Process management > Scheduling; Software and its engineering > Software organization and properties > Software system structures > Distributed systems organizing principles > Client-server architectures; Software and its engineering > Software organization and properties > Software system structures > Software architectures
• DOI: 10.5555/977395.977657

Traditionally, software pipelining is applied either to theinnermost loop of a given loop nest or from the innermostloop to outer loops. In this paper, we propose a three-stepapproach, called Single-dimension Software Pipelining(SSP), to software pipeline a loop nest at an arbitraryloop level.The first step identifies the most profitable loop level forsoftware pipelining in terms of initiation rate or data reusepotential. The second step simplifies the multi-dimensionaldata-dependence graph (DDG) into a 1-dimensional DDGand constructs a 1-dimensional schedule for the selectedloop level. The third step derives a simple mapping functionwhich specifies the schedule time for the operations of themulti-dimensional loop, based on the 1-dimensional schedule.We prove that the SSP method is correct and at least asefficient as other modulo scheduling methods.We establish the feasibility and correctness of our approachby implementing it on the IA-64 architecture. Experimentalresults on a small number of loops show significantperformance improvements over existing modulo schedulingmethods that software pipeline a loop nest from the innermostloop.