A comprehensive performance evaluation of the BinLPT workload-aware loop scheduler

摘要

Workload-aware loop schedulers were introduced to deliver better performance than classicalloop scheduling strategies. However, they presented limitations such as inflexible built-inworkload estimators and suboptimal chunk scheduling. Targeting these challenges, we proposedpreviously a workload-aware scheduling strategy called BinLPT, which relies on three features:(ⅰ) user-supplied estimations of the workload of the loop; (ⅱ) a greedy heuristic that adaptivelypartitions the iteration space in several chunks; and (ⅲ) a scheduling scheme based on theLongest Processing Time (LPT) rule and on-demand technique. In this paper, we present twonew contributions to the state-of-the-art. First, we introduce a multiloop support featureto BinLPT, which enables the reuse of estimations across loops. Based on this feature, weintegrated BinLPT into a real-world elastodynamics application, and we evaluated it runningon a supercomputer. Second, we present an evaluation of BinLPT using simulations as wellas synthetic and application kernels. We carried out this analysis on a large-scale NUMAmachine under a variety of workloads. Our results revealed that BinLPT is better at balancingthe workloads of the loop iterations and this behavior improves as the algorithmic complexityof the loop increases. Overall, BinLPT delivers up to 37.15% and 9.11% better performancethan well-known loop scheduling strategies, for the application kernels and the elastodynamicssimulation, respectively.