More Web Proxy on the site http://driver.im/

article

Scheduling parallel jobs on multicore clusters using CPU oversubscription

Authors:

Julita Corbalan,

Jesús LabartaAuthors Info & Claims

The Journal of Supercomputing, Volume 68, Issue 3

Pages 1113 - 1140

https://doi.org/10.1007/s11227-014-1142-9

Published: 01 June 2014 Publication History

Abstract

Job scheduling strategies in multiprocessing systems aim to minimize waiting times of jobs while satisfying user requirements in terms of number of execution units. However, the lack of flexibility in the requests leaves the scheduler a reduced margin of action for scheduling decisions. Many of such decisions consist on just moving ahead some specific jobs in the wait queue. In this work, we propose a job scheduling strategy that improves the overall performance and maximizes resource utilization by allowing jobs to adapt to variations in the load through CPU oversubscription and backfilling. The experimental evaluations include both real executions on multicore clusters and simulations of workload traces from real production systems. The results show that our strategy provides significant improvements over previous proposals like Gang Scheduling with Backfilling, especially in medium to high workloads with strong variations.

References

[1]

Top500 supercomputers sites (2013) http://www.top500.org/. Accessed 7 Mar 2014

[2]

Feitelson DG, Rudolph L, Schwiegelshohn U, Sevcik KC, Wong P (1997) Theory and practice in parallel job scheduling. Lect Notes Comput Sci 1291:1---34

[3]

Feitelson DG, Rudolph L (1996) Toward convergence in job schedulers for parallel supercomputers. In: Job scheduling strategies for parallel processing. Springer-Verlag, New York, pp 1---26

[4]

Utrera G, Corbalán J, Labarta J (2004) Implementing malleability on MPI jobs. In: Proceedings of the 13th international conference on parallel architectures and compilation techniques, PACT '04. IEEE Computer Society, Washington, pp 215---224

Digital Library

[5]

Subotic V, Labarta J, Valero M (2010) Simulation environment for studying overlap of communication and computation. Performance analysis of systems and software (ISPASS). In: 2010 IEEE international symposium on White Plains, pp 115---116

[6]

Utrera G, Tabik S, Corbalán J, Labarta J (2011) A job scheduling approach to reduce waiting times. In: Technical report, Technical University of Catalonia (UPC-DAC-RR-2012-1, October 2011) http://www.ac.upc.edu/app/research-reports/html/2012/1/tec_repor_092011. Accessed 18 Feb 2012

[7]

Feitelson DG, Rudolph L (1992) Gang scheduling performance benefits for fine-grain synchronization. J Parallel Distrib Comput 16(4):306---318

[8]

Zhang Y, Franke H, Moreira J, Sivasubramaniam A (2001) An integrated approach to parallel scheduling using gang-scheduling, backfilling, and migration. Job scheduling strategies for parallel processing. In: Feitelson D, Rudolph L (eds) Lecture notes in computer science, vol 2221. Springer, Berlin, Heidelberg, pp 133---158

[9]

Parallel workload archive (2013) http://www.cs.huji.ac.il/labs/parallel/workload/. Accessed 7 Mar 2014

[10]

Buisson J, Sonmez O, Mohamed H, Lammers W, Epema D (2007) Scheduling malleable applications in multicluster systems. In: Proceedings of the IEEE international conference on cluster computing 2007, pp 372---381

[11]

Cera MC, Georgiou Y, Richard O, Maillard N, Navaux POA (2010) Supporting malleability in parallel architectures with dynamic cpusets mapping and dynamic MPI. In: Proceedings of the 11th international conference on distributed computing and networking, ICDCN'10. Springer-Verlag, Berlin, Heidelberg, pp 242---257

[12]

El Maghraoui K, Desell TJ, Szymanski BK, Varela CA (2007) Dynamic malleability in iterative MPI applications. In: Proceedings of the 7th IEEE international symposium on cluster computing and the grid, CCGRID '07. IEEE Computer Society, Washington, pp 591---598

[13]

Iancu C, Hofmeyr S, Zheng Y, Blagojevic F (2010) Oversubscription on multicore processors. In: 24th international parallel and distributed processing symposium (IPDPS), pp 1---11

[14]

Padhye J, Dowdy LW (1996) Dynamic versus adaptive processor allocation policies for message passing parallel computers: an empirical comparison. In: Proceedings of the workshop on job scheduling strategies for parallel processing. Springer-Verlag, London, pp 224---243

[15]

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

[16]

Downey AB (1997) A model for speedup of parallel programs. In: Technical report, University of California, Berkerley

[17]

Sodan AC, Jin W (2010) Backfilling with fairness and slack for parallel job scheduling. J Phys Conf Ser 256(1):012---023

[18]

