MULTILEVEL SCHEDULING IN LARGE SCALE HIGH PERFORMANCE COMPUTERS

PI : Florina Ciorba

Funding agency : Swiss National Science Foundation ( www.snsf.ch )

Duration : 09/01/2017 – 04/30/2021

Project Summary
High performance computing systems are increasing in size (in terms of node and core count) and diversity (eg, core types per node), leading to an increase in their available parallelism. Hardware parallelism can be found at several levels, from machine instructions to global compute sites. This results in several corresponding levels of software parallelism, from scalar instructions to global job queues. Unfortunately, exploiting the available hardware parallelism even at a single level is notoriously challenging, in part due to difficulty in exposing and expressing parallelism in computational applications. Exposing, expressing, and exploiting parallelism is even more difficult when considering the increase in parallelism within each level and when considering more than a single or a couple of parallelism levels.

This project investigates and develops multilevel scheduling (MLS), a multilevel approach for achieving scalable scheduling in large scale high performance computing systems across the multiple levels of parallelism, with a focus on software parallelism. By integrating multiple levels of parallelism, MLS differs from hierarchical scheduling, traditionally employed to achieve scalability within a single level of parallelism. MLS is based on extending and bridging the most successful (batch, application, and thread) scheduling models beyond single or a couple of parallelism levels (scaling across) and beyond their current scale (scaling out).

The proposed MLS approach leverages all available parallelism and addresses hardware heterogeneity in large-scale high performance computers such that execution times are reduced, performance targets are achieved, and acceptable efficiency is maintained. The methodology for reaching the multilevel scheduling aims involves theoretical research studies, simulation, and experiments.

The outcome is an answer to the following research question: Given massive parallelism, at multiple levels, and of diverse forms and granularities, how can it be ( exposed ,) expressed and exploited such that execution times are reduced, performance targets (eg, robustness against perturbations) are achieved, and acceptable efficiency (eg, the tradeoff between maximizing parallelism and minimizing cost) is maintained?

This project leverages the most efficient existing scheduling solutions to extend them beyond one or two levels, respectively, and to scale them out within single levels of parallelism. The project addresses four tightly coupled problems: scalable scheduling, adaptive and dynamic scheduling, heterogeneous scheduling, and bridging schedulers designed for competitive execution (eg, batch and operating system schedulers) with those for cooperative execution (eg, application-level schedulers).

Overall, the project aims to make a fundamental advance toward simpler use of large-scale high performance computing systems, with impacts not only in the computer science community but also in all computational science domains.

Publications

JH Müller Korndörfer, A. Eleliemy, A. Mohammed, FM Ciorba. “LB4OMP: A Dynamic Load Balancing Library for Multithreaded Applications”. To appear at  Transactions on Parallel and Distributed Systems (TPDS), 2021. https://arxiv.org/abs/2106.05108 [n / a] Videos about LB4OMP ( OpenMP booth video,  OpenMP Users Developer Conference video )

A. Eleliemy and FM Ciorba, “A Distributed Chunk Calculation Approach for Self-scheduling of Parallel Applications on Distributed-memory Systems”, In International Journal of Computational Science, 2021, https://doi.org/10.1016/j.jocs. 2020.101284 ( Open Access ) [ J13.bib ]

A. Eleliemy and FM Ciorba. “A Resourceful Coordination Approach for Multilevel Scheduling”. In Proceedings of the International Conference on High Performance Computing & Simulation (HPCS 2020), Barcelona, ​​Spain, virtual , March 2021, https://arxiv.org/abs/2103.05809, Paper presentation recording [ C61.bib ]

JH Müller Korndörfer, M. Bielert, L. Lima Pilla, FM Ciorba. “Mapping Matters: Application Process Mapping on 3-D Processor Topologies”. In Proceedings of the International Conference on High Performance Computing & Simulation (HPCS 2020), Barcelona, ​​Spain, virtual, March 2021, https://arxiv.org/abs/2005.10413, Paper presentation recording [ C60.bib ]

