An Adaptive Algorithm Selection Framework
Hao Yu, Dongmin Zhang, Lawrence Rauchwerger · 2004
Irregular and dynamic memory reference patterns can cause performance variations for low level algo-rithms in general and for parallel algorithms in partic-ular. We present an adaptive algorithm selection frame-work which can collect and interpret the inputs of a par-ticular instance of a parallel algorithm and select the best performing one from a an existing library. In this paper present the dynamic selection of parallel reduc-tion algorithms. First we introduce a set of high-level pa-rameters that can characterize different parallel reduc-tion algorithms. Then we describe an off-line, system-atic process to generate predictive models which can be used for run-time algorithm selection. Our experiments show that our framework: (a) selects the most appro-priate algorithms in 85 % of the cases studied, (b) over-all delievers 98 % of the optimal performance, (c) adap-tively selects the best algorithms for dynamic phases of a running program (resulting in performance improve-ments otherwise not possible), and (d) adapts to the un-derlying machine architecture (tested on IBM Regatta and HP V-Class systems). 1.