Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding

Keshab K Parhi, David G. Messerschmitt

Research output: Contribution to journalArticle

191 Citations (Scopus)

Abstract

This paper addresses rate-optimal compile-time multiprocessor scheduling of iterative data-flow programs suitable for real-time signal processing applications. Recursions or loops in these programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. In general, it may not be possible to schedule a specified iterative data-flow program rate-optimally. Retiming transformation may improve the iteration period of a schedule, but cannot guarantee the schedule to be rate-optimal. Systematic unfolding of iterative data-flow programs is proposed, and properties of unfolded data-flow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrency in iterative data-flow programs, and can reduce the iteration period. We introduce a special class of iterative data-flow programs, referred to as perfect-rate programs. Each loop in these programs has a single register (a register is also referred to as a delay in signal processing literature). Perfect-rate programs have the important property that they can always be scheduled rate-optimally (requiring no retiming or unfolding transformation). We show that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate-optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops, and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is also given.

Original languageEnglish (US)
Pages (from-to)178-195
Number of pages18
JournalIEEE Transactions on Computers
Volume40
Issue number2
DOIs
StatePublished - Jan 1 1991

Fingerprint

Optimal Scheduling
Unfolding
Data Flow
Signal processing
Scheduling
Iteration
Optimal Rates
Schedule
Signal Processing
Lowest common multiple
Multiprocessor Scheduling
Arbitrary
Concurrency
Multiprocessor
Recursion
Execution Time

Keywords

  • deterministic
  • Full-static rate-optimal schedules
  • intra-interation and inter-iteration precedence constraints
  • iteration bound
  • nonpreemptive multiprocessor schduling
  • optimum unfolding
  • perfect-rate data-flow programs
  • periodic
  • processor bounds
  • program unfolding
  • retiming real-time signal and image processing
  • static data-flow programming

Cite this

Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding. / Parhi, Keshab K; Messerschmitt, David G.

In: IEEE Transactions on Computers, Vol. 40, No. 2, 01.01.1991, p. 178-195.

Research output: Contribution to journalArticle

@article{d425dde172f8498689fefa52c067572a,
title = "Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding",
abstract = "This paper addresses rate-optimal compile-time multiprocessor scheduling of iterative data-flow programs suitable for real-time signal processing applications. Recursions or loops in these programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. In general, it may not be possible to schedule a specified iterative data-flow program rate-optimally. Retiming transformation may improve the iteration period of a schedule, but cannot guarantee the schedule to be rate-optimal. Systematic unfolding of iterative data-flow programs is proposed, and properties of unfolded data-flow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrency in iterative data-flow programs, and can reduce the iteration period. We introduce a special class of iterative data-flow programs, referred to as perfect-rate programs. Each loop in these programs has a single register (a register is also referred to as a delay in signal processing literature). Perfect-rate programs have the important property that they can always be scheduled rate-optimally (requiring no retiming or unfolding transformation). We show that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate-optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops, and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is also given.",
keywords = "deterministic, Full-static rate-optimal schedules, intra-interation and inter-iteration precedence constraints, iteration bound, nonpreemptive multiprocessor schduling, optimum unfolding, perfect-rate data-flow programs, periodic, processor bounds, program unfolding, retiming real-time signal and image processing, static data-flow programming",
author = "Parhi, {Keshab K} and Messerschmitt, {David G.}",
year = "1991",
month = "1",
day = "1",
doi = "10.1109/12.73588",
language = "English (US)",
volume = "40",
pages = "178--195",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "2",

}

TY - JOUR

T1 - Static Rate-Optimal Scheduling of Iterative Data-Flow Programs via Optimum Unfolding

AU - Parhi, Keshab K

AU - Messerschmitt, David G.

PY - 1991/1/1

Y1 - 1991/1/1

N2 - This paper addresses rate-optimal compile-time multiprocessor scheduling of iterative data-flow programs suitable for real-time signal processing applications. Recursions or loops in these programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. In general, it may not be possible to schedule a specified iterative data-flow program rate-optimally. Retiming transformation may improve the iteration period of a schedule, but cannot guarantee the schedule to be rate-optimal. Systematic unfolding of iterative data-flow programs is proposed, and properties of unfolded data-flow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrency in iterative data-flow programs, and can reduce the iteration period. We introduce a special class of iterative data-flow programs, referred to as perfect-rate programs. Each loop in these programs has a single register (a register is also referred to as a delay in signal processing literature). Perfect-rate programs have the important property that they can always be scheduled rate-optimally (requiring no retiming or unfolding transformation). We show that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate-optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops, and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is also given.

AB - This paper addresses rate-optimal compile-time multiprocessor scheduling of iterative data-flow programs suitable for real-time signal processing applications. Recursions or loops in these programs lead to an inherent lower bound on the achievable iteration period, referred to as the iteration bound. A multiprocessor schedule is rate-optimal if the iteration period equals the iteration bound. In general, it may not be possible to schedule a specified iterative data-flow program rate-optimally. Retiming transformation may improve the iteration period of a schedule, but cannot guarantee the schedule to be rate-optimal. Systematic unfolding of iterative data-flow programs is proposed, and properties of unfolded data-flow programs are studied. Unfolding increases the number of tasks in a program, unravels the hidden concurrency in iterative data-flow programs, and can reduce the iteration period. We introduce a special class of iterative data-flow programs, referred to as perfect-rate programs. Each loop in these programs has a single register (a register is also referred to as a delay in signal processing literature). Perfect-rate programs have the important property that they can always be scheduled rate-optimally (requiring no retiming or unfolding transformation). We show that unfolding any program by an optimum unfolding factor transforms any arbitrary program to an equivalent perfect-rate program, which can then be scheduled rate-optimally. This optimum unfolding factor for any arbitrary program is the least common multiple of the number of registers (or delays) in all loops, and is independent of the node execution times. An upper bound on the number of processors for rate-optimal scheduling is also given.

KW - deterministic

KW - Full-static rate-optimal schedules

KW - intra-interation and inter-iteration precedence constraints

KW - iteration bound

KW - nonpreemptive multiprocessor schduling

KW - optimum unfolding

KW - perfect-rate data-flow programs

KW - periodic

KW - processor bounds

KW - program unfolding

KW - retiming real-time signal and image processing

KW - static data-flow programming

UR - http://www.scopus.com/inward/record.url?scp=0026108176&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026108176&partnerID=8YFLogxK

U2 - 10.1109/12.73588

DO - 10.1109/12.73588

M3 - Article

VL - 40

SP - 178

EP - 195

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 2

ER -