A. Mohammed, A. Cavelan, FM Ciorba, RM Cabezón, I. Banicescu. “Two-level Dynamic Load Balancing for High Performance Scientific Applications”. In Proceedings of the SIAM Parallel Processing (SIAM PP 2020), Seattle, WA, USA, February 12-15, 2020. https://doi.org/10.1137/1.9781611976137.7. [ C58.bib ] 

A. Mohammed and FM Ciorba, “SimAS: A simulation-assisted approach for the scheduling algorithm selection under perturbations”, In Concurrency and Computation: Practice and Experience (CPE),  2020, https://onlinelibrary.wiley.com / doi / full / 10.1002 / cpe.5648 ( Open Access ) [ J12.bib ]

A. Mohammed, A. Eleliemy, FM Ciorba, F. Kasielke, I. Banicescu, “An Approach for Realistically Simulating the Performance of Scientific Applications on High Performance Computing Systems”, in Future Generation Computer Systems (FGCS),  2020, https: //doi.org/10.1016/j.future.2019.10.007 ( Open Access ) [ J11.bib ]

V. Kale, C. Iwainsky, M. Klemm, JH Müller Korndörfer, and FM Ciorba. “Toward A Standard Interface for User-Defined Scheduling in OpenMP”, in Proceedings of the 2019 International Workshop on OpenMP (iWomp 2019), Auckland, New Zealand, September 11-13, 2019. https://arxiv.org/abs/1906.08911 [ C56.bib ]

A. Mohammed, A. Cavelan, and FM Ciorba, “rDLB: A Novel Approach for Robust Dynamic Load Balancing of Scientific Applications with Independent Tasks”, in Proceedings of the International Conference on High Performance Computing & Simulation (HPCS 2019), Tier B , Dublin, Ireland, July 15-19, 2019. https://arxiv.org/abs/1905.08073 [ C55.bib ]

F. Kasielke, R. Tschüter, M. Velten, C. Iwainsky, FM Ciorba, and I. Banicescu, “Exploring Loop Scheduling Enhancements in OpenMP: An LLVM Case Study”, In Proceedings of the 18th International Symposium on Parallel and Distributed Computing (ISPDC 2019), Tier C , Amsterdam, Netherlands, June 5-7, 2019. [ C52.bib ]

A. Eleliemy and FM Ciorba, “Hierarchical Dynamic Loop Self-Scheduling on Distributed-Memory Systems Using an MPI + MPI Approach”, in Proceedings of the 20th IEEE International Workshop on Parallel and Distributed Scientific and Engineering Computing (PDSEC 2019) of the 33rd IEEE International Parallel and Distributed Processing Symposium Workshops and Ph.D. Forum (IPDPSW 2019), Tier A , Rio de Janeiro, Brazil, May 20-24, 2019. https://arxiv.org/abs/1903.09510 [ C50.bib ]

A. Cavelan, RM Cabezón, JH Müller Korndörfer, and FM Ciorba. “Finding Neighbors in a Forest: Ab-tree for Smoothed Particle Hydrodynamics Simulations”. In Proceedings of the 2019 Spheric International Workshop (SPHERIC 2019), Exeter, UK, June 25-27, 2019. https://arxiv.org/abs/1910.02639 [ C53.bib ]

A. Eleliemy and FM Ciorba, “Dynamic Loop Scheduling Using MPI Passive-Target Remote Memory Access”, Proceedings of the 27th Euromicro International Conference on Parallel, Distributed and Networked-based (PDP 2019), Pavia, Italy, February 13-25, 2019. https://arxiv.org/abs/1901.02773 [C47.bib] 

A. Mohammed and FM Ciorba, “SiL: An Approach for Adjusting Applications to Heterogeneous Systems Under Perturbations”, in Proceedings of the International Workshop on Algorithms, Models, and Tools for Parallel Computing on Heterogeneous Platforms (HeteroPar 2018) of the 24th International European Conference on Parallel and Distributed Computing (Euro-Par 2018), Turin, Italy, August 27-31, 2018. https://arxiv.org/abs/1807.03577 [ C45.bib ]