Sudarsan R, Ribbens CJ (2009) Scheduling resizable parallel applications. In: International parallel and distributed processing symposium, pp 1---10

[19]

McCann C, Zahorjan J (1994) Processor allocation policies for message-passing parallel computers. In: Proceedings of the 1994 ACM SIGMETRICS conference on measurement and modeling of computer systems, SIGMETRICS '94. ACM, New York, pp 19---32

[20]

NAS Parallel Benchmarks (2013) http://www.nas.nasa.gov/Resources/Software/npb.html. Accessed 7 Mar 2014

[21]

Wiseman Y, Feitelson DG (2003) Paired gang scheduling. IEEE Trans Parallel Distrib Syst 14(6):581---592

Digital Library

[22]

Arpaci-Dusseau AC (2001) Implicit coscheduling: coordinated scheduling with implicit information in distributed systems. ACM Trans Comput Syst 19:283---331

Digital Library

[23]

Zhang Y, Sivasubramaniam A, Moreira J, Franke H (2000) A simulation-based study of scheduling mechanisms for a dynamic cluster environment. In: Proceedings of the 14th international conference on supercomputing, ICS'00. ACM, New York, pp 100---109

[24]

Utrera G, Corbalán J, Labarta J (2004) Scheduling of MPI applications: self-co-scheduling. In: Proceedings of the Euro-Par 2004 conference, 31th August---3rd September 2004, Italy. Lecture notes in computer science, vol 3149, pp 238---245. Springer, New York

[25]

Utrera G, Tabik S, Corbalán J, Labarta J (2012) A job scheduling approach for multi-core clusters based on virtual malleability. In: Euro-Par, pp 191---203

[26]

Lifka DA (1995) The ANL/IBM SP scheduling system. In: Job scheduling strategies for parallel processing. Springer Berlin, Heidelberg, pp 295---303 (1995)

[27]

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

Digital Library

[28]

MPI library (2013) http://www.mcs.anl.gov/research/projects/mpi/. Accessed 7 Mar 2014

[29]

MacDougall MH (1987) Simulating computer systems: techniques and tools. MIT Press, Cambridge

[30]

Subhlok J, Venkataramaiah S, Singh A (2002) Characterizing NAS benchmark performance on shared heterogeneous networks. In: Proceedings of the 16th international parallel and distributed processing symposium, IPDPS '02. IEEE Computer Society, Washington, pp 91

[31]

Intel MPI Benchmarks (2011) http://software.intel.com/en-us/articles/intel-mpi-benchmarks. Accessed 7 Mar 2014

Cited By

Adam JKermarquer MBesnard JBautista-Gomez LPérache MCarribault PJaeger JMalony AShende S(2019)Checkpoint/restart approaches for a thread-based MPI runtimeParallel Computing10.1016/j.parco.2019.02.00685:C(204-219)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.parco.2019.02.006
Utrera GFarreras MFornes J(2019)Task PackingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2019.08.003134:C(37-49)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2019.08.003
de Blanche ALundqvist T(2015)Addressing characterization methods for memory contention aware co-schedulingThe Journal of Supercomputing10.1007/s11227-014-1374-871:4(1451-1483)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11227-014-1374-8

Scheduling parallel jobs on multicore clusters using CPU oversubscription

Recommendations

Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines

The deadline of a request is the time instant at which its execution must complete. The deadline of the request in any period of a job with deferred deadline is some time instant after the end of the period. The authors describe a semi-static priority-...
Robust scheduling of moldable parallel jobs

Moldable job scheduling has been shown to be promising compared with traditional job scheduling policies. In contrast to rigid job scheduling where the number of processors for a job is fixed by the user, with moldable job scheduling the number of ...
A job scheduling approach for multi-core clusters based on virtual malleability
Euro-Par'12: Proceedings of the 18th international conference on Parallel Processing

Many commercial job scheduling strategies in multi processing systems tend to minimize waiting times of short jobs. However, long jobs cannot be left aside as their impact on the performance of the system is also determinant. In this work we propose a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Supercomputing

The Journal of Supercomputing Volume 68, Issue 3

June 2014

629 pages

ISSN:0920-8542

Issue’s Table of Contents

Copyright © Copyright © 2014 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Adam JKermarquer MBesnard JBautista-Gomez LPérache MCarribault PJaeger JMalony AShende S(2019)Checkpoint/restart approaches for a thread-based MPI runtimeParallel Computing10.1016/j.parco.2019.02.00685:C(204-219)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.parco.2019.02.006
Utrera GFarreras MFornes J(2019)Task PackingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2019.08.003134:C(37-49)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.jpdc.2019.08.003
de Blanche ALundqvist T(2015)Addressing characterization methods for memory contention aware co-schedulingThe Journal of Supercomputing10.1007/s11227-014-1374-871:4(1451-1483)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11227-014-1374-8

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents