research-article

Discovering performance bounds for grid scheduling by using evolutionary multiobjective optimization

Authors:

Christian Grimme,

Joachim Lepping,

Alexander PapaspyrouAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1491 - 1498

https://doi.org/10.1145/1389095.1389385

Published: 12 July 2008 Publication History

Abstract

In this paper, we introduce a methodology for the approximation of optimal solutions for a resource allocation problem in the domain of Grid scheduling on High Performance Computing systems. In detail, we review a real-world scenario with decentralized, equitable, and autonomously acting suppliers of compute power who wish to collaborate in the provision of their resources. We exemplarily apply NSGA-II in order to explore the bounds of maximum achievable benefit. To this end, appropriate encoding schemes and variation operators are developed while the performance is evaluated. The simulations are based upon recordings from real-world Massively Parallel Processing systems that span a period of eleven months and comprise approximately 100,000 jobs. By means of the obtained Pareto front we are able to identify bounds for the maximum benefit of Grid computing in a popular scenario. For the first time, this enables Grid scheduling researchers to rank their developed real-world strategies.

References

[1]

A. Abraham, R. Buyya, and B. Nath. Nature's heuristics for scheduling jobs in computational grids. In P. Sinha and R. Gupta, editors, Proceedings of 8th IEEE International Conference on Advanced Computing and Communications, pages 45--52, New Delhi, India, 2000. Tata McGraw-Hill Publishing.]]

[2]

P. Andreetto, S. Borgia, A. Dorigo, et al. Practical Approaches to Grid Workload and Resource Management in the EGEE Project. In Proceedings of the Conference on Computing in High Energy and Nuclear Physics (CHEP), Interlaken, Switzerland, September 2004. Organisation Européenne pour la Recherche Nucléaire (online).]]

[3]

D. Bernhold, S. Bharathi, D. Brown, K. Chanchio, et al. The Earth System Grid: Supporting the Next Generation of Climate Modeling Research. Proceedings of the IEEE, 93(3), March 2005.]]

[4]

J. Carretero, F. Xhafa, and A. Abraham. Genetic algorithm based schedulers for grid computing systems. International Journal of Innovative Computing, Information and Control, 3(6):1--19, 2007.]]

[5]

K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan. A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. In M. Schoenauer et al., editors, Parallel Problem Solving from Nature VI, volume 1917 of Lecture Notes in Computer Science (LNCS), pages 849--858. Springer, 2000.]]

Digital Library

[6]

D. England and J. B. Weissman. Cost and Benefits of Load Sharing in the Computational Grid. In D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn, editors, Proceedings of Job Scheduling Strategies for Parallel Processing, volume 3277 of Lecture Notes in Computer Science (LNCS), pages 160--175. Springer, 2004.]]

Digital Library

[7]

C. Ernemann, V. Hamscher, U. Schwiegelshohn, A. Streit, and R. Yahyapour. Enhanced Algorithms for Multi-Site Scheduling. In M. Parashar, editor, Proceedings of the 3rd International Workshop on Grid Computing, volume 2536 of Lecture Notes in Computer Science (LNCS), pages 219--231. Springer, 2002.]]

Digital Library

[8]

C. Ernemann, V. Hamscher, U. Schwiegelshohn, A. Streit, and R. Yahyapour. Enhanced Algorithms for Multi-Site Scheduling. In M. Parashar, editor, Proceedings of the 3rd International Workshop on Grid Computing, volume 2536 of Lecture Notes in Computer Science (LNCS), pages 219--231. Springer, 2002.]]

Digital Library

[9]

M. Ernst, P. Fuhrmann, A. Papaspyrou, M. Radicke, L. Schley, and R. Yahyapour. A Computational and Data Scheduling Architecture for HEP Applications. In Proceedings of the Conference on High Energy Physics (CHEP), Mumbai, India, February 2006.]]

[10]

D. W. Erwin and D. F. Snelling. UNICORE: A Grid Computing Environment. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Proceedings of the 7th International Euro-Par Conference, volume 2150 of Lecture Notes in Computer Science (LNCS), pages 825--834, Manchester, UK, August 2001. Springer.]]

Digital Library

[11]

D. G. Feitelson. Metrics for parallel job scheduling and their convergence. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, volume 2221 of Lecture Notes in Computer Science (LNCS), pages 188--206. Springer, 2001.]]

Digital Library

[12]

D. G. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel Job Scheduling -- A Status Report. In D. Feitelson, L. Rudolph, and U. Schwiegelshohn, editors, Proceedings of Job Scheduling Strategies for Parallel Processing, volume 3277 of Lecture Notes in Computer Science (LNCS), pages 1--16, Boston (MA), USA, June 2005. Springer.]]

Digital Library

[13]

I. Foster and C. Kesselman, editors. The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufman, 1st edition, 1998.]]

Digital Library

[14]

J. Garzon, E. Huedo, R. Montero, I. Llorente, and P. Chacon. Adaptation of a Multi-Resolution Docking Bioinformatics Application to the Grid. Journal of Software, 2:1--10, 2007.]]

[15]

C. Grimme, J. Lepping, and A. Papaspyrou. Prospects of Collaboration between Compute Providers by means of Job Interchange. In E. Frachtenberg and U. Schwiegelshohn, editors, Proceedings of Job Scheduling Strategies for Parallel Processing, volume 4942 of Lecture Notes in Computer Science (LNCS), pages 132--151. Springer, June 2007.]]

Digital Library

[16]

