TY - GEN
T1 - Identification of heap-carried data dependence via explicit store heap models
AU - Marron, Mark
AU - Stefanovic, Darko
AU - Kapur, Deepak
AU - Hermenegildo, Manuel
PY - 2008
Y1 - 2008
N2 - Dependence information between program values is extensively used in many program optimization techniques. The ability to identify statements, calls and loop iterations that do not depend on each other enables many transformations which increase the instruction and thread-level parallelism in a program. When program variables contain complex data structures including arrays, records, and recursive data structures, the ability to precisely model data dependence based on heap structure remains a challenging problem. This paper presents a technique for precisely tracking heap based data dependence in non-trivial Java programs via static analysis. Using an abstract interpretation framework, the approach extends a shape analysis technique based on an existing graph model of heaps, by integrating read/write history information and intelligent memoization. The method has been implemented and its effectiveness and utility are demonstrated by computing detailed dependence information for two benchmarks (Em3d and BH from the JOlden suite) and using this information to parallelize the benchmarks.
AB - Dependence information between program values is extensively used in many program optimization techniques. The ability to identify statements, calls and loop iterations that do not depend on each other enables many transformations which increase the instruction and thread-level parallelism in a program. When program variables contain complex data structures including arrays, records, and recursive data structures, the ability to precisely model data dependence based on heap structure remains a challenging problem. This paper presents a technique for precisely tracking heap based data dependence in non-trivial Java programs via static analysis. Using an abstract interpretation framework, the approach extends a shape analysis technique based on an existing graph model of heaps, by integrating read/write history information and intelligent memoization. The method has been implemented and its effectiveness and utility are demonstrated by computing detailed dependence information for two benchmarks (Em3d and BH from the JOlden suite) and using this information to parallelize the benchmarks.
UR - http://www.scopus.com/inward/record.url?scp=58449102721&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58449102721&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-89740-8_7
DO - 10.1007/978-3-540-89740-8_7
M3 - Conference contribution
AN - SCOPUS:58449102721
SN - 3540897399
SN - 9783540897392
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 94
EP - 108
BT - Languages and Compilers for Parallel Computing - 21st International Workshop, LCPC 2008, Revised Selected Papers
T2 - 21st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2008
Y2 - 31 July 2008 through 2 August 2008
ER -