Parallel processing has been researched by many computer scientists to provide faster execution environments for applications, and various kinds of parallel computers were developed with a great deal of technological and theoretical efforts. However, when we try to run an application on a parallel system, the overall performance is determined not only by the capacity of the parallel system but also the load balancing of program tasks. To task advantage of the inherent parallelism of these architectures, efficient allocation and scheduling methods have to be developed.
This thesis concerned allocating and scheduling program tasks on parallel systems. The tasks are the consumers, and they are represented through the use of directed graphs called data flow graphs. The processing elements are resources, and their interconnection networks can be represented through the use of undirected graphs. First, we modeled parallel programs, parallel systems, and communication cost. Then we developed algorithms that allocate and scheduling tasks to maximize a performance for a given program tasks and a target machine. In this thesis, we introduced four algorithms: (1) Optimal scheduling algorithm for cyclic synchronous tasks in fully-connected multiprocessors (2) Optimal task scheduling algorithm for cyclic synchronous tasks in general multiprocessor networks (3) Optimal algorithm for minimizing the computing period of control tasks in multiprocessors (4) Polynomial algorithm for minimizing the computing period of control tasks in multiprocessors.
We verified that our optimal scheduling algorithms provide the optimal solutions and shows that the processing time is reasonable for normal-size applications. To handle huge scheduling problems, we developed a heuristic polynomial-complexity algorithm, which divides the task allocation and scheduling process into four stages.
These algorithms can be applied directly to task schedulers in operating systems or compilers supporting multiple processors. Especially, embedded parallel computers and multi-DSP systems for complex control tasks and numerical simulation are appropriate since the algorithm provides optimized schedules for the fastest iterative execution.
병렬처리는 응용 프로그램의 고속 수행을 위해 연구되어 왔고, 이론적 기술적 연구를 통해 여러 종류의 병렬 컴퓨터가 개발되었다. 그러나, 이러한 병렬 시스템에서 응용 프로그램을 수행하고자 할 때 전체적인 성능은 시스템 자체의 계산능력 뿐 아니라 작업량의 적절한 분배에 의해서도 결정된다. 병렬구조의 이점을 충분히 발휘하기 위해서는 효과적인 작업 할당 및 스케줄링 방법이 개발되어야 한다.
이 학위논문은 병렬 시스템에서의 작업 할당과 스케줄링에 대한 연구를 다루고 있다. 작업들은 컴퓨팅 리소스의 소비자로서 data flow graph로 표현된다. 반면, 병렬 프로세서들은 리소스의 공급자로서 프로세서 노드의 network 형태로 표현된다. 먼저, 우리는 응용 프로그램, 병렬 시스템, 그리고 통신 비용을 모델링 하였다. 그런 다음, 수행성능을 최대화 시키는 작업 할당 및 스케줄링 알고리즘을 개발하였다. 이 학위 논문에서는 다음과 같은 네 개의 세부 주제를 다루고 있다. (1) Full connection 구조에서 cyclic synchronous task의 최적 할당 알고리즘 (2) 다양한 구조에서 cyclic synchronous task의 최적 할당 알고리즘 (3) 제어 작업의 연산주기를 최소화 시키는 최적 알고리즘 (4) 제어 작업의 연산주기를 최소화 시키는 경험적 알고리즘.
최적 알고리즘이 최적해를 제공함을 증명하였고 일반적인 크기의 작업 수에 대하여 타당한 시간 안에 결과를 제공함을 보였다. 매우 많은 수의 작업에 대한 문제를 풀기 위하여 근사 최적해를 제공하는 알고리즘을 제안하였고 이 알고리즘이 다항 함수 형태의 복잡도를 가진다는 것을 증명하였다.
위의 알고리즘들은 operating system이나 compiler의 작업 스케줄러에 직접 적용될 수 있다. 특히, 이 알고리즘들은 반복적 연산에 대해 최적의 스케줄링을 제공하기 때문에, 제어작업, 신호처리, 그리고 시뮬레이션을 위한 임베디드 병렬 컴퓨터나 다중 DSP 시스템에 적합하다.
