A framework for adaptive algorithm selection in STAPL Conference Paper uri icon

abstract

  • 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. Copyright 2005 ACM.

name of conference

  • the tenth ACM SIGPLAN symposium

published proceedings

  • Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP '05

author list (cited authors)

  • Thomas, N., Tanase, G., Tkachyshyn, O., Perdue, J., Amato, N. M., & Rauchwerger, L

citation count

  • 85

complete list of authors

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

editor list (cited editors)

  • Pingali, K., Yelick, K. A., & Grimshaw, A. S.

publication date

  • January 2005