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

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.Le modèle des tâches divisibles s’applique aux applications dont les données(et les calculs associés) ont une granularité arbitraire. Ce modèle a fait l’objet de nombreuses études, car son champ d’application est vaste, et sa mise en œuvre facile, via un paradigme maître-esclave classique. Nous étudions ici le déploiement simultané de plusieurs applications divisibles. Nous introduisons un modèle de plate-forme bien plus réaliste que les modèles précédents, et plus proche des caractéristiques des architectures distribuées à grande échelle. Nous cherchons à optimiser le régime permanent, avec un objectif qui prend en compte un accès équitable aux ressources pour les différentes applications. Ce problème d’ordonnancement est NP-complet, aussi nous proposons plusieurs heuristiques. Nous évaluons et comparons celles-ci `a travers une large gamme de simulations expérimentales conduites sur plus de 250 000 configurations. Certaines heuristiques sont très proches de l’optimal, et nous quantifions les compromis nécessaires entre performance et temps de calcu