Rotation scheduling: a loop pipelining algorithm

Liang Fang Chao, Andrea LaPaugh, Edwin Hsing Mean Sha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

60 Scopus citations


We consider the resource-constrained scheduling of loops with inter-iteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis of the operations based on retiming. We propose two heuristics to perform rotation scheduling, and give experimental results showing that they have very good performance.

Original languageEnglish (US)
Title of host publicationProceedings - Design Automation Conference
PublisherPubl by IEEE
Number of pages7
ISBN (Print)0897915771
StatePublished - 1993
EventProceedings of the 30th ACM/IEEE Design Automation Conference - Dallas, TX, USA
Duration: Jun 14 1993Jun 18 1993

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0146-7123


OtherProceedings of the 30th ACM/IEEE Design Automation Conference
CityDallas, TX, USA

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Rotation scheduling: a loop pipelining algorithm'. Together they form a unique fingerprint.

Cite this