Dynamic, competitive scheduling of multiple DAGs in a distributed heterogeneous environment
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
With the advent of large scale heterogeneous environments, there is a need for matching and scheduling algorithms which can allow multiple DAG-structured applications to share the computational resources of the network. The paper presents a matching and scheduling framework where multiple applications compete for the computational resources on the network. In this environment, each application makes its own scheduling decisions. Thus, no centralized scheduling resource is required. Applications do not need direct knowledge of the other applications. The only knowledge of other applications arrives indirectly through load estimates (like queue lengths). The paper also presents algorithms for each portion of this scheduling framework. One of these algorithms is modification of a static scheduling algorithm, the DLS algorithm, first presented by Sih and Lee (1993). Other algorithms attempt to predict the future task arrivals by modeling the task arrivals as Poisson random processes. A series of simulations are presented to examine the performance of these algorithms in this environment. These simulations also compare the performance of this environment to a more conventional, single user environment.Keywords
This publication has 9 references indexed in Scilit:
- Load Distribution Optimization in Heterogeneous Multiple Processor SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Heterogeneous Supercomputing: Problems and IssuesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Dynamic optimization of load distribution in heterogeneous systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Designs and experiments on heterogeneous mapping heuristicsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- “Agency scheduling” A model for dynamic task schedulingPublished by Springer Nature ,1995
- Load sharing with consideration of future task arrivals in heterogeneous distributed real-time systemsIEEE Transactions on Computers, 1994
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- An analytical approach to performance/ cost modeling of parallel computersJournal of Parallel and Distributed Computing, 1991
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990