SimAS: A Simulation-Assisted Approach for the Algorithm Selection Problem of Scheduling under Perturbations

Many scientific applications consist of large and computationally-intensive loops. Dynamic loop self-scheduling (DLS) techniques are used to parallelize and to balance the load of such applications during execution. Load imbalance arises from variations in the loop iteration (or tasks) execution times, caused by problem, algorithmic, or systemic characteristics. Variations in systemic characteristics are referred to as perturbations. Our hypothesis is that no single DLS technique can achieve the absolute best performance under various perturbations on heterogeneous HPC systems. Therefore, the selection of the most efficient DLS technique is critical to achieve the best application performance. The goal of this work is to solve the algorithm selection problem for the scheduling of computationally-intensive applications under perturbations. Existing work only considers perturbations caused by variations in the delivered computational speed of the HPC systems. However, perturbations in available network bandwidth or latency are inevitable on production HPC systems. A Simulation-assisted scheduling Algorithm Selection (SimAS) approach is introduced herein as a novel control-theoretic-inspired approach to select DLS techniques dynamically that improve the performance of applications executing on heterogeneous HPC systems under perturbations. The present work examines the performance of seven applications on a heterogeneous HPC system under all the above system perturbations. SimAS is evaluated using native and simulative experiments. The performance results confirm the original hypothesis that motivates this work. The experimental evaluation shows that the SimAS-based DLS selection identifies the most efficient technique and improves application performance in most cases.