research-article

Combining performance and priority for scheduling resizable parallel applications

Authors:

Rajesh Sudarsan,

Calvin J. RibbensAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 87, Issue C

Pages 55 - 66

https://doi.org/10.1016/j.jpdc.2015.09.007

Published: 01 January 2016 Publication History

Abstract

We illustrate and evaluate the potential impact of dynamic resizability on parallel job scheduling. Our ReSHAPE framework includes a job scheduler that supports dynamic resizing of malleable parallel applications. We propose and evaluate new scheduling policies and strategies enabled by the ReSHAPE framework. These strategies use both application performance and user-assigned priorities to inform decisions about expanding or contracting the set of processors assigned to a particular job. Experimental results show that the scheduling policies significantly improve individual job turn around time as well as overall cluster utilization. We describe a job scheduler that exploits malleable parallel applications.Processor allocations are based on job performance and on cluster workload.We present scheduling scenarios and algorithms that exploit malleability.Potential benefits when only some jobs are malleable and when job priority varies are studied.

References

[1]

K. Agrawal, Y. He, W.-J. Hsu, C.E. Leiserson, Adaptive scheduling with parallelism feedback, in: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2006, ACM, New York, NY, 2006, pp. 100-109.

[2]

K. Agrawal, Y. He, C.E. Leiserson, Adaptive work stealing with parallelism feedback, in: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2007, ACM, New York, NY, 2007, pp. 112-120.

[3]

L. Barsanti, A. Sodan, Adaptive job scheduling via predictive job resource allocation, in: Job Scheduling Strategies for Parallel Processing, Springer, 2007, pp. 115-140.

[4]

J. Blazewicz, M. Kovalyov, M. Machowiak, D. Trystram, J. Weglarz, Preemptable malleable task scheduling problem, IEEE Trans. Comput., 55 (2006) 486-490.

Digital Library

[5]

J. Blazewicz, M. Machowiak, G. Mounie, D. Trystram, Approximation algorithms for scheduling independent malleable tasks, in: Euro-Par, 2001, pp. 191-197.

[6]

R.D. Blumofe, C.E. Leiserson, Scheduling multithreaded computations by work stealing, J. ACM, 46 (1999) 720-748.

Digital Library

[7]

T.B. Brecht, K. Guha, Using parallel program characteristics in dynamic processor allocation policies, Perform. Eval., 27-28 (1996) 519-539.

Digital Library

[8]

J. Buisson, F. André, J.-L. Pazat, A framework for dynamic adaptation of parallel components, in: PARCO, 2005, pp. 65-72.

[9]

J. Buisson, O. Sonmez, H. Mohamed, W. Lammers, D. Epema, Scheduling malleable applications in multicluster systems, in: IEEE Intl Conf on Cluster Computing, 2007, pp. 372-381.

Digital Library

[10]

M. Calzarossa, G. Serazzi, A characterization of the variation in time of workload arrival patterns, IEEE Trans. Comput., 100 (1985) 156-162.

Digital Library

[11]

M.C. Cera, G.P. Pezzi, M.L. Pilla, N. Maillard, P.O.A. Navaux, Scheduling dynamically spawned processes in MPI-2, in: Lecture Notes in Computer Science, vol. 4376, Springer, 2006, pp. 33-46.

[12]

S. Chiang, A. Arpaci-Dusseau, M. Vernon, The impact of more accurate requested runtimes on production job scheduling performance, in: Job Scheduling Strategies for Parallel Processing, Springer, 2002, pp. 103-127.

[13]

S.-H. Chiang, R.K. Mansharamani, M.K. Vernon, Use of application characteristics and limited preemption for run-to-completion parallel processor scheduling policies, in: Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, 1994, pp. 33-44.

[14]

S.-H. Chiang, M. Vernon, Dynamic vs. static quantum-based parallel processor allocation, in: Lecture Notes in Computer Science, vol. 1162, Springer, 1996, pp. 200-223.

[15]

W. Cirne, F. Berman, Adaptive selection of partition size for supercomputer requests, in: Proceedings, Workshop on Job Scheduling Strategies for Parallel Processing, Springer, 2000, pp. 187-208.

Digital Library

[16]

W. Cirne, F. Berman, A model for moldable supercomputer jobs, in: Proceedings of the 15th International Parallel and Distributed Processing Symposium, 2001.

Digital Library

[17]

W. Cirne, F. Berman, Using moldability to improve the performance of supercomputer jobs, J. Parallel Distrib. Comput., 62 (2002) 1571-1601.

