An Adaptive Algorithm Selection Framework**Research was performed at Texas A&M and supported in part by NSF CAREER Award CCR-9734471, NSF Grant ACI-9872126, NSF Grant EIA-0103742, NSF Grant ACI-0326350, NSF Grant ACI-0113971, DOE ASCI ASAP Level 2 Grant B347886 Conference Paper uri icon

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).

name of conference

  • Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004.

published proceedings

  • Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004.

author list (cited authors)

  • Yu, H., Zhang, D., & Rauchwerger, L.

citation count

  • 7

complete list of authors

  • Yu, Hao||Zhang, Dongmin||Rauchwerger, Lawrence

publication date

  • January 2004