A Hybrid Approach to Proving Memory Reference Monotonicity

Cosmin Eugen Oancea; Lawrence Rauchwerger

doi:10.1007/978-3-642-36036-7_5

A Hybrid Approach to Proving Memory Reference Monotonicity

Cosmin Eugen Oancea, Lawrence Rauchwerger

9 Citations (Scopus)

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 language	English
Title of host publication	Languages and Compilers for Parallel Computing : 24th InternationalWorkshop, LCPC 2011 Fort Collins, CO, USA, September 8-10, 2011 Revised Selected Papers
Editors	Sanjay Rajopadhye, Michelle Mills Strout
Number of pages	15
Publisher	Springer
Publication date	2013
Pages	61-75
ISBN (Print)	978-3-642-36035-0
ISBN (Electronic)	978-3-642-36036-7
DOIs	https://doi.org/10.1007/978-3-642-36036-7_5
Publication status	Published - 2013
Externally published	Yes
Event	24th International Workshop, LCPC 2011 - Fort Collins, CO, United States Duration: 8 Sept 2011 → 10 Sept 2011 Conference number: 24

Workshop

Workshop	24th International Workshop, LCPC 2011
Number	24
Country/Territory	United States
City	Fort Collins, CO
Period	08/09/2011 → 10/09/2011

Access to Document

10.1007/978-3-642-36036-7_5

A Hybrid Approach to Proving Memory Reference MonotonicityAccepted author manuscript, 471 KB

Cite this

A Hybrid Approach to Proving Memory Reference Monotonicity. / Oancea, Cosmin Eugen; Rauchwerger, Lawrence.

Languages and Compilers for Parallel Computing: 24th InternationalWorkshop, LCPC 2011 Fort Collins, CO, USA, September 8-10, 2011 Revised Selected Papers. ed. / Sanjay Rajopadhye; Michelle Mills Strout. Springer, 2013. p. 61-75 .

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Oancea, CE & Rauchwerger, L 2013, A Hybrid Approach to Proving Memory Reference Monotonicity. in S Rajopadhye & MM Strout (eds), Languages and Compilers for Parallel Computing: 24th InternationalWorkshop, LCPC 2011 Fort Collins, CO, USA, September 8-10, 2011 Revised Selected Papers. Springer, pp. 61-75 , 24th International Workshop, LCPC 2011, Fort Collins, CO, United States, 08/09/2011. https://doi.org/10.1007/978-3-642-36036-7_5

@inproceedings{09b12fff0a304c0e82ed7af16ae11e85,

title = "A Hybrid Approach to Proving Memory Reference Monotonicity",

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.",

author = "Oancea, {Cosmin Eugen} and Lawrence Rauchwerger",

note = "@INPROCEEDINGS{OanceaMon, author = {Cosmin E. Oancea and Lawrence Rauchwerger}, title = {A {H}ybrid {A}pproach to {P}roving {M}emory {R}eference {M}onotonicity}, booktitle = {Procs. Int. Lang. Comp. Par. Comp. (LCPC)}, year = {2011} } ; 24th International Workshop, LCPC 2011 ; Conference date: 08-09-2011 Through 10-09-2011",

year = "2013",

doi = "10.1007/978-3-642-36036-7_5",

language = "English",

isbn = "978-3-642-36035-0",

pages = "61--75 ",

editor = "Sanjay Rajopadhye and Strout, {Michelle Mills}",

booktitle = "Languages and Compilers for Parallel Computing",

publisher = "Springer",

}

TY - GEN

T1 - A Hybrid Approach to Proving Memory Reference Monotonicity

AU - Oancea, Cosmin Eugen

AU - Rauchwerger, Lawrence

N1 - Conference code: 24

PY - 2013

Y1 - 2013

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

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

U2 - 10.1007/978-3-642-36036-7_5

DO - 10.1007/978-3-642-36036-7_5

M3 - Article in proceedings

SN - 978-3-642-36035-0

SP - 61

EP - 75

BT - Languages and Compilers for Parallel Computing

A2 - Rajopadhye, Sanjay

A2 - Strout, Michelle Mills

PB - Springer

T2 - 24th International Workshop, LCPC 2011

Y2 - 8 September 2011 through 10 September 2011

ER -

A Hybrid Approach to Proving Memory Reference Monotonicity

Abstract

Workshop

Access to Document

Fingerprint

Cite this