Automatic Selection of Loop Scheduling Algorithms Using Reinforcement Learning

Dhandayuthapani, S., Banicescu, I., Carino, R.L., Hansen, E., Pabico, J. P., & Rashid, M. (2005). Automatic Selection of Loop Scheduling Algorithms Using Reinforcement Learning. Proceedings of the 2005 International Workshop on Challenges of Large Applications in Distributed Environments. Atlanta, GA: IEEE Computer Society Press. 87-94.

This paper presents the design and implementation of a reinforcement learning agent that automatically selects appropriate loop scheduling algorithms for parallel loops embedded in time-stepping scientific applications executing on clusters. There may be a number of such loops in an application, and the loops may have different load balancing requirements. Further, loop characteristics may also change as the application progresses. Following a model-free learning approach, the learning agent assigned to a loop selects from a library the best scheduling algorithm for the loop during the lifetime of the application. The utility of the learning agent is demonstrated by its successful integration into the simulation of wave packets - an application arising from quantum mechanics. Results of statistical analysis using pairwise comparison of means on the running time of the simulation with and without the learning agent validate the effectiveness of the agent in improving the parallel performance of the simulation.