Concurrency and Computation: Practice and Experience

Volume 20, Issue 9 pp. 1029-1049

Research Article

A performance-oriented adaptive scheduler for dependent tasks on grids^†

Luiz F. Bittencourt,

Corresponding Author

Luiz F. Bittencourt

[email protected]

Institute of Computing, State University of Campinas, Campinas, São Paulo, Brazil

Institute of Computing, UNICAMP, P.O. 6176, Campinas, São Paulo, BrazilSearch for more papers by this author

Edmundo R. M. Madeira,

Edmundo R. M. Madeira

Institute of Computing, State University of Campinas, Campinas, São Paulo, Brazil

Search for more papers by this author

Luiz F. Bittencourt,

Corresponding Author

Luiz F. Bittencourt

[email protected]

Institute of Computing, State University of Campinas, Campinas, São Paulo, Brazil

Institute of Computing, UNICAMP, P.O. 6176, Campinas, São Paulo, BrazilSearch for more papers by this author

Edmundo R. M. Madeira,

Edmundo R. M. Madeira

Institute of Computing, State University of Campinas, Campinas, São Paulo, Brazil

Search for more papers by this author

First published: 22 November 2007

https://doi.org/10.1002/cpe.1282

Citations: 56

^†

This is an extended version of the paper ‘A dynamic approach for scheduling dependent tasks on the Xavantes grid middleware,’ presented at the 4th International Workshop on Middleware for Grid Computing (MGC'06).

Share a link

Email
Wechat
Bluesky

Abstract

A scheduler must consider the heterogeneity and communication delays when scheduling dependent tasks on a grid. The task-scheduling problem is NP-Complete in general, which led us to the development of a heuristic for the associated optimization problem. In this work we present a dynamic adaptive approach to schedule dependent tasks onto a grid based on the Xavantes grid middleware. The developed dynamic approach is applied to the Path Clustering Heuristic, and introduces the concept of rounds, which take turns sending tasks to execution and evaluating the performance of the resources. The adaptive extension changes the size of rounds during the process execution, taking task attributes and resources performance as parameters, and it can be adopted in other task schedulers. The experiments show that the dynamic round-based and adaptive schedule can minimize the effects of performance losses while executing processes on the grid. Copyright © 2007 John Wiley & Sons, Ltd.

REFERENCES

1 Bittencourt LF, Madeira ERM, Cicerre FRL, Buzato LE. A path clustering heuristic for scheduling task graphs onto a grid (short paper). Proceedings of the 3rd ACM International Workshop on Middleware for Grid Computing, Grenoble, France, 2005.
Google Scholar
2 Cicerre FRL, Madeira ERM, Buzato LE. A hierarchical process execution support for grid computing. Concurrency and Computation: Practice and Experience 2006; 18(6): 581–594.
10.1002/cpe.967
Web of Science® Google Scholar
3 Kwok Y-K, Ahmad I. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems 1996; 7(5): 506–521.
10.1109/71.503776
Web of Science® Google Scholar
4 Yang T, Gerasoulis A. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Transactions on Parallel and Distributed Systems 1994; 5(9): 951–967.
10.1109/71.308533
Web of Science® Google Scholar
5 Bajaj R, Agrawal DP. Improving scheduling of tasks in a heterogeneous environment. IEEE Transactions on Parallel and Distributed Systems 2004; 15(2): 107–118.
10.1109/TPDS.2004.1264795
Web of Science® Google Scholar
6 Sakellariou R, Zhao H. A hybrid heuristic for DAG scheduling on heterogeneous systems. Proceedings of the 13th Heterogeneous Computing Workshop. IEEE Computer Society Press: Los Alamitos, CA, 2004; 111–124.
10.1109/IPDPS.2004.1303065
Google Scholar
7 Topcuoglu H, Hariri S, Wu M-Y. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems 2002; 13(3): 260–274.
10.1109/71.993206
Web of Science® Google Scholar
8 Hagras T, Janeček J. An approach to compile-time task scheduling in heterogeneous computing systems. Proceedings of the 33rd International Conference on Parallel Processing Workshops. IEEE Computer Society Press: Los Alamitos, CA, 2004; 182–189.
10.1109/ICPPW.2004.1328016
Web of Science® Google Scholar
9 Frey J. Condor DAGMan: Handling inter-job dependencies. http://www.cs.wisc.edu/condor/dagman/ [25 July 2006].
Google Scholar
10 Prodan R, Fahringer T. Dynamic scheduling of scientific workflow applications on the grid: A case study. Proceedings of the 2005 ACM Symposium on Applied computing (SAC'05). ACM Press: New York, 2005; 687–694.
10.1145/1066677.1066835
Google Scholar
11 Chen H, Maheswaran M. Distributed dynamic scheduling of composite tasks on grid computing systems. Proceedings of the 11th IEEE Heterogeneous Computing Workshop, Fort Lauderdale, U.S.A., 2002.
Google Scholar
12 Cooper K, Dasgupta A, Kennedy K, Koelbel C, Mandal A, Marin G, Mazina M, Mellor-Crummey J, Berman F, Casanova H, Chien A, Dail H, Liu X, Olugbile A, Sievert O, Xia H, Johnsson L, Liu B, Patel M, Reed D, Deng W, Mendes C, Shi Z, YarKhan A, Dongarra J. New grid scheduling and rescheduling methods in the GrADS project. Proceedings of the IPDPS Next Generation Software Program—NSFNGS—PI Workshop. IEEE Computer Society Press: Los Alamitos, CA, 2004; 199–206.
10.1109/IPDPS.2004.1303222
Google Scholar
13 Fujimoto N, Hagihra K. Near-optimal dynamic task scheduling of precedence constrained coarse-grained tasks onto a computational grid. Second International Symposium on Parallel and Distributed Computing. Ljubljana, Slovenia, 2003; 80–87.
Google Scholar
14 Wolski R, Spring NT, Hayes J. The network weather service: A distributed resource performance forecasting service for metacomputing. Future Generation Computer Systems 1999; 15(5–6): 757–768.
10.1016/S0167-739X(99)00025-4
Web of Science® Google Scholar

Citing Literature

Volume20, Issue9

Special Issue:Middleware for Grid Computing: Future Trends (MGC2006)

25 June 2008

Pages 1029-1049

A performance-oriented adaptive scheduler for dependent tasks on grids^†

Abstract

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

A performance-oriented adaptive scheduler for dependent tasks on grids†

Abstract

REFERENCES

Citing Literature

References

Related

Information

A performance-oriented adaptive scheduler for dependent tasks on grids^†