Parallel Reductions: An Application of Adaptive Algorithm Selection Conference Paper uri icon

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

published proceedings

  • LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING

author list (cited authors)

  • Yu, H., Dang, F., & Rauchwerger, L

citation count

  • 3

complete list of authors

  • Yu, Hao||Dang, Francis||Rauchwerger, Lawrence

editor list (cited editors)

  • Pugh, W., & Tseng, C.

publication date

  • January 2005