Scheduling Jobs on the Grid – Multicriteria Approach
Kurowski Krzysztof 1*, Nabrzyski Jarosław 1*, Oleksiak Ariel 1*, Węglarz Jan 1,2**
1Poznan Supercomputing and Networking Center
2Institute of Computing Science, Poznan University of Technology
e-mail: {krzysztof.kurowski/naber/ariel}@man.poznan.pl*, Jan.Weglarz@cs.put.poznan.pl**
Received:
Rec. 28 August 2006
DOI: 10.12921/cmst.2006.12.02.123-138
OAI: oai:lib.psnc.pl:620
Abstract:
In the paper we present two different models of Grid resource management problems: (i) Grid scheduling problems with no time characteristics available, and (ii) scheduling of jobs in presence of time characteristics achieved by using some prediction techniques, and resource reservation mechanisms. We focus on demonstrating how these two scenarios, which are important examples of Grid environments, can be modeled as multi-criteria decision support problems. We also discuss advantages and disadvantages of these models as well as practical applications.
Key words:
grid computing, Grid resource management and scheduling, multicriteria decision support
References:
[1] http://www.coregrid.net/
[2] J. Blazewicz, K. H. Ecker, G. Schmidt and J. Węglarz, Scheduling in computer and Manufactoring Systems, Springer-Verlag (Second Edition) 9, 265-297 (1994).
[3] J. R. Boisseau, UT Grid: A Comprehensive Campus Cyberinfrastructure, hpdc, pp. 274-275, 13th IEEE International Symposium on High Performance Distributed Computing (HPDC-13 ’04) 2004.
[4] Community scheduler framework (CSF) http://www.globus.org/toolkit/docs/4.0/contributions/csf.
[5] K. Czajkowski, I. Foster, N. Karonis, C. Kesselman, S. Martin, W. Smith and S. Tuecke, A resource management architecture for metacomputing systems, In: D. Feitelson and L. Rudolph (eds.) Job Scheduling Strategies for Parallel Processing (Proceedings of the Fourth International JSSPP Workshop; LNCS #1459), pp. 62-68, Springer-Verlag (1998).
[6] K. Czajkowski, I. Foster, C. Kesselman, V. Sander and S. Tuecke, SNAP: A protocol for negotiating service level agreements and coordinating resource management in distributed systems, In: D. Feitelson and L. Rudolph (eds.), Job Scheduling Strategies for Parallel Processing (Proceedings of the Eighth International JSSPP Workshop; LNCS#2357), Springer-Verlag, pp. 153-183 (2002).
[7] P. Dinda, Online prediction of the running time of tasks, In: Proc. 10th IEEE Symp. on High Performance Distributed Computing (2001).
[8] P. Domagalski, K. Kurowski, A. Oleksiak, J. Nabrzyski, Z. Balaton, G. Gombás and P. Kacsuk, Sensor Oriented Grid Monitoring Infrastructures for Adaptive Multi-Criteria Resource Management Strategies, In: Proceedings of the 1st CoreGrid Workshop 2005, Pisa, Italy (2005).
[9] P. F. Dutot, L. Eyraud, G. Mounié and D. Trystram, Bicriteria algorithm for scheduling jobs on cluster platforms, In: Symposium on Parallel Algorithm and Architectures, Barcelona, pp. 125–132 (2004).
[10] Enabling grids for e-science. http://public.eu-egee.org
[11] P. C. Fishburn, Utility Theory for Decision Making, Wiley, New York (1970).
[12] I. Foster and C. Kesselman, Computational Grids, In: I. Foster and C. Kesselman (eds.) The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Francisco, California, pp. 15-52. (1999).
[13] I. Foster, C. Kesselman and S. Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, 15(3), 200-222 (2001).
[14] Global Grid Forum (GGF), http://www.ggf.org
[15] Grid Resource Allocation Agreement Protocol Working Group (GRAAP-WG), http://forge.gridforum.org/projects/graap-wg
[16] S. Greco, B. Matarazzo, R. Słowinski and A. Tsoukias, Exploitation of a rough approximation of the outranking relation in multicriteria choice and ranking, In: T. Stewart
(ed): Multiple Criteria Decision Making. Proceedings of the Thirteenth International Conference, Cape Town (South Africa), January 1997; Springer- Verlag, Berlin (1988).
[17] E. Huedo, R. S. Montero and I. M. Llorente, A Framework for Adaptive Execution on Grids, Journal of Software – Practice and Experience, 34, 631-651 (2004).
[18] E. Jacquet-Lagr‘eze and Y. Siskos, Assessing a set of additive utility functions for multicriteria decision-making, the UTA method, European Journal of Operational Research 10,
151-164 (1982).
[19] Job Submission Description Language (JSDL) Specification, http://forge.gridforum.org/projects/jsdl-wg
[20] K. Kurowski, J. Nabrzyski, A. Oleksiak and J. Węglarz, Multicriteria Aspects of Grid Resource Management, In: Grid Resource Management, J. Nabrzyski, J. Schopf and J. Węglarz (eds.), Kluwer Academic Publishers, Boston/Dordrecht/London (2003).
[21] Kurowski K., Nabrzyski J., Oleksiak, J. Pukacki et al., Programming Grid Applications with Gridge, In: Computational Methods for Science and Technology, by J. Nabrzyski, M. Stroinski, (eds.): Grid Applications – New Challenges for Computational Methods, OWN 2006.
[22] K. Kurowski, A. Oleksiak, J. Nabrzyski, A. Kwiecień, M. Wojtkiewicz, M. Dyczkowski, F. Guim, J. Corbalan and J. Labarta, Multi-criteria Grid Resource Management using Performance Prediction Techniques, In: Proceeding of the CoreGrid Integration Workshop, Pisa (2005).
[23] Oh-Kyoung Kwon, Jaegyoon Hahm, Sangwan Kim and Jongsuk Lee, A Grid Resource Allocation System for Scientific Application: Grid Resource Allocation Services Package
(GRASP), Mardi Gras Conference (2005).
[24] M. Litzkow and M. Livny, Experiences with the Condor distributed batch system, In: Proceedings of the IEEE Workshop on Experimental Distributed Systems (1990).
[25] C. Liu, L. Yang, I. Foster and D. Angulo, Design and evaluation of a resource selection framework for Grid applications, In: Proceedings of the Eleventh IEEE International
Symposium on High-Performance Distributed Computing (HPDC-11) (2002).
[26] E. Medernach, Workload analysis of a cluster in a grid environment. In: D. G. Feitelson, E. Frachtenberg, L. Rudolph and U. Schwiegelshohn (eds.), Job Scheduling Strategiesfor Parallel Processing, pp. 36-61. Springer Verlag, 2005.
[27] J. Nabrzyski., J. Schopf and J. Węglarz (eds.), Grid Resource Management – State of the Art and Future Trends, Kluwer Academic Publishers (2003).
[28] B. Roy, Multicriteria Methodology for Decision Aiding, Kluwer, Dordrecht (1996).
[29] J. Schopf and F. Berman, Performance prediction in production environments. In: Proceedings of IPPS/SPDP (1998).
[30] B. A. Shirazi, A. R. Husson and K. M. Kavi, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press (1995).
[31] R. Słowinski, S. Greco and B. Matarazzo, Axiomatization of utility, outranking and decision – rule preference models for multiple-criteria classification problems under partial
incosistency with the dominance principle. Control and Cybernetics, 31(4) (2002).
[32] R. Slowinski, Rough set theory for multicriteria decision analysis, European Journal of Operational Research 129, 1-47 (2001).
[33] W. Smith, V. Taylor and I. Foster, Predicting Application Run-times Using Historical Information, In: Proceedings IPPS/SPDP ’98 Workshop on Job Scheduling Strategies for
Parallel Processing (1988).
[34] W. Smith, I. Foster and V. Taylor, Scheduling with Advanced Reservations, Proceedings of the 2000 International Parallel and Distributed Processing Symposium. May (2000).
[35] W. Smith, V. Taylor and I. Foster, Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance, In: Proceedings of the IPPS/SPDP ’99 Workshop on Job Scheduling Strategies for Parallel Processing (1999).
[36] R. Wolski, N. Spring and J. Hayes, Predicting the CPU availability of time-shared unix systems, In:submitted to SIGMETRICS ’99 (also available as UCSD Technical Report Number CS98-602) (1998).
[37] R. Wolski, N. Spring and J. Hayes, The network weather service: A distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, 15(5-6), 757-768 (1999).
In the paper we present two different models of Grid resource management problems: (i) Grid scheduling problems with no time characteristics available, and (ii) scheduling of jobs in presence of time characteristics achieved by using some prediction techniques, and resource reservation mechanisms. We focus on demonstrating how these two scenarios, which are important examples of Grid environments, can be modeled as multi-criteria decision support problems. We also discuss advantages and disadvantages of these models as well as practical applications.
Key words:
grid computing, Grid resource management and scheduling, multicriteria decision support
References:
[1] http://www.coregrid.net/
[2] J. Blazewicz, K. H. Ecker, G. Schmidt and J. Węglarz, Scheduling in computer and Manufactoring Systems, Springer-Verlag (Second Edition) 9, 265-297 (1994).
[3] J. R. Boisseau, UT Grid: A Comprehensive Campus Cyberinfrastructure, hpdc, pp. 274-275, 13th IEEE International Symposium on High Performance Distributed Computing (HPDC-13 ’04) 2004.
[4] Community scheduler framework (CSF) http://www.globus.org/toolkit/docs/4.0/contributions/csf.
[5] K. Czajkowski, I. Foster, N. Karonis, C. Kesselman, S. Martin, W. Smith and S. Tuecke, A resource management architecture for metacomputing systems, In: D. Feitelson and L. Rudolph (eds.) Job Scheduling Strategies for Parallel Processing (Proceedings of the Fourth International JSSPP Workshop; LNCS #1459), pp. 62-68, Springer-Verlag (1998).
[6] K. Czajkowski, I. Foster, C. Kesselman, V. Sander and S. Tuecke, SNAP: A protocol for negotiating service level agreements and coordinating resource management in distributed systems, In: D. Feitelson and L. Rudolph (eds.), Job Scheduling Strategies for Parallel Processing (Proceedings of the Eighth International JSSPP Workshop; LNCS#2357), Springer-Verlag, pp. 153-183 (2002).
[7] P. Dinda, Online prediction of the running time of tasks, In: Proc. 10th IEEE Symp. on High Performance Distributed Computing (2001).
[8] P. Domagalski, K. Kurowski, A. Oleksiak, J. Nabrzyski, Z. Balaton, G. Gombás and P. Kacsuk, Sensor Oriented Grid Monitoring Infrastructures for Adaptive Multi-Criteria Resource Management Strategies, In: Proceedings of the 1st CoreGrid Workshop 2005, Pisa, Italy (2005).
[9] P. F. Dutot, L. Eyraud, G. Mounié and D. Trystram, Bicriteria algorithm for scheduling jobs on cluster platforms, In: Symposium on Parallel Algorithm and Architectures, Barcelona, pp. 125–132 (2004).
[10] Enabling grids for e-science. http://public.eu-egee.org
[11] P. C. Fishburn, Utility Theory for Decision Making, Wiley, New York (1970).
[12] I. Foster and C. Kesselman, Computational Grids, In: I. Foster and C. Kesselman (eds.) The Grid: Blueprint for a New Computing Infrastructure, Morgan Kaufmann, San Francisco, California, pp. 15-52. (1999).
[13] I. Foster, C. Kesselman and S. Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, 15(3), 200-222 (2001).
[14] Global Grid Forum (GGF), http://www.ggf.org
[15] Grid Resource Allocation Agreement Protocol Working Group (GRAAP-WG), http://forge.gridforum.org/projects/graap-wg
[16] S. Greco, B. Matarazzo, R. Słowinski and A. Tsoukias, Exploitation of a rough approximation of the outranking relation in multicriteria choice and ranking, In: T. Stewart
(ed): Multiple Criteria Decision Making. Proceedings of the Thirteenth International Conference, Cape Town (South Africa), January 1997; Springer- Verlag, Berlin (1988).
[17] E. Huedo, R. S. Montero and I. M. Llorente, A Framework for Adaptive Execution on Grids, Journal of Software – Practice and Experience, 34, 631-651 (2004).
[18] E. Jacquet-Lagr‘eze and Y. Siskos, Assessing a set of additive utility functions for multicriteria decision-making, the UTA method, European Journal of Operational Research 10,
151-164 (1982).
[19] Job Submission Description Language (JSDL) Specification, http://forge.gridforum.org/projects/jsdl-wg
[20] K. Kurowski, J. Nabrzyski, A. Oleksiak and J. Węglarz, Multicriteria Aspects of Grid Resource Management, In: Grid Resource Management, J. Nabrzyski, J. Schopf and J. Węglarz (eds.), Kluwer Academic Publishers, Boston/Dordrecht/London (2003).
[21] Kurowski K., Nabrzyski J., Oleksiak, J. Pukacki et al., Programming Grid Applications with Gridge, In: Computational Methods for Science and Technology, by J. Nabrzyski, M. Stroinski, (eds.): Grid Applications – New Challenges for Computational Methods, OWN 2006.
[22] K. Kurowski, A. Oleksiak, J. Nabrzyski, A. Kwiecień, M. Wojtkiewicz, M. Dyczkowski, F. Guim, J. Corbalan and J. Labarta, Multi-criteria Grid Resource Management using Performance Prediction Techniques, In: Proceeding of the CoreGrid Integration Workshop, Pisa (2005).
[23] Oh-Kyoung Kwon, Jaegyoon Hahm, Sangwan Kim and Jongsuk Lee, A Grid Resource Allocation System for Scientific Application: Grid Resource Allocation Services Package
(GRASP), Mardi Gras Conference (2005).
[24] M. Litzkow and M. Livny, Experiences with the Condor distributed batch system, In: Proceedings of the IEEE Workshop on Experimental Distributed Systems (1990).
[25] C. Liu, L. Yang, I. Foster and D. Angulo, Design and evaluation of a resource selection framework for Grid applications, In: Proceedings of the Eleventh IEEE International
Symposium on High-Performance Distributed Computing (HPDC-11) (2002).
[26] E. Medernach, Workload analysis of a cluster in a grid environment. In: D. G. Feitelson, E. Frachtenberg, L. Rudolph and U. Schwiegelshohn (eds.), Job Scheduling Strategiesfor Parallel Processing, pp. 36-61. Springer Verlag, 2005.
[27] J. Nabrzyski., J. Schopf and J. Węglarz (eds.), Grid Resource Management – State of the Art and Future Trends, Kluwer Academic Publishers (2003).
[28] B. Roy, Multicriteria Methodology for Decision Aiding, Kluwer, Dordrecht (1996).
[29] J. Schopf and F. Berman, Performance prediction in production environments. In: Proceedings of IPPS/SPDP (1998).
[30] B. A. Shirazi, A. R. Husson and K. M. Kavi, Scheduling and Load Balancing in Parallel and Distributed Systems, IEEE Computer Society Press (1995).
[31] R. Słowinski, S. Greco and B. Matarazzo, Axiomatization of utility, outranking and decision – rule preference models for multiple-criteria classification problems under partial
incosistency with the dominance principle. Control and Cybernetics, 31(4) (2002).
[32] R. Slowinski, Rough set theory for multicriteria decision analysis, European Journal of Operational Research 129, 1-47 (2001).
[33] W. Smith, V. Taylor and I. Foster, Predicting Application Run-times Using Historical Information, In: Proceedings IPPS/SPDP ’98 Workshop on Job Scheduling Strategies for
Parallel Processing (1988).
[34] W. Smith, I. Foster and V. Taylor, Scheduling with Advanced Reservations, Proceedings of the 2000 International Parallel and Distributed Processing Symposium. May (2000).
[35] W. Smith, V. Taylor and I. Foster, Using Run-Time Predictions to Estimate Queue Wait Times and Improve Scheduler Performance, In: Proceedings of the IPPS/SPDP ’99 Workshop on Job Scheduling Strategies for Parallel Processing (1999).
[36] R. Wolski, N. Spring and J. Hayes, Predicting the CPU availability of time-shared unix systems, In:submitted to SIGMETRICS ’99 (also available as UCSD Technical Report Number CS98-602) (1998).
[37] R. Wolski, N. Spring and J. Hayes, The network weather service: A distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, 15(5-6), 757-768 (1999).