A fast task-to-processor assignment heuristic for real-time multiprocessor digital signal processing applications

The optimal assignment of the tasks to the processors to minimize total delay in a multiprocessor digital signal processing (DSP) architecture is extremely difficult, particularly for systems of many (e.g. 100) tasks. Two factors especially complicate the problem: (1) the multiprocessor architecture affects the inter-processor communication times, and (2) the specific assignment of tasks to processors affects the inter-task communication times. We develop a fast heuristic for assigning tasks to processors. There are two main ingredients in our method: (i) the choice of a useful general-purpose multiprocessor architecture for DSP applications, and (ii) an adaptive list-ordering heuristic which takes advantage of knowledge of the inter-processor communication characteristics of the chosen architecture. Examples are given, including comparisons to exact branch-and-bound methods, and a large sonar example.