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 Citations (Scopus)

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

Scheduling
Signal processing

Cite this

Fully-static rate-optimal scheduling of iterative data-flow programs via optimum unfolding. / Parhi, Keshab K; Messerschmitt, David G.

In: Proceedings of the International Conference on Parallel Processing, Vol. 1, 01.12.1989, p. 209-216.

Research output: Contribution to journalArticle

@article{0aea366473f746689d03529c6696673f,
title = "Fully-static rate-optimal scheduling of iterative data-flow programs via optimum unfolding",
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.",
author = "Parhi, {Keshab K} and Messerschmitt, {David G.}",
year = "1989",
month = "12",
day = "1",
language = "English (US)",
volume = "1",
pages = "209--216",
journal = "Proceedings of the International Conference on Parallel Processing",
issn = "0190-3918",

}

TY - JOUR

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

AU - Parhi, Keshab K

AU - Messerschmitt, David G.

PY - 1989/12/1

Y1 - 1989/12/1

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

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

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

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

M3 - Article

VL - 1

SP - 209

EP - 216

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

SN - 0190-3918

ER -