A Comparison of Task-Duplication-Based Algorithms for Scheduling Parallel Programs to Message-Passing Systems
Iftikhar Ahmad, YK Kwok · 1997
A major hurdle in achieving high performance in message-passing architectures is the inevitable communication overhead that occurs when tasks scheduled on different processors need to exchange data. This overhead can cause a stern penalty especially in distributed systems such as clusters of workstations, where the network channels are considerably slower than the processors. For a given parallel program represented by a task graph, the communication overhead can be mitigated by redundantly executing some tasks on which other tasks critically depend. There have been a few taskduplication based scheduling algorithms that are designed for such environments. Although these algorithms are independently shown to be effective, no attempt has been made to quantitatively compare their performance under a broad range of input parameters. In this paper we analyze the problem of using task-duplication in compile-time scheduling of task graphs on parallel and distributed systems. We discuss the ch...