Autonomous protocols for bandwidth-centric scheduling of independent-task applications
- 22 March 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper we investigate protocols for scheduling applications that consist of large numbers of identical, independent tasks on large-scale computing platforms. By imposing a tree structure on an overlay network of computing nodes, our previous work showed that it is possible to compute the schedule which leads to the optimal steady-state task completion rate. However, implementing this optimal schedule in practice, without prohibitive global coordination of all the computing nodes or unlimited buffers, remained an open question. To address this question, in this paper we develop autonomous scheduling protocols, i.e. distributed scheduling algorithms by which each node makes scheduling decisions based solely on locally available information. Our protocols have two variants: with non-interruptible and with interruptible communications. Further, we evaluate both protocols using simulations on randomly generated trees. We show that the non-interruptible communication version may need a prohibitive number of buffers at each node. However, our autonomous protocol withinterruptible communication and only 3 buffers per node reaches the optimal steady-state performance in over 99.5% of our simulations. The autonomous scheduling approach is inherently scalable and adaptable, and thus ideally suited to currently emerging computing platforms. In particular this work has direct impact on the deployment of large applications on Grid, and peer-to-peer computing platforms.Keywords
This publication has 21 references indexed in Scilit:
- UMR: a multi-round algorithm for scheduling divisible workloadsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- ChordPublished by Association for Computing Machinery (ACM) ,2001
- The Anatomy of the Grid: Enabling Scalable Virtual OrganizationsThe International Journal of High Performance Computing Applications, 2001
- Sharing partitionable workloads in heterogeneous NOWs: greedier is not betterPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- The AppLeS Parameter Sweep Template: User-Level Middleware for the GridScientific Programming, 2000
- Monte Carlo Simulation of Neuro- Transmitter Release Using MCell, a General Simulator of Cellular Physiological ProcessesPublished by Springer Nature ,1998
- Allocating Independent Tasks to Parallel Processors: An Experimental StudyJournal of Parallel and Distributed Computing, 1997
- Load-sharing in heterogeneous systems via weighted factoringPublished by Association for Computing Machinery (ACM) ,1996
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical ProcessorsJournal of the ACM, 1977