Fully-static rate-optimal scheduling of iterative data-flow programs via optimum unfolding

Keshab K Parhi, David G. Messerschmitt

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

Rate-optimal multiprocessor scheduling of iterative data-flow signal processing programs is addressed. A schedule is rate-optimal if the iteration period of the schedule is same as the iteration period bound. Retiming transformation redistributes the delays in iterative data-flow programs and improves the scheduling time of each iteration but does not guarantee that schedules will be rate-optimal. Unfolding of dataflow programs uses interiteration concurrency and can reduce the iteration period of multiprocessor schedules. It is shown that unfolding any dataflow program beyond a certain factor does not lead to any further reduction in the execution time. It is shown that this optimum unfolding factor is given by the least common multiple of the loop delay counts in the dataflow program graph. It is also shown that unfolding the optimum unfolding factor reduces any iterative dataflow program, which can always be scheduled rate-optimally.

Original languageEnglish (US)
Pages (from-to)209-216
Number of pages8
JournalProceedings of the International Conference on Parallel Processing
Volume1
StatePublished - Dec 1 1989

Fingerprint Dive into the research topics of 'Fully-static rate-optimal scheduling of iterative data-flow programs via optimum unfolding'. Together they form a unique fingerprint.

  • Cite this