An adaptive algorithm selection framework

Hao Yu, Dongmin Zhang, Lawrence Rauchwerger

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

Abstract

Irregular and dynamic memory reference patterns can cause performance variations for low level algorithms in general and for parallel algorithms in particular. 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 present the dynamic selection of parallel reduction algorithms. First we introduce a set of high-level parameters that can characterize 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. Our experiments show that our framework: (a) selects the most appropriate algorithms in 85% of the cases studied, (b) overall delievers 98% of the optimal performance, (c) adoptively selects the best algorithms for dynamic phases of a running program (resulting in performance improvements otherwise not possible), and (d) adapts to the underlying machine architecture (tested on IBM Regatta and HP V-Class systems).

Original languageEnglish (US)
Title of host publicationProceedings - 13th International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
Pages278-289
Number of pages12
DOIs
StatePublished - Dec 27 2004
Externally publishedYes
EventProceedings - 13th International Conference on Parallel Architectures and Compilation Techniques (PACT 2004) - Antibes Juan-les-Pins, France
Duration: Sep 29 2004Oct 3 2004

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Conference

ConferenceProceedings - 13th International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
CountryFrance
CityAntibes Juan-les-Pins
Period9/29/0410/3/04

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'An adaptive algorithm selection framework'. Together they form a unique fingerprint.

  • Cite this

    Yu, H., Zhang, D., & Rauchwerger, L. (2004). An adaptive algorithm selection framework. In Proceedings - 13th International Conference on Parallel Architectures and Compilation Techniques (PACT 2004) (pp. 278-289). (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT). https://doi.org/10.1109/PACT.2004.1342561