Home research People General Info Seminars Resources Intranet

Hao Yu, Dongmin Zhang, Francis Dang, Lawrence Rauchwerger, "An Adaptive Algorithm Selection Framework," Technical Report, TR04-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Mar 2004.
Technical Report(ps, pdf, abstract)

Irregular and dynamic memory reference patterns can cause performance variations for low level algorithms in general and for parallel algorithms in particular. We have previously shown that parallel algorithms (reductions, sorting) are input sensitive and can benefit from adaptation to their inputs and environment. Here we present an Adaptive Algorithm Selection Framework which can collect and interpret the inputs of a particular instance of a parallel algorithm and select the best performing one from a an existing library. In this paper we use our framework to select dynamically the best parallel reduction algorithm. We first introduce a set of high-level parameters that can model and rank the performance of different parallel reduction algorithms. Then we describe an off-line, systematic process to generate predictive models which can be used for run-time algorithm selection. A compiler generated instrumentation code dynamically characterizes a reduction loop�s reference pattern and selects the most appropriate method for parallelizing it. Our experiments show that our framework: (a) Selects the most appropriate algorithms in 85% of the cases studied (b) When the best possible algorithm was not selected the performance is still within 2% of the optimal scheme�s performance. (c) Adaptively selects the best algorithms for each phase of a dynamic program resulting in better overall performance (d) Adapts to the underlying machine architecture. (tested on IBM Regatta and HP V-Class).