Dynamic Algorithm Selection Using Reinforcement Learning
- 1 December 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 18-25
Abstract
It is often the case that many algorithms exist to solve a single problem, each possessing different performance characteristics. The usual approach in this situation is to manually select the algorithm which has the best average performance. However, this strategy has drawbacks in cases where the optimal algorithm changes during an invocation of the program, in response to changes in the program's state and the computational environment. This paper presents a prototype tool that uses reinforcement learning to guide algorithm selection at runtime, matching the algorithm used to the current state of the computation. The tool is applied to a simulation similar to those used in some computational chemistry problems. It is shown that the low dimensionality of the problem enables the optimal choice of algorithm to be determined quickly, and that the learning system can react rapidly to phase changes in the target programKeywords
This publication has 7 references indexed in Scilit:
- Method-specific dynamic compilation using logistic regression2006
- Online performance auditing2006
- A Survey of Adaptive Optimization in Virtual MachinesProceedings of the IEEE, 2005
- Adaptive java optimisation using instance-based learning2004
- LLVM: A compilation framework for lifelong program analysis & transformation2004
- Issues in data stream managementACM SIGMOD Record, 2003
- An API for Runtime Code PatchingThe International Journal of High Performance Computing Applications, 2000