Rate-Optimal DSP Synthesis by Pipeline and Minimum Unfolding
DSP algorithms w i t h recursions o r feedback loops lead t o a n inheren t lower bound o n t h e achievable i terat ion period, called a n iteration period bound. A hardware DSP synthesis schedule is rate-optimal if t he i terat ion period equals t h e i terat ion period bound, and n o fa s t e r realization exis ts even w h e n infinite processor s are available. Sys t emat i c unfolding of t h e recursive data p o w graph is presented. T h e unfolding technique increases t h e number of tasks , unravels t he hidd e n concurrency in the recursive data f l ow graph, and reduces t h e i terat ion period. T h e compu ta t ion paths longer t h a n i terat ion period bound are pipelined and allocated o n dif ferent processors w i th in the i terat ion period bound. B y use of t h e opt imal unfolding transf o r m a t i o n , a recursive data f l ow graph i s equivalent t o a n a-unfolded data f l ow graph wh ich t h e n be scheduled rate-optimally. T h i s op t ima l unfolding fac tor i s determ i n a t e and smaller t h a n all previous works and theref o re reduces m o r e overhead. All experimental results show opt imal per formance of t he rate-optimal design