On realistic and efficient scheduling of DSP algorithms onto multiprocessor architectures

Available strategies for static scheduling of DSP algorithms onto multiprocessor (general purpose and DSP-based) systems are discussed. It is found that simplistic interprocessor communication (IPC) modeling and the absence of precedence analysis are major reasons for unrealistic and not always efficient solutions. The authors propose a mapping scheme based on clustering and various realistic scheduling strategies in order to minimize the runtime of the DSP algorithm. The scheme, called NODUST (for NOde DUplication STrategy), incorporates modeling of the target architecture in terms of nonsimplistic IPC times, which makes the solutions more realistic. The NODUST algorithm provides superior speedup and better processor utilizations in all possible cases compared to the results of T. C. Hu (1961). The compile time for the Hu strategy, on the other hand, is lower than that of NODUST. The speedups do not vary significantly when one moves from the M68000 to the ADSP 2101 environment