Steady-State Scheduling of Multiple Divisible Load Applications on Wide-Area Distributed Computing Platforms
Open Access
- 1 August 2006
- journal article
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 20 (3), 365-381
- https://doi.org/10.1177/1094342006067474
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 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.Keywords
This publication has 19 references indexed in Scilit:
- Scheduling strategies for master-slave tasking on heterogeneous processor platformsIEEE Transactions on Parallel and Distributed Systems, 2004
- Research feature - Ten reasons to use divisible load theoryComputer, 2003
- Parameter Sweeps on the Grid with APSTPublished by Wiley ,2003
- Optimizing execution of component-based applications using group instancesFuture Generation Computer Systems, 2002
- The Anatomy of the Grid: Enabling Scalable Virtual OrganizationsThe International Journal of High Performance Computing Applications, 2001
- Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet RoutingJournal of Algorithms, 1999
- The network weather service: a distributed resource performance forecasting service for metacomputingFuture Generation Computer Systems, 1999
- Collection-aware optimum sequencing of operations and closed-form solutions for the distribution of a divisible load on arbitrary processor treesIEEE Transactions on Parallel and Distributed Systems, 1998
- Closed form solutions for bus and tree networks of processors load sharing a divisible jobIEEE Transactions on Computers, 1994
- Processor equivalence for daisy chain load sharing processorsIEEE Transactions on Aerospace and Electronic Systems, 1993