Adaptive reduction parallelization techniques Conference Paper uri icon


  • In this paper, we propose to adapt parallelizing transformations, more specifically, reduction parallelizations, to the actual reference pattern executed by a loop, i.e., to the particular input data and dynamic phase of a program. More precisely we will show how, after validating a reduction at run-time (when this is not possible at compile time) we can dynamically characterize its reference pattern and choose the most appropriate method for parallelizing it. For this purpose, we develop a library of parallel reduction algorithms, including both previously known and novel schemes, which includes algorithms specialized for different classes of access behavior. In particular, each algorithm in our library has identified strengths related to specific reference pattern characteristics, which are matched, at run-time, with measured characteristics of the actual reference pattern. The matching of algorithm to reference pattern is performed using a decision-tree based selection scheme. The contribution of this work consists in new optimizations for reduction parallelization and in the introduction of a new approach to the optimization of irregular applications: Characteristic based customization.

name of conference

  • the 14th international conference

published proceedings

  • Proceedings of the 14th international conference on Supercomputing - ICS '00

author list (cited authors)

  • Yu, H., & Rauchwerger, L

citation count

  • 51

complete list of authors

  • Yu, Hao||Rauchwerger, Lawrence

editor list (cited editors)

  • Reynders, J., & Veidenbaum, A. V.

publication date

  • January 2000