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

Venue: Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)
DOI: 10.1145/1065944.1065981
Link to Publication

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. 

@inproceedings{Thomas-affaas-2005, 
 address = {New York, NY, USA}, 
 author = {Thomas, Nathan and Tanase, Gabriel and Tkachyshyn, Olga and Perdue, Jack and Amato, Nancy M. and Rauchwerger, Lawrence}, 
 booktitle = {Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, 
 doi = {10.1145/1065944.1065981}, 
 isbn = {1595930809}, 
 keywords = {machine learning, parallel algorithms, matrix multiplication, sorting, adaptive algorithms}, 
 location = {Chicago, IL, USA}, 
 numpages = {12}, 
 pages = {277–288}, 
 publisher = {Association for Computing Machinery}, 
 series = {PPoPP \'05}, 
 title = {A Framework for Adaptive Algorithm Selection in STAPL}, 
 url = {https://doi.org/10.1145/1065944.1065981}, 
 year = {2005} 
}