C. Grimme, J. Lepping, A. Papaspyrou, P. Wieder, R. Yahyapour, A. Oleksiak, O. Wäldrich, and W. Ziegler. Towards a standards-based Grid Scheduling Architecture. CoreGRID Technical Report TR-0123, Institute on Resource Management and Scheduling, December 2007.]]

[17]

V. Hamscher, U. Schwiegelshohn, A. Streit, and R. Yahyapour. Evaluation of Job-Scheduling Strategies for Grid Computing. In R. Buyya and M. Baker, editors, Proceedings of the 7th International Conference on High Performance Computing, volume 1971 of Lecture Notes in Computer Science (LNCS), pages 191--202. Springer, 2000.]]

Digital Library

[18]

W. Jakob, A. Quinte, K.-U. Stucky, and W. Süss. Optimised Scheduling of Grid Resources Using Hybrid Evolutionary Algorithms. In R. Wyrzykowski et al., editors, Proceedings of the 6th International Conference on Parallel Processing and Applied Mathematics, number 3911 in Lecture Notes in Computer Science (LNCS), pages 406--413, 2005.]]

Digital Library

[19]

K. Kurowski, J. Nabrzski, A. Oleksiak, and J. Weglarz. Scheduling Jobs on the Grid - Multicriteria Approach. Computational Methods in Science and Technology, 12(2):123--138, 2006.]]

[20]

D. A. Lifka. The ANL/IBM SP Scheduling System. In Proceedings of Job Scheduling Strategies for Parallel Processing, volume 949 of Lecture Notes in Computer Science (LNCS), pages 295--303. Springer, 1995.]]

Digital Library

[21]

U. Lublin and D. G. Feitelson. The Workload on Parallel Supercomputers: Modeling the Characteristics of Rigid Jobs. Journal of Parallel and Distributed Computing, 63(11):1105--1122, 2003.]]

Digital Library

[22]

Z. Michalewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer, 2 edition, November 1998.]]

Digital Library

[23]

M. Pinedo. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, New Jersey, second edition, 2002.]]

[24]

K. Sastry. Single and Multiobjective Genetic Algorithm Toolbox for Matlab in C++. Technical Report 2007017, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 117 Transportation Building, 104 S. Mathews Avenue Urbana, IL 61801, 2007.]]

[25]

U. Schwiegelshohn and R. Yahyapour. Fairness in Parallel Job Scheduling. Journal of Scheduling, 3(5):297--320, 2000.]]

Cited By

Singh M(2019)An Overview of Grid Computing2019 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS)10.1109/ICCCIS48478.2019.8974490(194-198)Online publication date: Oct-2019
https://doi.org/10.1109/ICCCIS48478.2019.8974490
Folling AGrimme CLepping JPapaspyrou A(2010)Robust Load Delegation in Service Grid EnvironmentsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.1621:9(1304-1316)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1109/TPDS.2010.16
Hirales-Carbajal ATchernykh ARoblitz TYahyapour R(2010)A Grid simulation framework to study advance scheduling strategies for complex workflow applications2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW)10.1109/IPDPSW.2010.5470918(1-8)Online publication date: Apr-2010
https://doi.org/10.1109/IPDPSW.2010.5470918
Show More Cited By

Index Terms

Discovering performance bounds for grid scheduling by using evolutionary multiobjective optimization

Recommendations

Meta-schedulers for grid computing based on multi-objective swarm algorithms

Job scheduling is a challenging task on grid environments because they must fulfill user requirements. Scientists often have deadlines and budgets for their experiments (set of jobs). But these requirements are in conflict with each other - cheaper ...
Computational models and heuristic methods for Grid scheduling problems

In this paper we survey computational models for Grid scheduling problems and their resolution using heuristic and meta-heuristic approaches. Scheduling problems are at the heart of any Grid-like computational system. Different types of scheduling based ...
A novel multi-objective optimization scheme for grid resource allocation
MGC '08: Proceedings of the 6th international workshop on Middleware for grid computing

Grid computing emerges as an infrastructure for large-scale data processing, resource sharing, and scientific computing. Job scheduling at the Grid level is challenging in that Grid schedulers do not have control over the computing resources across ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
279
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Singh M(2019)An Overview of Grid Computing2019 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS)10.1109/ICCCIS48478.2019.8974490(194-198)Online publication date: Oct-2019
https://doi.org/10.1109/ICCCIS48478.2019.8974490
Folling AGrimme CLepping JPapaspyrou A(2010)Robust Load Delegation in Service Grid EnvironmentsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2010.1621:9(1304-1316)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1109/TPDS.2010.16
Hirales-Carbajal ATchernykh ARoblitz TYahyapour R(2010)A Grid simulation framework to study advance scheduling strategies for complex workflow applications2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW)10.1109/IPDPSW.2010.5470918(1-8)Online publication date: Apr-2010
https://doi.org/10.1109/IPDPSW.2010.5470918
Fölling AGrimme CLepping JPapaspyrou ASchwiegelshohn U(2009)Competitive coevolutionary learning of fuzzy systems for job exchange in computational gridsEvolutionary Computation10.1162/evco.2009.17.4.1740617:4(545-560)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1162/evco.2009.17.4.17406
Niyato DChaisiri SSung L(2009)Optimal Power Management for Server Farm to Support Green ComputingProceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid10.1109/CCGRID.2009.89(84-91)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.1109/CCGRID.2009.89
Fölling AGrimme CLepping JPapaspyrou A(2009)Decentralized Grid Scheduling with Evolutionary Fuzzy SystemsJob Scheduling Strategies for Parallel Processing10.1007/978-3-642-04633-9_2(16-36)Online publication date: 13-Oct-2009
https://dl.acm.org/doi/10.1007/978-3-642-04633-9_2

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten