Adaptive reduction parallelization techniques

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
Number of pages12
StatePublished - 2000
Externally publishedYes
Event2000 International Conference on Supercomputing - Santa Fe, NM, USA
Duration: May 8 2000May 11 2000


Conference2000 International Conference on Supercomputing
CitySanta Fe, NM, USA

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Adaptive reduction parallelization techniques'. Together they form a unique fingerprint.

Cite this