TASK ALLOCATION AND SCHEDULING MODELS FOR MULTIPROCESSOR DIGITAL SIGNAL-PROCESSING

This paper presents models and techniques for the task allocation and scheduling problem, subject to task precedence, memory requirements, and interprocessor communication costs. Traditional models assume sequential I/O and computing activities, and linear memory requirements. The new models take into account the special characteristics of new architectures and may handle both sequential I/O and program execution and parallel I/O and program execution within a processor. Furthermore, both linear and nonlinear memory requirements may be modeled. The models also take into special consideration the unique requirements and characteristics of digital signal processing applications. By distinguishing between tasks that require all the output data from a predecessor before they begin execution (for example, an FFT) and tasks that require only partial data (for example, filtering applications), our models are more realistic and the accuracy and efficiency of our schedules are further improved. Both periodic and nonperiodic schedules are considered. Periodic schedules maximize the throughput, while nonperiodic schedules minimize the computation time. A simple branch and bound technique is presented, and it is applied to the solution of the task allocation problem. The algorithm incorporates simple forward and backward searching techniques from the theory of 0-1 linear programming, and can easily be adapted to fit any of the scheduling models by simply modifying its cost function. Various examples are also presented. © 1990 IEEE