Digital Library

[18]

J. Corbalan, X. Martorell, J. Labarta, Performance-driven processor allocation, IEEE Trans. Parallel Distrib. Syst., 16 (2005) 599-611.

Digital Library

[19]

A.B. Downey, A parallel workload model and its implications for processor allocation, Cluster Comput., 1 (1998) 133-145.

Digital Library

[20]

P. Dutot, D. Trystram, Scheduling on hierarchical clusters using malleable tasks, in: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001, pp. 199-208.

[21]

D. Feitelson, Packing schemes for gang scheduling, Lecture Notes in Comput. Sci., 1162 (1996) 89-111.

[22]

D. Feitelson, M. Jette, Improved utilization and responsiveness with gang scheduling, Lecture Notes in Comput. Sci., 1291 (1997) 238-261.

[23]

D.G. Feitelson, L. Rudolph, Toward convergence in job schedulers for parallel supercomputers, in: Proceedings, Workshop on Job Scheduling Strategies for Parallel Processing, Springer, 1996, pp. 1-26.

Digital Library

[24]

D. Feitelson, L. Rudolph, Metrics and benchmarking for parallel job scheduling, in: Lecture Notes in Computer Science, vol. 1459, Springer, 1998, pp. 1-24.

Digital Library

[25]

D. Feitelson, L. Rudolph, U. Schwiegelshohn, Parallel job scheduling-a status report, Lecture Notes in Comput. Sci., 3277 (2005) 1-16.

Digital Library

[26]

D.G. Feitelson, L. Rudolph, U. Schwiegelshohn, K.C. Sevcik, P. Wong, Theory and practice in parallel job scheduling, in: IPPS'97: Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, Springer, London, UK, 1997, pp. 1-34.

[27]

A. Feldmann, J. Sgall, S.-H. Teng, Dynamic scheduling on parallel machines, Theoret. Comput. Sci., 130 (1994) 49-72.

Digital Library

[28]

R. Graham, T. Woodall, J. Squyres, Open MPI: a flexible high performance MPI, in: Proceedings, 6th Annual International Conference on Parallel Processing and Applied Mathematics, 2005, pp. 228-239.

[29]

Y. He, W. Hsu, C. Leiserson, Provably efficient online non-clairvoyant adaptive scheduling, in: Parallel and Distributed Processing Symposium, IPDPS 2007, 2007, pp. 1-10.

[30]

Y. He, W. jing Hsu, C.E. Leiserson, Provably efficient two-level adaptive scheduling, in: Job Scheduling Strategies for Parallel Processing, Springer, 2007, pp. 1-32.

[31]

C. Huang, O. Lawlor, L. Kalé, Adaptive MPI, Languages and Compilers for Parallel Computing (2004) 306-322.

[32]

D. Jackson, Q. Snell, M. Clement, Core algorithms of the Maui scheduler, in: Job Scheduling Strategies for Parallel Processing, Springer, 2001, pp. 87-102.

[33]

J. Jann, P. Pattnaik, H. Franke, F. Wang, J. Skovira, J. Riodan, Modeling of workload in MPPs, in: Lecture Notes in Computer Science, vol. 1291, Springer, 1997, pp. 95-116.

[34]

L. Kale, S. Krishnan, Charm++: A portable concurrent object oriented system based on C++, in: Proceedings of the Eighth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, ACM, 1993, pp. 91-108.

[35]

W. Leland, T. Ott, Load-balancing heuristics and process behavior, ACM SIGMETRICS Performance Eval. Rev., 14 (1986) 54-69.

[36]

D. Lifka, The ANL/IBM SP scheduling system, in: Job Scheduling Strategies for Parallel Processing, Springer, 1995, pp. 295-303.

[37]

U. Lublin, D.G. Feitelson, The workload on parallel supercomputers: Modeling the characteristics of rigid jobs, J. Parallel Distrib. Comput., 63 (2003) 1105-1122.

Digital Library

[38]

C. McCann, R. Vaswani, J. Zahorjan, A dynamic processor allocation policy for multiprogrammed shared-memory multiprocessors, ACM Trans. Comput. Syst., 11 (1993) 146-178.

Digital Library

[39]

C. McCann, J. Zahorjan, Processor allocation policies for message-passing parallel computers, in: Proceedings of the 1994 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, ACM, New York, NY, 1994, pp. 19-32.

[40]

Moab scheduler, URL: http://www.clusterresources.com/products-/moab-cluster-suite.php.

[41]

