A hybrid approach to proving memory reference monotonicity

Cosmin E. Oancea, Lawrence Rauchwerger

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

Abstract

Array references indexed by non-linear expressions or subscript arrays represent a major obstacle to compiler analysis and to automatic parallelization. Most previous proposed solutions either enhance the static analysis repertoire to recognize more patterns, to infer array-value properties, and to refine the mathematical support, or apply expensive run time analysis of memory reference traces to disambiguate these accesses. This paper presents an automated solution based on static construction of access summaries, in which the reference non-linearity problem can be solved for a large number of reference patterns by extracting arbitrarily-shaped predicates that can (in)validate the reference monotonicity property and thus (dis)prove loop independence. Experiments on six benchmarks show that our general technique for dynamic validation of the monotonicity property can cover a large class of codes, incurs minimal run-time overhead and obtains good speedups.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 24th International Workshop, LCPC 2011, Revised Selected Papers
Pages61-75
Number of pages15
DOIs
StatePublished - 2013
Event24th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2011 - Fort Collins, CO, United States
Duration: Sep 8 2011Sep 10 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7146 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2011
CountryUnited States
CityFort Collins, CO
Period9/8/119/10/11

Keywords

  • access summary
  • autoparallelization
  • monotonicity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A hybrid approach to proving memory reference monotonicity'. Together they form a unique fingerprint.

  • Cite this

    Oancea, C. E., & Rauchwerger, L. (2013). A hybrid approach to proving memory reference monotonicity. In Languages and Compilers for Parallel Computing - 24th International Workshop, LCPC 2011, Revised Selected Papers (pp. 61-75). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7146 LNCS). https://doi.org/10.1007/978-3-642-36036-7_5