Design methodology for workload-aware loop scheduling strategies based on genetic algorithm and simulation

摘要

In high-performance computing, the application’s workload must be evenly balanced among threads torndeliver cutting-edge performance and scalability. In OpenMP, the load balancing problem arises whenrnscheduling loop iterations to threads. In this context, several scheduling strategies have been proposed, butrnthey do not take into account the input workload of the application and thus turn out to be suboptimal. In thisrnwork, we introduce a design methodology to propose, study, and assess the performance of workload-awarernloop scheduling strategies. In this methodology, a genetic algorithm is employed to explore the state spacernsolution of the problem itself and to guide the design of new loop scheduling strategies, and a simulator isrnused to evaluate their performance. As a proof of concept, we show how the proposed methodology wasrnused to propose and study a new workload-aware loop scheduling strategy named smart round-robin (SRR).rnWe implemented this strategy into GNU Compiler Collection’s OpenMP runtime. We carry out severalrnexperiments to validate the simulator and to evaluate the performance of SRR. Our experimental results showrnthat SRR may deliver up to 37:89% and 14:10% better performance than OpenMP’s dynamic loop schedulingrnstrategy in the simulated environment and in a real-world application kernel, respectively.