DocumentCode :
1190770
Title :
Rate optimal scheduling of recursive DSP algorithms by unfolding
Author :
Wang, Duen-Jeng ; Hu, Yu Hen
Author_Institution :
Dept. of Electr. & Comput. Eng., Wisconsin Univ., Madison, WI, USA
Volume :
41
Issue :
10
fYear :
1994
fDate :
10/1/1994 12:00:00 AM
Firstpage :
672
Lastpage :
675
Abstract :
We propose a novel criterion called modified generalized perfect rate graph (MGPRG) to facilitate efficient synthesis of recurrent digital signal processing (RDSP) algorithms on application specific multiprocessor systems. We prove that a rate optimal schedule, which is a multiprocessor realization with maximum throughput rate, exists if and only if the dependence graph of the corresponding RDSP algorithm is unfolded sufficient number of times to satisfy the MGPRG condition. We show that MGPRG is a more general and unified criterion compared to earlier proposed criteria. An advantage of MGPRG is that the original algorithm needs not to be unfolded too many times before it can be guaranteed to have a rate optimal schedule. Consequently, the resulting MGPRG will consist of fewer nodes and edges, making it easier to find the rate optimal schedule
Keywords :
graph theory; parallel algorithms; processor scheduling; signal processing; application specific multiprocessor systems; dependence graph; maximum throughput rate; modified generalized perfect rate graph; rate optimal scheduling; recurrent digital signal processing algorithms; recursive DSP algorithms; unfolding; Digital signal processing; Iterative algorithms; Multiprocessing systems; Optimal scheduling; Sampling methods; Scheduling algorithm; Signal processing algorithms; Signal synthesis; Sufficient conditions; Throughput;
fLanguage :
English
Journal_Title :
Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on
Publisher :
ieee
ISSN :
1057-7122
Type :
jour
DOI :
10.1109/81.329729
Filename :
329729
Link To Document :
بازگشت