J.E. Moriera, V.K. Naik, Dynamic resource management on distributed systems using reconfigurable applications, IBM J. Res. Dev., 41 (1997) 303-330.

Digital Library

[42]

G. Mounie, C. Rapine, D. Trystram, Efficient approximation algorithms for scheduling malleable tasks, in: Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, ACM, 1999, pp. 23-32.

Digital Library

[43]

A. Mu'alem, D. Feitelson, Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling, IEEE Trans. Parallel Distrib. Syst. (2001) 529-543.

[44]

T. Nguyen, R. Vaswani, J. Zahorjan, Using runtime measured workload characteristics in parallel processor scheduling, in: Lecture Notes in Computer Science, vol. 1162, Springer, 1996, pp. 155-174.

[45]

J. Ousterhout, Scheduling techniques for concurrent systems, in: Proceedings of the 3rd International Conference on Distributed Computing Systems, 1982, pp. 22-30.

[46]

J. Padhye, L. Dowdy, Dynamic versus adaptive processor allocation policies for message passing parallel computers: An empirical comparison, in: Lecture Notes in Computer Science, vol. 1162, Springer, 1996, pp. 224-243.

[47]

Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing, Boston, 1996.

[48]

G. Sabin, M. Lang, P. Sadayappan, Moldable parallel job scheduling using job efficiency: An iterative approach, in: Job Scheduling Strategies for Parallel Processing, Springer, 2007, pp. 94-114.

[49]

K.C. Sevcik, Application scheduling and processor allocation in multiprogrammed parallel processing systems, Perform. Eval., 19 (1994) 107-140.

Digital Library

[50]

E. Shmueli, D. Feitelson, Backfilling with lookahead to optimize the performance of parallel job scheduling, Lecture Notes in Comput. Sci., 2862 (2003) 228-251.

[51]

J. Skovira, W. Chan, H. Zhou, D. Lifka, The easy-loadleveler api project, Lecture Notes in Comput. Sci. (1996) 41-47.

[52]

S. Srinivasan, R. Kettimuthu, V. Subramani, P. Sadayappan, Selective reservation strategies for backfill job scheduling, in: Job Scheduling Strategies for Parallel Processing, Springer, 2002, pp. 55-71.

[53]

S. Srinivasan, S. Krishnamoorthy, P. Sadayappan, A robust scheduling technology for moldable scheduling of parallel jobs, in: 2003 IEEE International Conference on Cluster Computing, 2003. Proceedings, 2003, pp. 92-99.

[54]

R. Sudarsan, C.J. Ribbens, ReSHAPE: A Framework for Dynamic Resizing and Scheduling of Homogeneous Applications in a Parallel Environment, in: Proceedings of the 2007 International Conference on Parallel Processing (ICPP), XiAn, China, 2007, p. 44.

Digital Library

[55]

R. Sudarsan, C.J. Ribbens, Efficient multidimensional data redistribution for resizable parallel computations, in: Proceedings of the International Symposium on Parallel and Distributed Processing and Applications, ISPA 07, 2007, pp. 182-194.

[56]

R. Sudarsan, C.J. Ribbens, Scheduling resizable parallel applications, in: Proceedings of the 2009 IEEE International Symposium on Parallel & Distributed Processing, IEEE Computer Society, 2009, pp. 10 pages.

Digital Library

[57]

R. Sudarsan, C.J. Ribbens, Design and performance of a scheduling framework for resizable parallel applications, Parallel Comput., 36 (2010) 48-64.

Digital Library

[58]

R. Sudarsan, C.J. Ribbens, D. Farkas, Dynamic resizing of parallel scientific simulations: A case study using lammps, in: LNCS, vol. 5544, Springer, 2009, pp. 175-184.

[59]

H. Sun, Y. Cao, W. Hsu, Efficient adaptive scheduling of multiprocessors with stable parallelism feedback, IEEE Trans. Parallel Distrib. Syst., 22 (2011) 594-607.

Digital Library

[60]

H. Sun, Y. Cao, W.-J. Hsu, Competitive two-level adaptive scheduling using resource augmentation, in: Lecture Notes in Computer Science, vol. 5798, Springer, 2009, pp. 207-231.

[61]

D. Talby, D. Feitelson, Supporting priorities and improving utilization of the IBM SP scheduler using slack-based backfilling, in: 13th Intl. Parallel Processing Symp., IEEE Computer Society, 1999, pp. 513-517.

[62]

D. Tsafrir, Y. Etsion, D. Feitelson, Backfilling using system-generated predictions rather than user runtime estimates, IEEE Trans. Parallel Distrib. Syst. (2007) 789-803.

