TY - GEN
T1 - A static heap analysis for shape and connectivity
T2 - 19th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2006
AU - Marron, Mark
AU - Kapur, Deepak
AU - Stefanovic, Darko
AU - Hermenegildo, Manuel
PY - 2007
Y1 - 2007
N2 - Modeling the evolution of the state of program memory during program execution is critical to many parallelization techniques. Current memory analysis techniques either provide very accurate information but run prohibitively slowly or produce very conservative results. An approach based on abstract interpretation is presented for analyzing programs at compile time, which can accurately determine many important program properties such as aliasing, logical data structures and shape. These properties are known to be critical for transforming a single threaded program into a version that can be run on multiple execution units in parallel. The analysis is shown to be of polynomial complexity in the size of the memory heap. Experimental results for benchmarks in the Jolden suite are given. These results show that in practice the analysis method is efficient and is capable of accurately determining shape information in programs that create and manipulate complex data structures.
AB - Modeling the evolution of the state of program memory during program execution is critical to many parallelization techniques. Current memory analysis techniques either provide very accurate information but run prohibitively slowly or produce very conservative results. An approach based on abstract interpretation is presented for analyzing programs at compile time, which can accurately determine many important program properties such as aliasing, logical data structures and shape. These properties are known to be critical for transforming a single threaded program into a version that can be run on multiple execution units in parallel. The analysis is shown to be of polynomial complexity in the size of the memory heap. Experimental results for benchmarks in the Jolden suite are given. These results show that in practice the analysis method is efficient and is capable of accurately determining shape information in programs that create and manipulate complex data structures.
UR - http://www.scopus.com/inward/record.url?scp=38149041997&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38149041997&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-72521-3_25
DO - 10.1007/978-3-540-72521-3_25
M3 - Conference contribution
AN - SCOPUS:38149041997
SN - 3540725202
SN - 9783540725206
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 345
EP - 363
BT - Languages and Compilers for Parallel Computing - 19th International Workshop, LCPC 2006, Revised Papers
Y2 - 2 November 2006 through 4 November 2006
ER -