A framework for adaptive algorithm selection in STAPL

Nathan Thomas, Gabriel Tanase, Olga Tkachyshyn, Jack Perdue, Nancy M. Amato, Lawrence Rauchwerger

Research output: Contribution to conferencePaperpeer-review


Writing portable programs that perform well on multiple platforms or for varying input sizes and types can be very difficult because performance is often sensitive to the system architecture, the run-time environment, and input data characteristics. This is even more challenging on parallel and distributed systems due to the wide variety of system architectures. One way to address this problem is to adaptively select the best parallel algorithm for the current input data and system from a set of functionally equivalent algorithmic options. Toward this goal, we have developed a general framework for adaptive algorithm selection for use in the Standard Template Adaptive Parallel Library (STAPL). Our framework uses machine learning techniques to analyze data collected by STAPL installation benchmarks and to determine tests that will select among algorithmic options at run-time. We apply a prototype implementation of our framework to two important parallel operations, sorting and matrix multiplication, on multiple platforms and show that the framework determines run-time tests that correctly select the best performing algorithm from among several competing algorithmic options in 86-100% of the cases studied, depending on the operation and the system.

Original languageEnglish (US)
Number of pages12
StatePublished - 2005
Externally publishedYes
Event2005 ACM SIGPLAN Symposium on Principles and Practise of Parallel Programming, PROPP 05 - Chicago, IL, United States
Duration: Jun 15 2005Jun 17 2005


Conference2005 ACM SIGPLAN Symposium on Principles and Practise of Parallel Programming, PROPP 05
Country/TerritoryUnited States
CityChicago, IL


  • Adaptive Algorithms
  • Machine Learning
  • Matrix Multiplication
  • Parallel Algorithms
  • Sorting

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'A framework for adaptive algorithm selection in STAPL'. Together they form a unique fingerprint.

Cite this