[63]

D. Tsafrir, Y. Etsion, D.G. Feitelson, Modeling user runtime estimates, in: Lect. Notes Comput. Sci., vol. 3834, Springer, 2005, pp. 1-35.

Digital Library

[64]

A. Tucker, A. Gupta, Process control and scheduling issues for multiprogrammed shared-memory multiprocessors, in: Proceedings of the Twelfth ACM Symposium on Operating Systems Principles, SOSP'89, ACM, New York, NY, 1989, pp. 159-166.

Digital Library

[65]

G. Utrera, J. Corbalan, J. Labarta, Implementing malleability on MPI jobs, in: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, IEEE Computer Society, 2004, pp. 215-224.

[66]

S. Vadhiyar, J. Dongarra, Self adaptivity in grid computing, Concurrency comput., Pract. Exp., 17 (2005) 235-257.

Digital Library

[67]

J.B. Weissman, Prophet: Automated scheduling of SPMD programs in workstation networks, Concurrency, Pract. Exp., 11 (1999) 301-321.

[68]

J.B. Weissman, L. Rao, D. England, Integrated scheduling: The best of both worlds, J. Parallel Distrib. Comput., 63 (2003) 649-668.

Digital Library

[69]

J. Zahorjan, C. McCann, Processor scheduling in shared memory multiprossors, in: Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, ACM, New York, NY, 1990, pp. 214-225.

Cited By

Martín-Álvarez IAliaga JCastillo MIserte S(2024)Proteo: a framework for the generation and evaluation of malleable MPI applicationsThe Journal of Supercomputing10.1007/s11227-024-06277-580:15(23083-23119)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06277-5
Posner JHupfeld FFinnerty P(2023)Enhancing Supercomputer Performance with Malleable Job Scheduling StrategiesEuro-Par 2023: Parallel Processing Workshops10.1007/978-3-031-48803-0_14(180-192)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-48803-0_14
Mascagni MIserte SMartínez HBarrachina SCastillo MMayo RPeña A(2020)Dynamic reconfiguration of noniterative scientific applicationsInternational Journal of High Performance Computing Applications10.1177/109434201880234733:5(804-816)Online publication date: 17-Jun-2020
https://dl.acm.org/doi/10.1177/1094342018802347
Show More Cited By

Recommendations

Improvements in Parallel Job Scheduling Using Gang Service
ISPAN '99: Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks

Gang scheduling has been widely used as a practical solution to the dynamic parallel job scheduling problem. Parallel threads of a single job are scheduled for simultaneous execution on a parallel computer even if the job does not fully utilize all ...
A Multi-constraint Preemption Algorithm for Parallel Job Scheduling
PDCAT '11: Proceedings of the 2011 12th International Conference on Parallel and Distributed Computing, Applications and Technologies

Using effective scheduling strategies to improve turnaround time, slowdown, and utilization is an important consideration in large supercomputing environments. Since such machines have traditionally used non-preemption strategies to accommodate multiple ...
The Impact of Critical Sporadic Jobs on Gang Scheduling Performance in Distributed Systems

A commonly used task scheduling algorithm for parallel and distributed systems is gang scheduling. In this paper, we study gang scheduling performance in the presence of critical sporadic jobs. A simulation model is used to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 87, Issue C

January 2016

155 pages

ISSN:0743-7315

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 08 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Martín-Álvarez IAliaga JCastillo MIserte S(2024)Proteo: a framework for the generation and evaluation of malleable MPI applicationsThe Journal of Supercomputing10.1007/s11227-024-06277-580:15(23083-23119)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s11227-024-06277-5
Posner JHupfeld FFinnerty P(2023)Enhancing Supercomputer Performance with Malleable Job Scheduling StrategiesEuro-Par 2023: Parallel Processing Workshops10.1007/978-3-031-48803-0_14(180-192)Online publication date: 28-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-48803-0_14
Mascagni MIserte SMartínez HBarrachina SCastillo MMayo RPeña A(2020)Dynamic reconfiguration of noniterative scientific applicationsInternational Journal of High Performance Computing Applications10.1177/109434201880234733:5(804-816)Online publication date: 17-Jun-2020
https://dl.acm.org/doi/10.1177/1094342018802347
Liao JYin DPeng X(2018)Block I/O Scheduling on Storage Servers of Distributed File SystemsJournal of Grid Computing10.1007/s10723-017-9423-116:2(299-316)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10723-017-9423-1

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents