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 Citationer (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.

Originalsprog	Engelsk
Titel	Languages and Compilers for Parallel Computing : 24th InternationalWorkshop, LCPC 2011 Fort Collins, CO, USA, September 8-10, 2011 Revised Selected Papers
Redaktører	Sanjay Rajopadhye, Michelle Mills Strout
Antal sider	15
Forlag	Springer
Publikationsdato	2013
Sider	61-75
ISBN (Trykt)	978-3-642-36035-0
ISBN (Elektronisk)	978-3-642-36036-7
DOI	https://doi.org/10.1007/978-3-642-36036-7_5
Status	Udgivet - 2013
Udgivet eksternt	Ja
Begivenhed	24th International Workshop, LCPC 2011 - Fort Collins, CO, USA Varighed: 8 sep. 2011 → 10 sep. 2011 Konferencens nummer: 24

Workshop

Workshop	24th International Workshop, LCPC 2011
Nummer	24
Land/Område	USA
By	Fort Collins, CO
Periode	08/09/2011 → 10/09/2011

Adgang til dokumentet

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

A Hybrid Approach to Proving Memory Reference MonotonicityAccepteret manuskript, 471 KB

Citationsformater

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. red. / Sanjay Rajopadhye; Michelle Mills Strout. Springer, 2013. s. 61-75 .

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Oancea, CE & Rauchwerger, L 2013, A Hybrid Approach to Proving Memory Reference Monotonicity. i S Rajopadhye & MM Strout (red), Languages and Compilers for Parallel Computing: 24th InternationalWorkshop, LCPC 2011 Fort Collins, CO, USA, September 8-10, 2011 Revised Selected Papers. Springer, s. 61-75 , 24th International Workshop, LCPC 2011, Fort Collins, CO, USA, 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

Adgang til dokumentet

Fingeraftryk

Citationsformater