A Hybrid Approach to Proving Memory Reference Monotonicity
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
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
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
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
Y2 - 8 September 2011 through 10 September 2011
ER -
ID: 44909206