Article

Free access

Toward a fully decentralized algorithm for multiple bag-of-tasks application scheduling on grids

Authors:

R. Bertin,

A. Legrand,

C. TouatiAuthors Info & Claims

GRID '08: Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing

Pages 118 - 125

https://doi.org/10.1109/GRID.2008.4662790

Published: 29 September 2008 Publication History

PDF eReader

Abstract

In this paper, we present a fully decentralized algorithm for fair resource sharing between multiple bag-of-tasks applications in a grid environment. This algorithm is inspired from related work on multi-path routing in communication network. An interesting feature of this algorithm is that it allows the choice of wide variety of fairness criteria and achieves both optimal path selection and flow control. In addition, this algorithm only requires local information at each slave computing tasks and at each buffer of the network links while minimal computation is done by the schedulers. A naive adaptation is unstable and inefficient though. Fortunately, a simple and effective scaling mechanism is sufficient to circumvent this issue. This scaling mechanism is motivated by a careful study of the subtle differences with the classical multi-path routing problem. We prove its efficiency through a detailed analysis of a simple simulation.

References

[1]

O. Beaumont, L. Carter, J. Ferrante, A. Legrand, L. Marchal, and Y. Robert. Centralized versus distributed schedulers multiple bag-of-tasks applications. IEEE Trans. Parallel Distributed Systems, 19(5):698-709, May 2008.

Digital Library

Google Scholar

[2]

O. Beaumont, A. Legrand, L. Marchal, and Y. Robert. Steady-state scheduling on heterogeneous clusters: Why and how? In 6th Workshop on Advances in Parallel and Distributed Computational Models APDCM 2004, page 171a (8 pages). IEEE Computer Society Press, 2004.

Google Scholar

[3]

E. Caron and F. Desprez. Diet: A scalable toolbox to build network enabled servers on the grid. International Journal of High Performance Computing Applications, 20(3):335-352, 2006.

Digital Library

Google Scholar

[4]

B. Hong and V. K. Prasanna. Adaptive allocation of independent tasks to maximize throughput. IEEE Trans. Parallel Distributed Systems, 18(10):1420-1435, Oct. 2007.

Digital Library

Google Scholar

[5]

F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237-252, 1998.

Crossref

Google Scholar

[6]

A. Legrand, M. Quinson, K. Fujiwara, and H. Casanova. The SimGrid project - simulation and deployment of distributed applications. In Proceedings of the IEEE International Symposium on High Performance Distributed Computing (HPDC-15), pages 385-386. IEEE Computer Society Press, 2006.

Crossref

Google Scholar

[7]

