This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Marchal, L. Articles by Robert, Y. Search for Related Content Social Bookmarking                         What's this?

Steady-State Scheduling of Multiple Divisible Load Applications on Wide-Area Distributed Computing Platforms

LABORATOIRE LIP, CNRS-INRIA, ÉCOLE NORMALE SUPÉRIEURE DE LYON, FRANCE

Y. Yang

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, UNIVERSITY OF CALIFORNIA, SAN DIEGO, USA

H. Casanova

INFORMATION AND COMPUTER SCIENCES DEPARTMENT UNIVERSITY OF HAWAII AT MANOA, USA; LABORATOIRE LIP, CNRS-INRIA, ÉCOLE NORMALE SUPÉRIEURE DE LYON, FRANCE

Y. Robert

LABORATOIRE LIP, CNRS-INRIA, ÉCOLE NORMALE SUPÉRIEURE DE LYON, FRANCE

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 the steady-state multi-application scheduling problem as a linear program that expresses a 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. 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.

Key Words: parallel computing • scheduling • divisible load • multiple applications • resource sharing

International Journal of High Performance Computing Applications, Vol. 20, No. 3, 365-381 (2006)
DOI: 10.1177/1094342006067474


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?