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 off-the-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 with 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 is a heuristic scheduling method obtained by extending the work due to [PrkI92] to the case of iterative recursive DFGs. We introduced an implicit sorting technique to efficiently represent the current status in a scheduling process and proposed the "node-locking" scheme instead of the original "tuple-locking" in the iteration steps of the algorithm. We show that due to the combined effects of the two techniques the resulting algorithm runs fast and its scheduling results are less sensitive to the selection of the reference node chosen for analyzing the scheduling time space. Finally, a heuristic scheduling method for non-negligible interprocessor communication delays is proposed, which simultaneously performs the time scheduling and the processor assignment. This is an extension of our scheduling method that has been suggested for negligible interprocessor communication delays. Also, an implementation method of the resulting schedule on a shared multi-bus system has been suggested to minimize the number of required buses.
현대의 디지탈 신호처리 응용분야에서 실시간처리의 필요성이 크게 증가하고 있으나 한 개의 프로세서만을 사용하는 기존의 시스템에서는 이러한 요구에 부합되는 계산능력을 제공하기 힘들다. 이에 대한 유망한 해결책으로 다중프로세서 시스템에서의 병렬처리를 들 수 있는데, 이는 반도체 제조기술의 발전에 따라 성능이 뛰어나고 프로그램이 가능한 디지탈 신호처리기들을 손쉽게 사용할 수 있기 때문이다.
본 논문은 반복 데이터 흐름 그래프(DFG)로 표현되는 신호처리 알고리즘을 다중 프로세서 시스템에 스케줄하는 체계적인 방법에 대하여 다룬다. 신호처리 알고리즘은 일정한 주기를 갖고 반복적으로 수행되므로, 스케줄 길이(schedule length)를 최적화하려는 일반적인 스케줄 문제와는 달리 스케줄된 결과가 반복될 때 겹침(overlapping)이 생기는 경우를 고려해 주어야 한다.
먼저, 주어진 DFG를 해석하는 방법을 제시했다. 사이클(cycle)을 포함하는 DFG의 경우 무한개의 프로세서를 사용하더라도 반복 주기를 임의로 짧게 할 수 없는데, 그 반복 주기의 한계 값 및 해당 사이클을 찾는 방법과 각 task가 움직일 수 있는 시간축 상의 범위를 구하는 방법을 제시 했다. 다음으로 프로세서간의 통신지연이 무시될 수 있는 경우, 주어진 반복주기 값에 대하여 구현에 필요한 프로세서의 수를 최소화하기 위한 스케줄 방법으로 0-1 정수 프로그래밍 방법과 휴리스틱(heuristic)에 의한 방법을 제시했다. 전자는 작은 크기의 문제에만 적용이 가능하나 필요한 최소의 프로세서 수를 구할 수 있다. 반면, 후자는 최적의 해를 항상 보장할 수 없으나 빠른 시간에 스케줄 결과를 제공할 수 있어 실용적으로 유용하다. 마지막으로 프로세서간의 통신지연이 무시될 수 없는 경우, 주어진 반복주기 값 및 주어진 프로세서 수를 사용하는 수행 가능한 스케줄을 구하는 방법을 제시하였다. 이것은 통신지연이 무시될 수 있는 경우에 적용했던 휴리스틱 방법을 확장한 것으로 task의 스케줄 시간 결정과 프로세서 할당을 동시에 수행한다. 또, 이 방법으로 얻어진 스케줄 결과를 공유버스를 갖는 시스템에 구현하는 방법을 보였다.