Scheduling and task allocation for parallel digital signal processing architectures

The authors present models and techniques for the task and I/O allocation and scheduling problem, subject to task precedence, memory requirements, and interprocessor communication costs. The models take into account the special characteristics of new architectures and can handle both sequential and parallel I/O and program execution within a processor. Both linear and nonlinear memory requirements can be modeled. By distinguishing between tasks that require all the output data from a predecessor before they begin execution and tasks that require only partial data, the models are more realistic and the accuracy and efficiency of the schedules is further improved. A simple branch-and-bound technique is presented, and it is applied to the solution of the task allocation problem. An example from the scheduling of a measurement application that includes filtering and FFT operations is also presented