Adaptive reduction parallelization techniques

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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

Original languageEnglish (US)
Title of host publicationICS 2014 - Proceedings of the 28th ACM InternationaI Conference on Supercomputing
EditorsUtpal Banerjee
PublisherAssociation for Computing Machinery
Pages311-322
Number of pages12
ISBN (Electronic)9781450328401
DOIs
StatePublished - Jun 10 2014
Externally publishedYes
Event25th ACM International Conference on Supercomputing, ICS 2014 - Munich, Germany
Duration: Jun 10 2014Jun 13 2014

Publication series

NameProceedings of the International Conference on Supercomputing

Other

Other25th ACM International Conference on Supercomputing, ICS 2014
CountryGermany
CityMunich
Period6/10/146/13/14

ASJC Scopus subject areas

  • Computer Science(all)

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

  • Cite this

    Yu, H., & Rauchwerger, L. (2014). Adaptive reduction parallelization techniques. In U. Banerjee (Ed.), ICS 2014 - Proceedings of the 28th ACM InternationaI Conference on Supercomputing (pp. 311-322). (Proceedings of the International Conference on Supercomputing). Association for Computing Machinery. https://doi.org/10.1145/2591635.2667180