Skip to Main content Skip to Navigation

A realistic network/application model for scheduling divisible loads on large-scale platforms

Loris Marchal 1 Yang Yang 1 Henri Casanova 1 Yves Robert 1
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Divisible load applications consist of an amount of data and associated computation that can be divided arbitrarily into any number of independent pieces. This model is a good approximation of many real-world scientific applications, lends itself to a natural master-worker implementation, and has thus received a lot of attention. The critical issue of divisible load scheduling has been studied extensively in previous work. However, only a few authors have explored the simultaneous scheduling of multiple such applications on a distributed computing platform. We focus on this increasingly relevant scenario and make the following contributions. We use a novel and more realistic platform model that captures some of the fundamental network properties of Grid platforms. We formulate a steady-state multi-application scheduling problem as a linear program that expresses some notion of fairness between applications. This scheduling problem is NP-complete and we propose several heuristics that we evaluate and compare via extensive simulation experiments conducted over 250,000 platform configurations. Our main finding is that some of our heuristics can achieve performance close to the optimal and we quantify the trade-offs between achieved performance and heuristic complexity.
Document type :
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:39:56 PM
Last modification on : Thursday, November 21, 2019 - 2:31:56 AM


  • HAL Id : inria-00070795, version 1



Loris Marchal, Yang Yang, Henri Casanova, Yves Robert. A realistic network/application model for scheduling divisible loads on large-scale platforms. [Research Report] RR-5197, LIP RR-2004-21, INRIA, LIP. 2004, pp.22. ⟨inria-00070795⟩



Record views


Files downloads