The lrpd test: Speculative run-time parallelization of loops with privatization and reduction Parallelization

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

Abstract

Current parallelizing compilers cannot identify a significantfraction of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: Speculatively execute the loop as a do all, and apply a fully parallel data dependence test to determine if it had any cross-iteration dependence; if the test fails, then the loop is re-executed serially. Since, from our experience, a significant amount of the available parallelism in Fortran programs can be exploited by loops transformed through privatization and reductionparallelization, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution of this paper is a novel method for reduction recognition which goes beyond syntactic pattetm matching: It detects at run-time if the values stored in art array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow, We present experimental results on loops from the PERFECT Benchmarks which substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGPLAN 1995 Conference on Programming language Design and Implementation, PLDI 1995
PublisherAssociation for Computing Machinery
Pages218-232
Number of pages15
ISBN (Electronic)0897916972
DOIs
StatePublished - Jun 18 1995
Event1995 ACM SIGPLAN Conference on Programming language Design and Implementation, PLDI 1995 - San Diego, United States
Duration: Jun 18 1995Jun 21 1995

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
VolumePart F129371

Other

Other1995 ACM SIGPLAN Conference on Programming language Design and Implementation, PLDI 1995
CountryUnited States
CitySan Diego
Period6/18/956/21/95

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'The lrpd test: Speculative run-time parallelization of loops with privatization and reduction Parallelization'. Together they form a unique fingerprint.

  • Cite this

    Rauchwerger, L., & Padua, D. (1995). The lrpd test: Speculative run-time parallelization of loops with privatization and reduction Parallelization. In Proceedings of the ACM SIGPLAN 1995 Conference on Programming language Design and Implementation, PLDI 1995 (pp. 218-232). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI); Vol. Part F129371). Association for Computing Machinery. https://doi.org/10.1145/207110.207148