NDLI: Single-dimension software pipelining for multidimensional loops

Content Provider	ACM Digital Library
Author	Tang, Zhizhong Gao, Guang R. Douillet, Alban Rong, Hongbo Govindarajan, R.
Copyright Year	2007
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.
File Format	PDF
ISSN	15443566
e-ISSN	15443973
DOI	10.1145/1216544.1216550
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Architecture and Code Optimization (TACO)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2007-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Software pipelining Loop transformation Modulo scheduling
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Single-dimension software pipelining for multidimensional loops (2004)

Fast modulo scheduler utilizing patternized routes for coarse-grained reconfigurable architectures

Evaluator-executor transformation for efficient pipelining of loops with conditionals

Iterative modulo scheduling: an algorithm for software pipelining loops

Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops (1994)

Improving performance of nested loops on reconfigurable array processors

Single-dimension software pipelining for multi-dimensional loops.

Single-dimension software pipelining for multi-dimensional loops (2004)

Predicate-aware, makespan-preserving software pipelining of scheduling tables

Single-dimension software pipelining for multidimensional loops

Similar Documents

Single-dimension software pipelining for multidimensional loops (2004)

Fast modulo scheduler utilizing patternized routes for coarse-grained reconfigurable architectures

Evaluator-executor transformation for efficient pipelining of loops with conditionals

Iterative modulo scheduling: an algorithm for software pipelining loops

Iterative Modulo Scheduling: An Algorithm for Software Pipelining Loops (1994)

Improving performance of nested loops on reconfigurable array processors

Single-dimension software pipelining for multi-dimensional loops.

Single-dimension software pipelining for multi-dimensional loops (2004)

Predicate-aware, makespan-preserving software pipelining of scheduling tables

Single-dimension software pipelining for multidimensional loops