Multilevel
Scheduling
in HPC
 

PI: Florina Ciorba

Funding agency: Swiss National Science Foundation

(www.snsf.ch)

Duration: 01.09.2017-31.08.2020

Project Summary

High performance computing systems are increasing in size (in terms of node and core count) and diversity (e.g., 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 the 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. Scheduling and load balancing are vital parts of any successful effort of coordinating and managing parallelism in high performance computing.

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 address 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 (e.g., robustness against perturbations) are achieved, and acceptable efficiency (e.g., 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 (e.g., batch and operating system schedulers) with those for cooperative execution (e.g., application level schedulers).

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


Publications


A. Eleliemy and F. M. 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, To appear. [C47.bib]


A. Mohammed and F. M. 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. [C45.bib]


F. M. 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. [C44.bib]


A. Mohammed, A. Eleliemy, and F. M. 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. [C43.bib]


A. Mohammed, A. Eleliemy, F. M. 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. [C42.bib]


A. Eleliemy, A. Mohammed, and F. M. Ciorba, “Scalable 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. [C38.bib]


F. Hoffeins, F. M. 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. [C37.bib]


A. Boulmier, I. Banicescu, F. M. 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. [C36.bib]


A. Eleliemy, A. Mohammed, and F. M. 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. [C35.bib]


Posters

A. Mohammed and F. M. 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 F. M. 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 F. M. 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 F. M. 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 F. M. 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

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 F. M. 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 F. M. 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: F. M. Ciorba

Contributors: F. M. 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 F. M. 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, F. M. 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 F. M. 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, F. M. 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, F. M. 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 F. M. Ciorba

Scientific paper presented at the 16th International Symposium on Parallel and Distributed Computing (ISPDC 2017), Innsbruck, Austria, July 3-6, 2017.

Multilevel scheduling in 
large scale high performance computers