A Multi-Round Algorithm for Scheduling Divisible Workload Applications: Analysis and Experimental Evaluation

In this paper we present UMR, an algorithm for scheduling parallel applications that consist of a divisible workload. Our algorithm uses multiple rounds to overlap communication and computation between a master and a number of workers. Multi-round scheduling has been used for divisible workloads in previous work and our contributions in this paper are as follows. UMR uses ``uniform'' rounds, i.e. a fixed amount of work is sent out to all workers at each round. This restriction makes it possible to compute an approximatively optimal number of rounds, which was not possible for previously proposed algorithms. In addition, we use more realistic platform models than those used in previous works. We provide an analysis of our algorithm both for homogeneous and heterogeneous platforms and present simulation results to quantify the benefits of our approach.Pre-2018 CSE ID: CS2002-072