Scheduling divisible workloads on heterogeneous platforms

✍ Scribed by Olivier Beaumont; Arnaud Legrand; Yves Robert

• Book ID: 104304265
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 384 KB
• Volume: 29
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(03)00095-4

✦ Synopsis

In this paper, we discuss several algorithms for scheduling divisible workloads on heterogeneous systems. Our main contributions are (i) new optimality results for single-round algorithms and (ii) the design of an asymptotically optimal multi-round algorithm. This multi-round algorithm automatically performs resource selection, a difficult task that was previously left to the user. Because it is periodic, it is simpler to implement, and more robust to changes in the speeds of the processors and/or communication links. On the theoretical side, to the best of our knowledge, this is the first published result assessing the absolute performance of a multi-round algorithm. On the practical side, extensive simulations reveal that our multi-round algorithm outperforms existing solutions on a large variety of platforms, especially when the communication-to-computation ratio is not very high (the difficult case).