Rotation scheduling: a loop pipelining algorithm

Liang Fang Chao, Andrea Suzanne LaPaugh, Edwin Hsing Mean Sha

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

56 Scopus citations

Abstract

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
Pages566-572
Number of pages7
ISBN (Print)0897915771
StatePublished - Jan 1 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

Other

OtherProceedings of the 30th ACM/IEEE Design Automation Conference
CityDallas, TX, USA
Period6/14/936/18/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

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

  • Cite this

    Chao, L. F., LaPaugh, A. S., & Sha, E. H. M. (1993). Rotation scheduling: a loop pipelining algorithm. In Proceedings - Design Automation Conference (pp. 566-572). (Proceedings - Design Automation Conference). Publ by IEEE.