A. Legrand and C. Touati. Non-cooperative scheduling of multiple bag-of-task appplications. In Proceedings of the 25th Conference on Computer Communications (INFOCOM'07), Alaska, USA, May 2007.

Google Scholar

[8]

S. Low. A duality model of TCP and queue management algorithms. IEEE/ACM Transactions on Networking, 11(4):525-536, 2003.

Digital Library

Google Scholar

[9]

C. Touati, E. Altman, and J. Galtier. Generalized Nash bargaining solution for bandwidth allocation. Computer Networks, 50(17):3242-3263, Dec. 2006.

Digital Library

Google Scholar

[10]

C. Touati, E. Altman, and J. Galtier. Generalized Nash bargaining solution for bandwidth allocation. Computer Networks, 50(17):3242-3263, Dec. 2006.

Digital Library

Google Scholar

[11]

W.-H. Wang, M. Palaniswami, and S. Low. Optimal flow control and routing in multi-path networks. Performance Evaluation, 52:119-132, 2003.

Digital Library

Google Scholar

Cited By

View all

Bertin RHunold SLegrand ATouati C(2014)Fair scheduling of bag-of-tasks applications using distributed Lagrangian optimizationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.08.01174:1(1914-1929)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2013.08.011
Simon TNguyen PHalem MLiu FRupp KPhillips RThacker W(2013)Multiple objective scheduling of HPC workloads through dynamic prioritizationProceedings of the High Performance Computing Symposium10.5555/2499968.2499981(1-8)Online publication date: 7-Apr-2013
https://dl.acm.org/doi/10.5555/2499968.2499981
Casanova HGallet MVivien F(2010)Non-clairvoyant scheduling of multiple bag-of-tasks applicationsProceedings of the 16th international Euro-Par conference on Parallel processing: Part I10.5555/1887695.1887715(168-179)Online publication date: 31-Aug-2010
https://dl.acm.org/doi/10.5555/1887695.1887715
Show More Cited By

Index Terms

Toward a fully decentralized algorithm for multiple bag-of-tasks application scheduling on grids

Recommendations

Practical Scheduling of Bag-of-Tasks Applications on Grids with Dynamic Resilience

Over the past decade, the grid has emerged as an attractive platform to tackle various large-scale problems, especially in science and engineering. One primary issue associated with the efficient and effective utilization of heterogeneous resources in a ...
A Grid Scheduling Algorithm for Bag-of-Tasks Applications Using Multiple Queues with Duplication
ICIS-COMSAR '06: Proceedings of the 5th IEEE/ACIS International Conference on Computer and Information Science and 1st IEEE/ACIS International Workshop on Component-Based Software Engineering,Software Architecture and Reuse

Over the past decade the computational grid has emerged as an attractive platform to tackle various large-scale problems, especially in science and engineering. One primary issue associated with the efficient and effective utilization of heterogeneous ...
Scheduling in Bag-of-Task Grids: The PAUÁ Case
SBAC-PAD '04: Proceedings of the 16th Symposium on Computer Architecture and High Performance Computing

In this paper we discuss the difficulties involved in the scheduling of applications on computational grids. We highlight two main sources of difficulties: firstly, the size of the grid rules out the possibility of using a centralized scheduler; ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GRID '08: Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing

September 2008

416 pages

ISBN:9781424425785

Publisher

IEEE Computer Society

United States

Publication History

Published: 29 September 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
102
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bertin RHunold SLegrand ATouati C(2014)Fair scheduling of bag-of-tasks applications using distributed Lagrangian optimizationJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.08.01174:1(1914-1929)Online publication date: 1-Jan-2014
https://dl.acm.org/doi/10.1016/j.jpdc.2013.08.011
Simon TNguyen PHalem MLiu FRupp KPhillips RThacker W(2013)Multiple objective scheduling of HPC workloads through dynamic prioritizationProceedings of the High Performance Computing Symposium10.5555/2499968.2499981(1-8)Online publication date: 7-Apr-2013
https://dl.acm.org/doi/10.5555/2499968.2499981
Casanova HGallet MVivien F(2010)Non-clairvoyant scheduling of multiple bag-of-tasks applicationsProceedings of the 16th international Euro-Par conference on Parallel processing: Part I10.5555/1887695.1887715(168-179)Online publication date: 31-Aug-2010
https://dl.acm.org/doi/10.5555/1887695.1887715
Wu CSun R(2010)An integrated security-aware job scheduling strategy for large-scale computational gridsFuture Generation Computer Systems10.1016/j.future.2009.08.00426:2(198-206)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1016/j.future.2009.08.004
Coucheney PHyon ETouati CGaujal BStea GMairesse JMendes J(2009)Myopic versus clairvoyant admission policies in wireless networksProceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools10.4108/ICST.VALUETOOLS2009.7766(1-10)Online publication date: 20-Oct-2009
https://dl.acm.org/doi/10.4108/ICST.VALUETOOLS2009.7766

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Practical Scheduling of Bag-of-Tasks Applications on Grids with Dynamic Resilience

A Grid Scheduling Algorithm for Bag-of-Tasks Applications Using Multiple Queues with Duplication

Scheduling in Bag-of-Task Grids: The PAUÁ Case

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations