Gyung-Leen Park, Sang Joon Lee, BongKyu Lee, Journal of Internet Computing and Services, Vol. 1, No. 2, pp. 19-28, Dec. 2000
Full Text:  HTML

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 net 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.

Statistics
Cite this article