DocumentCode :
780264
Title :
On the distribution of sequential jobs in random brokering for heterogeneous computational grids
Author :
Berten, Vandy ; Goossens, Joël ; Jeannot, Emmanuel
Author_Institution :
Departement d´´Informatique, Univ. Libre de Bruxelles, Brussels, Belgium
Volume :
17
Issue :
2
fYear :
2006
Firstpage :
113
Lastpage :
124
Abstract :
Scheduling stochastic workloads is a difficult task. In order to design efficient scheduling algorithms for such workloads, it is required to have a good in-depth knowledge of basic random scheduling strategies. This paper analyzes the distribution of sequential jobs and the system behavior in heterogeneous computational grid environments where the brokering is done in such a way that each computing element has a probability to be chosen proportional to its number of CPUs and (new from the previous paper) its relative speed. We provide the asymptotic behavior for several metrics (queue-sizes, slowdowns, etc.) or, in some cases, an approximation of this behavior. We study these metrics for a variety of workload configurations (load, distribution, etc.). We compare our probabilistic analysis to simulations in order to validate our results. These results provide a good understanding of the system behavior for each metric proposed. This enables us to design advanced and efficient algorithms for more complex cases.
Keywords :
grid computing; probability; processor scheduling; resource allocation; stochastic processes; heterogeneous computational grid; probabilistic analysis; random brokering; sequential job distribution; stochastic workload scheduling; Algorithm design and analysis; Analytical models; Computer architecture; Distributed computing; Grid computing; Middleware; Processor scheduling; Random variables; Scheduling algorithm; Stochastic processes; Grid brokering; heterogeneous and distributed architecture.; multilevel scheduling; random brokering; stochastic workload;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2006.27
Filename :
1566590
Link To Document :
بازگشت