Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC. Authors must sign a non-exclusive distribution agreement after article acceptance.
What to consider for applying backfilling on non-dedicated environments
Keywords:
Space-Sharing, Non-Dedicated clusters, Backfilling, Coscheduling, Load BalancingAbstract
The resource utilization level in open laboratories of several universities has been shown to be very low. Our aim is to take advantage of those idle resources for parallel computation without disturbing the local load. In order to provide a system that lets us execute parallel applications in such a non-dedicated cluster, we use an integral scheduling system that considers both Space and Time sharing concerns. For dealing with the Time Sharing (TS) aspect, we use a technique based on the communicationdriven coscheduling principle. This kind of TS system has some implications on the Space Sharing (SS) system, that force us to modify the way job scheduling is traditionally done. In this paper, we analyze the relation between the TS and the SS systems in a non-dedicated cluster. As a consequence of this analysis, we propose a new technique, termed 3DBackfilling. This proposal implements the well known SS technique of backfilling, but applied to an environment with a MultiProgramming Level (MPL) of the parallel applications that is greater than one. Besides, 3DBackfilling considers the requirements of the local workload running on each node. Our proposal was evaluated in a PVM/MPI Linux cluster, and it was compared with several more traditional SS policies applied to non-dedicated environments.
Downloads
Download data is not yet available.
References
[1] Giné, F. Cooperating Coscheduling: a coscheduling proposal for non-dedicated, multiprogrammed clusters. PhD Thesis, Universitat Autònoma de Barcelona, 2004.
[2] Setia, S., Squillante, M. & Naik, V. The Impact of Job Memory Requirements on Gang-Scheduling Performance 1999.
[3] Hanzich, M.; Giné, F.; Hernández, P.; Solsona, F. & Luque, E. Coscheduling and Multiprogramming Level in a Non-dedicated Cluster. EuroPVM/MPI 2004, LNCS, 2004 , 3241, 327-336.
[4] Feitelson, D.G.; Rudolph, L.; Schwiegelshohn, U.; Sevcik, K.C. & Wong, P. Theory and Practice in Parallel Job Scheduling Lecture Notes in Computer Science, 1997, 1291, 1-34.
[5] Feitelson, D.G. Packing schemes for gang scheduling Job Scheduling Strategies for Parallel Processing, Springer-Verlag, LNCS, 1996, 1162, 89-110.
[6] Hanzich, M. Combining Space And Time Sharing On A Non-Dedicated NOW Universitat Autònoma de Barcelona, 2004.
[7] Zhang, Y.; Franke, H.; Moreira, J.E. & Sivasubramaniam, A. An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration Lecture Notes in Computer Science, 2001 , 2221 , 133-151.
[8] Feitelson, D.G. & Jette, M.A. Improved Utilization and Responsiveness with Gang Scheduling Springer Verlag, 1997, 238-261.
[9] Giné, F.; Solsona, F.; Hernández, P. & Luque, E. Adjusting Time Slices To Apply Coscheduling Techniques in a Non-Dedicated NOW LNCS, 2002 , 2400 , 234-240.
[10] Shmueli, E. & Feitelson, D.G. Backfilling with lookahead to optimize the performance of parallel job scheduling Job Scheduling Strategies for Parallel Processing, LNCS, 2003, 2862, 228-251.
[11] Ousterhout, J. Scheduling techniques for concurrent systems Proceedings of the Conference on Distributed Computing Systems, 1982.
[12] Sobalvarro, P. & Weihl, W. Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors Job Scheduling Strategies for Parallel Processing, LNCS, 1995 , 949 , 106-126
[13] Anglano, C. A Comparative Evaluation of Implicit Coscheduling Strategies for Networks of Workstations Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), 2000 , 221-228.
[14] Frachtenberg, E.; Feitelson, D.G.; Fernández, J. & Petrini, F. Parallel Job Scheduling Under Dynamic Workloads 9th Workshop on Job Scheduling Strategies for Parallel Processing. HPDC, LNCS, 2003 , 2862 , 208-227.
[15] Arpaci, R.; Dusseau, A.; Vahdat, A.; Liu, L.; Anderson, T. & Patterson, D. The Interaction of Parallel and Sequential Workloads on a Network of Workstations ACM SIGMETRICS 1995, 1995, 267-277.
[16] Hanzich, M.; Giné, F.; Hernández, P.; Solsona, F. & Luque, E. CISNE: A New Integral Approach for Scheduling Parallel Applications on Non-Dedicated Clusters Accepted at EuroPar 2005, 2005 , to be appear at LNCS.
[17] Miller, R. Response Time in Man-Computer Conversational Transactions AFIPS Fall Joint Computer Conference Proceedings, 1968 , 33 , 267-277.
[18] Nielsen, J. Nielsen, J. (ed.) Advances in Human-Computer Interaction Intellect Publishers, 1995.
[2] Setia, S., Squillante, M. & Naik, V. The Impact of Job Memory Requirements on Gang-Scheduling Performance 1999.
[3] Hanzich, M.; Giné, F.; Hernández, P.; Solsona, F. & Luque, E. Coscheduling and Multiprogramming Level in a Non-dedicated Cluster. EuroPVM/MPI 2004, LNCS, 2004 , 3241, 327-336.
[4] Feitelson, D.G.; Rudolph, L.; Schwiegelshohn, U.; Sevcik, K.C. & Wong, P. Theory and Practice in Parallel Job Scheduling Lecture Notes in Computer Science, 1997, 1291, 1-34.
[5] Feitelson, D.G. Packing schemes for gang scheduling Job Scheduling Strategies for Parallel Processing, Springer-Verlag, LNCS, 1996, 1162, 89-110.
[6] Hanzich, M. Combining Space And Time Sharing On A Non-Dedicated NOW Universitat Autònoma de Barcelona, 2004.
[7] Zhang, Y.; Franke, H.; Moreira, J.E. & Sivasubramaniam, A. An Integrated Approach to Parallel Scheduling Using Gang-Scheduling, Backfilling, and Migration Lecture Notes in Computer Science, 2001 , 2221 , 133-151.
[8] Feitelson, D.G. & Jette, M.A. Improved Utilization and Responsiveness with Gang Scheduling Springer Verlag, 1997, 238-261.
[9] Giné, F.; Solsona, F.; Hernández, P. & Luque, E. Adjusting Time Slices To Apply Coscheduling Techniques in a Non-Dedicated NOW LNCS, 2002 , 2400 , 234-240.
[10] Shmueli, E. & Feitelson, D.G. Backfilling with lookahead to optimize the performance of parallel job scheduling Job Scheduling Strategies for Parallel Processing, LNCS, 2003, 2862, 228-251.
[11] Ousterhout, J. Scheduling techniques for concurrent systems Proceedings of the Conference on Distributed Computing Systems, 1982.
[12] Sobalvarro, P. & Weihl, W. Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors Job Scheduling Strategies for Parallel Processing, LNCS, 1995 , 949 , 106-126
[13] Anglano, C. A Comparative Evaluation of Implicit Coscheduling Strategies for Networks of Workstations Ninth IEEE International Symposium on High Performance Distributed Computing (HPDC'00), 2000 , 221-228.
[14] Frachtenberg, E.; Feitelson, D.G.; Fernández, J. & Petrini, F. Parallel Job Scheduling Under Dynamic Workloads 9th Workshop on Job Scheduling Strategies for Parallel Processing. HPDC, LNCS, 2003 , 2862 , 208-227.
[15] Arpaci, R.; Dusseau, A.; Vahdat, A.; Liu, L.; Anderson, T. & Patterson, D. The Interaction of Parallel and Sequential Workloads on a Network of Workstations ACM SIGMETRICS 1995, 1995, 267-277.
[16] Hanzich, M.; Giné, F.; Hernández, P.; Solsona, F. & Luque, E. CISNE: A New Integral Approach for Scheduling Parallel Applications on Non-Dedicated Clusters Accepted at EuroPar 2005, 2005 , to be appear at LNCS.
[17] Miller, R. Response Time in Man-Computer Conversational Transactions AFIPS Fall Joint Computer Conference Proceedings, 1968 , 33 , 267-277.
[18] Nielsen, J. Nielsen, J. (ed.) Advances in Human-Computer Interaction Intellect Publishers, 1995.
Downloads
Published
2005-12-01
How to Cite
Hanzich, M., Giné de Solà, F., Hernández Budé, P., Solsona Theás, F., & Luque Fadón, E. (2005). What to consider for applying backfilling on non-dedicated environments. Journal of Computer Science and Technology, 5(04), p. 189–195. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/835
Issue
Section
Original Articles
