Rotation scheduling: A loop pipelining algorithm

Liang Fang Chao, Andrea S. Lapaugh, Edwin Hsing Mean Sha

Research output: Contribution to journalArticlepeer-review

95 Scopus citations

Abstract

We consider the resource-constrained scheduling of loops with interiteration 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 DFG's using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for 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)
Pages (from-to)229-239
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume16
Issue number3
DOIs
StatePublished - 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Keywords

  • High-level synthesis
  • Loop pipelining
  • Parallel compiler
  • Retiming
  • Scheduling

Fingerprint

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

Cite this