Exploiting duplication to minimize the execution times of parallel programs on message-passing systems

Abstract

Communication overhead is one of the main factors that can limit the speedup of parallel programs on message-passing parallel architectures. This limiting factor is more predominant in distributed systems such as clusters of homogeneous or heterogeneous workstations. However, excessive communication overhead can be reduced by redundantly executing some of the tasks of a parallel program on which other tasks critically depend. In this paper, we study the problem of duplication-based static scheduling of parallel programs on parallel and distributed systems. Previous duplication-based scheduling algorithms assumed the availability of unlimited number of homogeneous processors. In this paper, we consider more practical scenarios: when the number of processors is limited, and when the system consists of heterogeneous computers. For the first scenario, we propose an algorithm which minimizes the execution of a parallel program by controlling the level of duplication according to the number of processors available. For the second scenario, we design an algorithm which simultaneously exploits duplication and processor heterogeneity to minimize the total execution time of a parallel program. The proposed algorithms are suitable for low as well as high communication-to-computation ratios.