FM Ciorba, C. Iwainsky, and P. Buder, “OpenMP Loop Scheduling Revisited: Making a Case for More Schedules”, in Proceedings of the 2018 International Workshop on OpenMP (iWomp 2018), Barcelona, ​​Spain, September 21-23 , 2018. https://arxiv.org/abs/1809.03188 [ C44.bib ]

A. Mohammed, A. Eleliemy, and FM Ciorba, “Performance Reproduction and Prediction of Selected Dynamic Loop Scheduling Experiments”, in Proceedings of the 2018 International Conference on High Performance Computing & Simulation (HPCS 2018), Orléans, France, July 16- 20, 2018.  https://arxiv.org/abs/1805.07998 [ C43.bib ]

A. Mohammed, A. Eleliemy, FM Ciorba, F. Kasielke, and I. Banicescu, “Experimental Verification and Analysis of Dynamic Loop Scheduling in Scientific Applications”, in Proceedings of the 17th International Symposium on Parallel and Distributed Computing (ISPDC 2018), Geneva, June 25-28, 2018. https://arxiv.org/abs/1804.11115 [ C42.bib ]

A. Eleliemy, A. Mohammed, and FM Ciorba, “Efficient Generation of Parallel Spin-images Using Dynamic Loop Scheduling”, in Proceedings of the 8th International Workshop on Multicore and Multithreaded Architectures and Algorithms (M2A2 2017) in conjunction with the 19th IEEE International Conference for High Performance Computing and Communications (HPCC 2017), Bangkok, Thailand, December 18-20, 2017. https://arxiv.org/abs/1811.00901 [ C38.bib ]

F. Hoffeins, FM Ciorba, and I. Banicescu, “Towards the Reproducibility of Using Dynamic Loop Scheduling Techniques in Scientific Applications”, in Proceedings of the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017), Tier C, Innsbruck, Austria, July 3-6, 2017. https://edoc.unibas.ch/59513/ [ C37.bib ]

A. Boulmier, I. Banicescu, FM Ciorba, and N. Abdennadher, “An Autonomic Approach for the Selection of Robust Dynamic Loop Scheduling Techniques,” in Proceedings of the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017), Tier C, Innsbruck, Austria, July 3-6, 2017. https://edoc.unibas.ch/59514/ [ C36.bib ]

A. Eleliemy, A. Mohammed, and FM Ciorba, “Exploring the Relation Between Two Levels of Scheduling Using a Novel Simulation Approach”, in Proceedings of the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017), Tier C, Innsbruck, Austria, July 3-6, 2017.  https://arxiv.org/abs/1811.01344 [ C35.bib ]

F. Hoffeins, FM Ciorba, and I. Banicescu, “Examining the Reproducibility of Using Dynamic Loop Scheduling Techniques in Scientific Applications”, in Proceedings of the 4th International Workshop on Reproducibility in Parallel Computing (REPPAR) of the 31st IEEE International Parallel and Distributed Processing Symposium Workshops and Ph.D. Forum (IPDPSW 2017), Tier A, Orlando, USA, June 2, 2017. https://edoc.unibas.ch/59515/ [ C34.bib ]

Posters

A. Eleliemy, FM Ciorba, “Don’t Compete, Let’s Cooperate: A Cooperative Scheduling Approach”, to appear at the Platform for Advanced Scientific Computing (PASC21), 2021.

A. Mohammed, A. Eleliemy, JH Müller Korndörfer, RM Cabezón, FM Ciorba, “Single- and Two-Level Dynamic Load Balancing of Scientific Applications”, to appear at the Platform for Advanced Scientific Computing (PASC21), 2021.

JH Müller Korndörfer, FM Ciorba, A. Yilmaz, C. Iwainsky, J. Doerfert, H. Finkel, V. Kale, M. Klemm, “A Runtime Approach for Dynamic Load Balancing of OpenMP Parallel Loops in LLVM”, presented at the 31st ACM / IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC 2019) ( online ), Tier A , Denver, CO, USA, November 17-22, 2019.

