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

Keshab K. Parhi, David G. Messerschmitt

Research output: Contribution to journalArticle

194 Scopus citations

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 - Feb 1991

    Fingerprint

Keywords

  • Full-static rate-optimal schedules
  • deterministic
  • 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