Published Articles >> Table of Contents >> Abstract

International Parallel and Distributed Processing Symposium (IPDPS'03)   p. 26a
Autonomous Protocols for Bandwidth-Centric Scheduling of Independent-Task Applications
Barbara Kreaseck, University of California at San Diego
Larry Carter, University of California at San Diego
Henri Casanova, University of California at San Diego
Jeanne Ferrante, University of California at San Diego

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213104
Send link to a friend

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 with interruptible 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.
Back to Top Additional Information
Citation:  Barbara Kreaseck, Larry Carter, Henri Casanova, Jeanne Ferrante, "Autonomous Protocols for Bandwidth-Centric Scheduling of Independent-Task Applications," ipdps, p. 26a,  International Parallel and Distributed Processing Symposium (IPDPS'03),  2003