Multiprocessor scheduling of iterative data-flow graphs for signal processing applications

Abstract

The increasing demand of real-time processing in modern digital signal processing (DSP) applications requires a great deal of computing capabilities which can not be met using conventional single processor systems. A promising approach to satisfy this requirement is the parallel procession on multiprocessor systems, as there are many commercially available offthe-shelf high-performance digital signal processors. In order to process any problem on a multiprocessor system a scheduling method has to be developed, which consists of the two subproblems that are strongly inter-related: the time scheduling and processor assignment. In this work, we are concerned withe the development of a systematic methodology for mapping iterative DSP algorithms given as the data-flow graphs (DFGs) onto multiprocessor systems. In the conventional scheduling problems the tasks are computed only once and the objective of the scheduling is to minimize the schedule length. On the other hand, DSP algorithms are repeated infinitely many times in a periodic fashion. Therefore, the scheduling algorithm should be able to consider the overlapping of tasks between successive iterations. In addition, the particular properties of DSP applications allow the deterministic, static scheduling. The contributions of this work are as follows. First, the analysis methods for a given DFG are presented, which include the method for evaluating the iteration period bound and locating the critical cycle, and the method for analyzing the scheduling time space of each task. Second, two scheduling techniques which are applicable when the interprocessor communication delays are negligible with respect to the execution times of tasks are suggested. One is a formal approach based on the 0-1 integer linear programming formulation to obtain a schedule that uses the minimum number of processors. It is only useful for moderate sized problems, but we can formalize the scheduling problem efficiently with it. The other i...