Rotation scheduling: A loop pipelining algorithm

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

doi:10.1109/43.594829

Rotation scheduling: A loop pipelining algorithm

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

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	229-239
Number of pages	11
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	16
Issue number	3
DOIs	https://doi.org/10.1109/43.594829
State	Published - 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

Access to Document

10.1109/43.594829

Cite this

@article{88d8ee7368434937b616b96c69d7765f,

title = "Rotation scheduling: A loop pipelining algorithm",

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.",

keywords = "High-level synthesis, Loop pipelining, Parallel compiler, Retiming, Scheduling",

author = "Chao, \{Liang Fang\} and Lapaugh, \{Andrea S.\} and Sha, \{Edwin Hsing Mean\}",

note = "Funding Information: Manuscript received June 22, 1993; revised December 22, 1996. This paper was recommended by Associate Editor, M. McFarland. This work was supported in part by DARPA/ONR Contract N00014-88-K-0459 and by the National Science Foundation under Grant MIP90-23542. L.-F. Chao is with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 46556 USA. A. S. LaPaugh is with the Department of Computer Science, Princeton University, Princeton, NJ 08544 USA. E. H.-M. Sha is with the Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556 USA. Publisher Item Identifier S 0278-0070(97)04740-4. Copyright: Copyright 2011 Elsevier B.V., All rights reserved.",

year = "1997",

doi = "10.1109/43.594829",

language = "English (US)",

volume = "16",

pages = "229--239",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Rotation scheduling

T2 - A loop pipelining algorithm

AU - Chao, Liang Fang

AU - Lapaugh, Andrea S.

AU - Sha, Edwin Hsing Mean

N1 - Funding Information: Manuscript received June 22, 1993; revised December 22, 1996. This paper was recommended by Associate Editor, M. McFarland. This work was supported in part by DARPA/ONR Contract N00014-88-K-0459 and by the National Science Foundation under Grant MIP90-23542. L.-F. Chao is with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 46556 USA. A. S. LaPaugh is with the Department of Computer Science, Princeton University, Princeton, NJ 08544 USA. E. H.-M. Sha is with the Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556 USA. Publisher Item Identifier S 0278-0070(97)04740-4. Copyright: Copyright 2011 Elsevier B.V., All rights reserved.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

KW - High-level synthesis

KW - Loop pipelining

KW - Parallel compiler

KW - Retiming

KW - Scheduling

UR - https://www.scopus.com/pages/publications/0031097278

UR - https://www.scopus.com/pages/publications/0031097278#tab=citedBy

U2 - 10.1109/43.594829

DO - 10.1109/43.594829

M3 - Article

AN - SCOPUS:0031097278

SN - 0278-0070

VL - 16

SP - 229

EP - 239

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 3

ER -

Rotation scheduling: A loop pipelining algorithm

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this