TY - GEN
T1 - Extending index-array properties for data dependence analysis
AU - Mohammadi, Mahdi Soltan
AU - Cheshmi, Kazem
AU - Dehnavi, Maryam Mehri
AU - Venkat, Anand
AU - Yuki, Tomofumi
AU - Strout, Michelle Mills
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Automatic parallelization is an approach where a compiler analyzes serial code and identifies computations that can be rewritten to leverage parallelism. Many data dependence analysis techniques have been developed to determine which loops in a code can be parallelized. With code that includes indirect array accesses through what are commonly called index arrays, such data dependence analysis is restricted in the conclusions that can be drawn at compile time. Various approaches that use index array properties such as monotonicity have been shown to more effectively find parallel loops. In this paper, we extend the kinds of properties about index arrays that can be expressed, show how to convert loop-carried data dependence relations and relevant index-array properties to constraints that can be provided to the Z3 SMT solver, and evaluate the impact of using such index-array properties on identifying parallel loops in a set of numerical benchmarks.
AB - Automatic parallelization is an approach where a compiler analyzes serial code and identifies computations that can be rewritten to leverage parallelism. Many data dependence analysis techniques have been developed to determine which loops in a code can be parallelized. With code that includes indirect array accesses through what are commonly called index arrays, such data dependence analysis is restricted in the conclusions that can be drawn at compile time. Various approaches that use index array properties such as monotonicity have been shown to more effectively find parallel loops. In this paper, we extend the kinds of properties about index arrays that can be expressed, show how to convert loop-carried data dependence relations and relevant index-array properties to constraints that can be provided to the Z3 SMT solver, and evaluate the impact of using such index-array properties on identifying parallel loops in a set of numerical benchmarks.
KW - Automatic parallelization
KW - Data dependence analysis
KW - SMT solvers
KW - Sparse matrices
UR - http://www.scopus.com/inward/record.url?scp=85076324852&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076324852&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34627-0_7
DO - 10.1007/978-3-030-34627-0_7
M3 - Conference contribution
AN - SCOPUS:85076324852
SN - 9783030346263
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 78
EP - 93
BT - Languages and Compilers for Parallel Computing - 31st International Workshop, LCPC 2018, Revised Selected Papers
A2 - Hall, Mary
A2 - Sundar, Hari
PB - Springer
T2 - 31st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2018
Y2 - 9 October 2018 through 11 October 2018
ER -