TY - GEN
T1 - Unfolding and retiming data-flow DSP programs for risc multiprocessor scheduling
AU - Chao, Liang Fang
AU - Sha, Edwin Hsing Mean
N1 - Publisher Copyright:
© 1992 IEEE.
PY - 1992
Y1 - 1992
N2 - Retiming and unfolding are two useful techniques which have been effectively applied in many fields. In this paper, we combine these two technique for the problem of rate-optimal scheduling for unit-Time DFG. A rutc-optimal retimable graph is a DFG such that after a legal retim-ing a rate-optimal schedule ran be obtained. For the case of unit-Time DFG, which is applicable to RISC multiprocessors, we improve the best known upper-bound for an unfolding factor which produces a rate-optimal retimable DFG, and we show that our result is (he minimum possible unfolding factor for rate-optimal schedules. Moreover, for any unfolding factor, the corresponding minimum rate is given by a simple criterion. Since we prove that the order of retiming and unfolding is irrelevant, efficient polynomial-Time retiming algorithms are obtained.
AB - Retiming and unfolding are two useful techniques which have been effectively applied in many fields. In this paper, we combine these two technique for the problem of rate-optimal scheduling for unit-Time DFG. A rutc-optimal retimable graph is a DFG such that after a legal retim-ing a rate-optimal schedule ran be obtained. For the case of unit-Time DFG, which is applicable to RISC multiprocessors, we improve the best known upper-bound for an unfolding factor which produces a rate-optimal retimable DFG, and we show that our result is (he minimum possible unfolding factor for rate-optimal schedules. Moreover, for any unfolding factor, the corresponding minimum rate is given by a simple criterion. Since we prove that the order of retiming and unfolding is irrelevant, efficient polynomial-Time retiming algorithms are obtained.
UR - https://www.scopus.com/pages/publications/84971459762
U2 - 10.1109/ICASSP.1992.226557
DO - 10.1109/ICASSP.1992.226557
M3 - 会议稿件
AN - SCOPUS:84971459762
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 565
EP - 568
BT - ICASSP 1992 - 1992 International Conference on Acoustics, Speech, and Signal Processing
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1992 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 1992
Y2 - 23 March 1992 through 26 March 1992
ER -