Scheduling of a class of DSP algorithms for real-time processing on a multiprocessor architecture: actual versus ideal I/O

Through the analysis of a data-flow-graph representation of an algorithm, the recent work by P.W. Lee (Ph.D. dissertation, Rutgers Univ., NJ, 1988) produces static, nonpreemptive schedules capable of implementing the algorithm on a multiple-processor system. These schedules are based on the assumptions that algorithms of the type that are typical of a class of digital signal processing (DSP) algorithms are computation bound (as opposed to I/O bound) and that data transfer (I/O operations) occurs instantaneously. This raises the question of the effects on the efficiency of the multiprocessor´s utilization as the execution of the algorithm changes from computation bound to I/O bound. In the present work the author examines these effects for two cases of an algorithm (typical of this class of DSP algorithms). These cases are with and without a dominant run-time task, where a dominant run-time task is characterized by a far larger execution time than any other task in the algorithm. It is concluded that the ideal I/O assumption put forth by Lee is valid for software structures that exhibit dominant tasks