A. Eleliemy and FM Ciorba, “(PhD04) Multilevel Scheduling of Computations in Large-Scale Parallel Computing Systems”, Ph.D. Forum poster presented at the ISC High Performance 2019 Conference ( online ), Frankfurt, Germany, June 17-20, 2019.

A. Mohammed and FM Ciorba, “(PhD03) Design of Robust Scheduling Methodologies in High Performance Computing”, Ph.D. Forum poster presented at the ISC High Performance 2019 Conference ( online ), Frankfurt, Germany, June 17-20, 2019.

FM Ciorba, A. Eleliemy, JH Müller Korndörfer, “MLS: Multilevel Scheduling in Large Scale High Performance”, Project poster presented at the ISC High Performance 2019 Conference ( online) , Frankfurt, Germany, June 17-20, 2019.

A. Mohammed, A. Cavelan, FM Ciorba, RM Cabezón, I. Banicescu, “Identifying Performance Challenges in Smoothed Particle Hydrodynamics Simulations”, presented at the 6th ACM SIGHPC Platform for Advancing Scientific Computing Conference (PASC 2019) ( online ), Zurich , Switzerland, June 12-14, 2019.

A. Mohammed and FM Ciorba, “A Study of the Performance of Scientific Applications with Dynamic Loop Scheduling under Perturbations”, presented at the 2018 Platform for Advanced Scientific Computing Conference (PASC18) ( online ), Basel, Switzerland, July 2-4, 2018. [ P14.bib ]

A. Eleliemy and FM Ciorba, “Performance Evaluation of Dynamic Loop Scheduling Techniques Using MPI Passive RDMA on Distributed Memory Systems”, presented at the 2018 Platform for Advanced Scientific Computing Conference (PASC18) ( online ), Basel, Switzerland, July 2-4 , 2018. [ P13.bib ]

A. Mohammed, A. Eleliemy, and FM Ciorba , “Towards the Reproduction of Selected Dynamic Loop Scheduling Experiments Using SimGrid-SimDag”, presented at the 19th IEEE International Conference for High Performance Computing and Communications (HPCC 2017) ( online ), Tier B , Bangkok, Thailand, December 18-20, 2017. [ P10.bib ]

A. Mohammed, A. Eleliemy, and FM Ciorba , “A Methodology for Bridging the Native and Simulated Execution of Parallel Applications”, presented at the 29th ACM / IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC 2017) ( online ), Tier A , Denver, Colorado, USA, November 12-17, 2017. [ P9.bib ]

A. Eleliemy, A. Mohammed, and FM Ciorba, “Simulating Batch and Application Level Scheduling Using GridSim and SimGrid”, presented at the 28th ACM / IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC 2016) ( online ), Tier A , Salt Lake City, Utah, USA, November 11-18, 2016. [ P6.bib ]

Talks

“LB4OMP: A Load Balancing Library for OpenMP”,
Speaker: JH Müller Korndörfer
Talk and panel discussion at the OpenMP Users Developer Conference, December 2, 2020. ( video ) 

“LB4OMP: A Load Balancing Portfolio for OpenMP”,
Speaker: Jonas H. Müller Korndörfer
Invited talk at the OpenMP Booth at the The International Conference for High Performance Computing, Networking, Storage, and Analysis, September 23, 2020. ( video )

“Two-level Dynamic Load Balancing for High Performance Scientific Applications”
Speaker: A. Mohammed
Scientific paper presented at the SIAM Conference on Parallel Processing for Scientific Computing (SIAM PP20), Seattle, WA, USA, February 12-15, 2020. ( slides )

“Robust Dynamic Load Balancing of Scientific Applications Against Perturbations”
Speaker: F. Ciorba
Invited talk at MS79 of the SIAM Conference on Parallel Processing for Scientific Computing (SIAM PP20), Seattle, WA, USA, February 12-15, 2020. ( slides )

