Parallel reductions: An application of adaptive algorithm selection

Hao Yu, Francis Dang, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 15th Workshop, LCPC 2002, Revised Papers
PublisherSpringer-Verlag Berlin Heidelberg
Pages188-202
Number of pages15
ISBN (Print)3540307818, 9783540307815
DOIs
StatePublished - 2005
Event15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002 - College Park, MD, United States
Duration: Jul 25 2002Jul 27 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2481 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002
CountryUnited States
CityCollege Park, MD
Period7/25/027/27/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel reductions: An application of adaptive algorithm selection'. Together they form a unique fingerprint.

  • Cite this

    Yu, H., Dang, F., & Rauchwerger, L. (2005). Parallel reductions: An application of adaptive algorithm selection. In Languages and Compilers for Parallel Computing - 15th Workshop, LCPC 2002, Revised Papers (pp. 188-202). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2481 LNCS). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/11596110_13