Skip to Main content Skip to Navigation
Conference papers

Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling

Abstract : Scheduling in High-Performance Computing (HPC) has been traditionally centered around computing resources (e.g., processors/cores). The ever-growing amount of data produced by modern scientific applications start to drive novel architectures and new computing frameworks to support more efficient data processing, transfer and storage for future HPC systems. This trend towards data-driven computing demands the scheduling solutions to also consider other resources (e.g., I/O, memory, cache) that can be shared amongst competing applications. In this paper, we study the problem of scheduling HPC applications while exploring the availability of multiple types of resources that could impact their performance. The goal is to minimize the overall execution time, or makespan, for a set of moldable tasks under multiple-resource constraints. Two scheduling paradigms, namely, list scheduling and pack scheduling, are compared through both theoretical analyses and experimental evaluations. Theoretically, we prove, for several algorithms falling in the two scheduling paradigms, tight approximation ratios that increase linearly with the number of resource types. As the complexity of direct solutions grows exponentially with the number of resource types, we also design a strategy to indirectly solve the problem via a transformation to a single-resource-type problem, which can significantly reduce the algorithms' running times without compromising their approximation ratios. Experiments conducted on Intel Knights Landing with two resource types (processor cores and high-bandwidth memory) and simulations designed on more resource types confirm the benefit of the transformation strategy and show that pack-based scheduling, despite having a worse theoretical bound, offers a practically promising and easy-to-implement solution, especially when more resource types need to be managed.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Guillaume Pallez (aupy) Connect in order to contact the contributor
Submitted on : Tuesday, December 11, 2018 - 2:09:58 PM
Last modification on : Friday, January 21, 2022 - 3:10:40 AM
Long-term archiving on: : Tuesday, March 12, 2019 - 2:24:19 PM


Files produced by the author(s)




Hongyang Sun, Redouane Elghazi, Ana Gainaru, Guillaume Aupy, Padma Raghavan. Scheduling Parallel Tasks under Multiple Resources: List Scheduling vs. Pack Scheduling. IPDPS 2018 - 32nd IEEE International Parallel & Distributed Processing Symposium, May 2018, Vancouver, Canada. ⟨10.1109/IPDPS.2018.00029⟩. ⟨hal-01951412⟩



Les métriques sont temporairement indisponibles