Department of Computer Science & Engineering

Divisible workload applications occur in many fields of science and engineering. Although these application can be easily parallelized in a master-worker fashion, they pose several scheduling challenges. Previously proposed scheduling algorithms either distribute work to processors in a single round of work allocation or in multiple rounds. Multi-round algorithms can achieve better overlap of computation and communication but are more difficult to analyze. Consequently, a number of open questions still remain for multi-round scheduling. In this paper we improve on the seminal "multi-installment" algorithm proposed by Bharadwaj. et al. for homogeneous star networks. Their work suffers from two important limitations: (i) communication and computation latencies are assumed to be negligible; and (ii) size of application output data is assumed to be negligible. These two limitations strongly restrict the applicability of multi-installment to real-world platforms and applications. In this paper we remove both limitations.

Pre-2018 CSE ID: CS2003-0754