An efficient multiprocessor implementation scheme for real-time DSP algorithms

An algorithm to derive minimum-processor implementation for real-time DSP algorithms is proposed. In order to make the number of possible schedules finite and to assure the optimal schedule within the search space, the authors define a novel notion of cutoff time. All the possible schedules can find an equivalent schedule that finishes before cutoff time. Next, they apply all efficient heuristic periodic scheduling and fully static allocation algorithms derived from two generic problem solving heuristics developed in a branch of artificial intelligence research called planning. Extensive benchmarks have been tested and the results are most encouraging