Strategies for Realistic and Efficient Static Scheduling of Data Independent Algorithms onto Multiple Digital Signal Processors.

The ever increasing complexity of Digital Signal Processing and other data independent scientific computations means that single processor systems in many cases do not provide the required computational capacity in order to respect given time constraints. Architectures with multiple DSP processors are therefore becoming popular alternatives. This raises, however, a natural requirement for formal methods which can help the system designer to create realistic and efficient multiprocessor solutions. Of particular importance in this design process is static multiprocessor scheduling which 1) assigns nodes (i.e., subalgorithms) to the individual processors, 2) specifies the node execution order, and 3) on the basis of estimated execution and communication times calculates invocation times for the individual nodes. We have found no or very little reported work on 1) the overall formal design trajectory, 2) realistic strategies for static multiprocessor scheduling of DSP algorithms, and 3) gu..