Seminar: Scheduling – Modern Problems in a Seemingly Solved Discipline (IN0014,IN2107)

Dr. Matthias Maiterth

Dates:	Mondays 14:00-16:00, room 00.08.059, Seminarraum (5608.EG.059)
First meeting:	02.05.2022
ECTS:	5
Language:	English
Type:	Seminar, 2S

Motivation

In high performance computing (HPC), scheduling is a central aspect for efficient processing of applications and user workloads. This seminar looks at traditional aspects of job or batch scheduling and analyizes modern takes and solutions for this long standing (and seeminlgy solved) problem.

Aspects discussed in the seminar are:

Traditional scheduling — FCFS, SJF, backfilling
Job and batch schedulers in HPC
Usage and scheduling of containers in HPC
Workflow scheduling
Additional resources: Energy as resource, quantum and other domain specific resources
Simulators for schedulers
Task and process scheduling

The students will select material for the presentation, provide a report, and give a presentation.

Slides and Documents:

Topic List:

1. Metrics and Fundamentals of Scheduling	Parallel Job Scheduling — A Status Report, JSSPP 2004, (http://dx.doi.org/10.1007/11407522_1) Theory and Practice in Parallel Job Scheduling, JSSPP 1997 (https://www.cs.huji.ac.il/w~feit/parsched/jsspp97/p-97-1.pdf) Characteristics of Fairness Metrics and their Effect on Perceived Scheduler Effectiveness, IJCA 2010 (https://doi.org/10.1080/1206212X.2010.11441974) Fattened backfilling: An improved strategy for job scheduling in parallel systems, JPDC 2016 (https://www.sciencedirect.com/science/article/abs/pii/S0743731516300788)
2. Threads and Tasks Scheduling	BOLT: Optimizing OpenMP Parallel Regions with User-Level Threads, PACT'19 (https://pavanbalaji.github.io/pubs/2019/pact/pact19.bolt.pdf) Task-graph scheduling extensions for efficient synchronization and communication, ISC'21 (https://dl.acm.org/doi/abs/10.1145/3447818.3461616?sid=SCITRUS) LB4OMP: A Dynamic Load Balancing Library for Multithreaded Applications, TPDS'22 (https://ieeexplore.ieee.org/document/9524500)
3. GPU Scheduling (Warps and Compute Units)	Improving GPU Performance via Large Warps and Two-Level Warp Scheduling MICRO, 2011 (https://users.ece.cmu.edu/~omutlu/pub/large-gpu-warps_micro11.pdf) Simultaneous Branch and Warp Interweaving for Sustained GPU Performance, ISCA 2012 (https://hal-ens-lyon.archives-ouvertes.fr/ensl-00649650v2/document) Exploiting Inter-Warp Heterogeneity to Improve GPGPU Performance, PACT'15 (https://dl.acm.org/doi/10.1109/PACT.2015.38)
4. Process Scheduling (OS)	Thread and memory placement on NUMA systems: asymmetry matters, USENIX ATC 2015 (https://www.usenix.org/system/files/conference/atc15/atc15-paper-lepers.pdf) Improving Resource Utilization through Demand Aware Process Scheduling, ICPP'18 (https://dl.acm.org/doi/10.1145/3225058.3225132) Collaborative Heterogeneity-Aware OS Scheduler for Asymmetric Multicore Processors, TPDS'21 (https://ieeexplore.ieee.org/document/9296343)
5. Modern Batch Scheduling by example of FLUX	Flux: A Next-Generation Resource Management Framework for Large HPC Centers, ICPP 2014 ( https://flux-framework.org/publications/Flux-SRMPDS-final.pdf ) Flux: Overcoming Scheduling Challenges for Exascale Workflows, WORKS 2018 ( https://ieeexplore.ieee.org/abstract/document/8638377 ) Evaluation of an Interference-free Node Allocation Policy on Fat-tree Clusters, SC'18 ( https://flux-framework.org/publications/a26-pollard.pdf )
6. Clouds and Container Scheduling	A Survey on Resource Scheduling in Cloud Computing: Issues and Challenges, Journal of Grid Computing 2016, (https://link.springer.com/article/10.1007/s10723-015-9359-2) Towards Interference-Aware Dynamic Scheduling in Virtualized Environments, JSSPP 2020 (https://link.springer.com/chapter/10.1007/978-3-030-63171-0_1) Container scheduling techniques: A Survey and assessment, J of King Saud University - Computer and Information Sciences ( https://doi.org/10.1016/j.jksuci.2021.03.002 )
7. Large-Scale Cluster management by example of Borg	Large-scale cluster management at Google with Borg, EuroSys 2015 (https://research.google/pubs/pub43438/) Borg: the Next Generation, EuroSys 2020 (https://research.google/pubs/pub49065/) Autopilot: workload autoscaling at Google, EuroSys ’20 (https://dl.acm.org/doi/10.1145/3342195.3387524)
8. Scheduling for Heterogeneous Systems	GPU age-aware scheduling to improve the reliability of leadership jobs on Titan, SC'18 ( https://dl.acm.org/doi/10.1109/SC.2018.00010 ) Busy-Time Scheduling on Heterogeneous Machines, IPDPS'20 (https://personal.ntu.edu.sg/asxytang/papers/ipdps2020.pdf) MARBLE: A Multi-GPU Aware Job Scheduler for Deep Learning on HPC Systems, CCGRID 2020(https://par.nsf.gov/biblio/10167822)
9. Workflows and scheduling	Enabling Workflow-Aware Scheduling on HPC Systems, HPDC'17 (https://dl.acm.org/doi/10.1145/3078597.3078604) Melissa: large scale in transit sensitivity analysis avoiding intermediate files, SC'17 (https://dl.acm.org/doi/10.1145/3126908.3126922) GLUME: A Strategy for Reducing Workflow Execution Times on Batch-Scheduled Platforms, JSSPP 2021, (https://link.springer.com/chapter/10.1007/978-3-030-88224-2_11)
10. Co-Scheduling	Hypart: a hybrid technique for practical memory bandwidth partitioning on commodity servers, PACT'18 ( https://dl.acm.org/doi/10.1145/3243176.3243211 ) Co-Scheduling HPC Workloads on Cache-Partitioned CMP Platforms, CLUSTER'18 (https://people.bordeaux.inria.fr/gaupy/ressources/pub/confs/cluster18_cache.pdf) Co-Run Scheduling with Power Cap on Integrated CPU-GPU Systems, IPDPS'17 (https://people.engr.ncsu.edu/xshen5/Publications/ipdps17.pdf)
11. IO-Aware Scheduling	Scheduling Beyond CPUs for HPC, HPDC'19 (https://dl.acm.org/doi/10.1145/3307681.3325401) Scalable I/O-Aware Job Scheduling for Burst Buffer Enabled HPC Clusters, HPDC'16 ( https://dl.acm.org/doi/10.1145/2907294.2907316 ) Mapping and scheduling HPC applications for optimizing I/O ( https://dl.acm.org/doi/10.1145/3392717.3392764)
12. Malleability	Combining malleability and I/O control mechanisms to enhance the execution of multiple applications. J. Syst. Softw., 2019 (https://doi.org/10.1016/j.jss.2018.11.006) Infrastructure and API Extensions for Elastic Execution of MPI Applications, EuroMPI 2016 (https://doi.org/10.1145/2966884.2966917) Holistic Slowdown Driven Scheduling and Resource Management for Malleable Jobs, ICPP 2019 (https://doi.org/10.1145/3337821.3337909)
13. Power-Aware Scheduling	Power Aware Heterogeneous Node Assembly, HPCA'19 (https://ieeexplore.ieee.org/document/8675210) Power efficient job scheduling by predicting the impact of processor manufacturing variability, ICS'19 (https://dl.acm.org/doi/10.1145/3330345.3330372) A data driven scheduling approach for power management on HPC systems, SC'16 (https://dl.acm.org/doi/10.5555/3014904.3014979)
14. ML-Based Scheduling	RLScheduler: an automated HPC batch job scheduler using reinforcement learning, SC'20 (https://dl.acm.org/doi/abs/10.5555/3433701.3433742) Obtaining dynamic scheduling policies with simulation and machine learning, SC'17 ( https://hal.inria.fr/hal-01618940/document ) Deep Reinforcement Agent for Scheduling in HPC, IPDPS'21 (https://arxiv.org/pdf/2102.06243.pdf)
15. Scheduling for Quantum Systems	Quantum Accelerators for High-Performance Computing Systems, ICRC 2017 ( https://www.osti.gov/biblio/1412048 ) High-Performance Computing with Quantum Processing Units, JETC 2017 ( https://doi.org/10.1145/3007651 ) XACC: a system-level software infrastructure for heterogeneous quantum–classical computing, Quantum Science and Technology 2020 ( https://iopscience.iop.org/article/10.1088/2058-9565/ab6bf6 ) OpenQL: A Portable Quantum Programming Framework for Quantum Accelerators, JETC 2022, ( https://dl.acm.org/doi/10.1145/3474222 )