병렬 처리장치의 개수에 따른 스케줄링 알고리즘의 제안 및 성능평가 = Proposal and Performance Evaluation of A Scalable Scheduling Algorithm According to the Number of Parallel Processors

다국어 초록 (Multilingual Abstract)

The scheduling problem in parallel processing systems has been a challenging research issue for decades. The problem is defined as finding an optimal schedule which minimizes the parallel execution time of an application on a target multiprocessor system. Duplication Based Scheduling (DBS) is a relatively new approach for solving the problem, The DBS algorithms are capable of reducing communication overhead by duplicating remote parent tasks on local processors. Most of DBS algorithms assume an availability of the unlimited number of processors in the system. Since the assumption may not hold in practice, the paper proposes a new scalable DBS algorithm for a target system with limited number of processors. It is shown that the proposed algorithm with N available processors generates the same schedule as that obtained by the algorithm with unlimited number of processors, where N is the number of input tasks. Also, the performance evaluation reveals that the proposed algorithm shows a graceful performance degradation as the number of available processors in the system is decreased.