Fully static multiprocessor realization for real-time recursive DSP algorithms

A systematic approach to implement a real time recursive digital signal processing algorithm on a dedicated multiprocessor array is presented. First, the authors unfold the algorithm so that its corresponding dependence graph becomes a newly defined generalized perfect rate graph. They prove that the dependence graph of a recursive algorithm admits a desirable rate optimal, full static multiprocessor implementation if and only if it is a generalized perfect rate graph. Based on these results, an efficient heuristic algorithm is presented to perform optimal multi-processor scheduling and task assignment so that the number of processors required is minimized