“Dynamic Load Balancing of Loops in OpenMP”,
Speaker: F. Ciorba
Invited talk at the OpenMP Booth at The International Conference for High Performance Computing, Networking, Storage, and Analysis, Denver, CO, USA, November 19, 2019.

“OpenMP Loop Scheduling Revisited: Making a Case for More Schedules”,
Speaker: Florina M. Ciorba
Invited speaker at the 6th ADAC: Accelerated Data Analytics and Computing Institute workshop, Zurich, Switzerland, June 2018.

“Scheduling an Load Balancing in High-Performance Computing: A Multilevel Approach”
Speaker: Florina M. Ciorba
Department of Mathematics and Computer Science Colloquium, University of Basel, Basel, Switzerland, December 2016.

“Dynamic Loop Scheduling Using MPI Passive-Target Remote Memory Access”
Speaker: A. Eleliemy
Contributors: A. Eleliemy and FM Ciorba
Scientific paper presented at the 27th Euromicro International Conference on Parallel, Distributed and Networked-based (PDP 2019), Pavia, Italy, February 13-25, 2019.

“SiL: An Approach for Adjusting Applications to Heterogeneous Systems Under Perturbations”
Speaker: A. Mohammed
Contributors: A. Mohammed and FM Ciorba
Scientific paper presented at the International Workshop on Algorithms, Models, and Tools for Parallel Computing on Heterogeneous Platforms (HeteroPar 2018 ) of the 24th International European Conference on Parallel and Distributed Computing (Euro-Par 2018), Turin, Italy, August 27-31, 2018.

“OpenMP Loop Scheduling Revisited: Making a Case for More Schedules”
Speaker: FM Ciorba
Contributors: FM Ciorba, C. Iwainsky, and P. Buder
Scientific paper presented at the 2018 International Workshop on OpenMP (iWomp 2018), Barcelona, ​​Spain , September 21-23, 2018.

“Performance Reproduction and Prediction of Selected Dynamic Loop Scheduling Experiments”
Speaker: A. Mohammed
Contributors: A. Mohammed, A. Eleliemy, and FM Ciorba
Scientific paper presented at the 2018 International Conference on High Performance Computing & Simulation (HPCS 2018), Orléans , France, July 16-20, 2018. [ C43.bib ]

“Experimental Verification and Analysis of Dynamic Loop Scheduling in Scientific Applications”
Speaker: A. Mohammed
Contributors: A. Mohammed, A. Eleliemy, FM Ciorba, F. Kasielke, and I. Banicescu
Scientific paper presented at the 17th International Symposium on Parallel and Distributed Computing (ISPDC 2018), Geneva, June 25-28, 2018.

“Scalable Generation of Parallel Spin-images Using Dynamic Loop Scheduling”,
Speaker: A. Eleliemy
Contributors: A. Eleliemy, A. Mohammed, and FM Ciorba
Scientific paper presented at the 8th International Workshop on Multicore and Multithreaded Architectures and Algorithms (M2A2 2017 ) in conjunction with the 19th IEEE International Conference for High Performance Computing and Communications (HPCC 2017), Bangkok, Thailand, December 18-20, 2017.

“Towards the Reproducibility of Using Dynamic Loop Scheduling Techniques in Scientific Applications”
Speaker: F. Hoffeins
Contributors: F. Hoffeins, FM Ciorba, and I. Banicescu
Scientific paper presented at the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017), Innsbruck, Austria, July 3-6, 2017.

“An Autonomic Approach for the Selection of Robust Dynamic Loop Scheduling Techniques”
Speaker: A. Boulmier
Contributors: A. Boulmier, I. Banicescu, FM Ciorba, and N. Abdennadher
Scientific paper presented at the 16th International Symposium on Parallel and Distributed Computing ( ISPDC 2017), Innsbruck, Austria, July 3-6, 2017.

“Exploring the Relation Between Two Levels of Scheduling Using a Novel Simulation Approach”
Speaker: A. Eleliemy
Contributors: A. Eleliemy, A. Mohammed, and FM Ciorba
Scientific paper presented at the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017) , Innsbruck, Austria, July 3-6, 2017.