Parallel reductions: An application of adaptive algorithm selection
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Irregular and dynamic memory reference patterns can cause significant performance variations for low level algorithms in general and especially for parallel algorithms. We have previously shown that parallel reduction algorithms are quite input sensitive and thus can benefit from an adaptive, reference pattern directed selection. In this paper we extend our previous work by detailing a systematic approach to dynamically select the best parallel algorithm. First we model the characteristics of the input, i.e., the memory reference pattern, with a descriptor vector. Then we measure the performance of several reduction algorithms for various values of the pattern descriptor. Finally we establish a (many-to-one) mapping (function) between a finite set of descriptor values and a set of algorithms. We thus obtain a performance ranking of the available algorithms with respect to a limited set of descriptor values. The actual dynamic selection code is generated using statistical regression methods or a decision tree. Finally we present experimental results to validate our modeling and prediction techniques. Springer-Verlag Berlin Heidelberg 2005.
name of conference
Languages and Compilers for Parallel Computing, 15th Workshop, LCPC 2002, College Park, MD, USA, July 25-27, 2002, Revised Papers
