TY - GEN
T1 - Expanding Opportunities for Array Privatization in Sparse Computations
AU - Mohammadi, Mahdi Soltan
AU - Hall, Mary
AU - Strout, Michelle Mills
N1 - Publisher Copyright:
© 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - Sparse computation, where sparse formats are used to compress nonzero values of big data, are commonly used in real world applications. However, the compiler-based data dependence analysis of sparse computations needed for automatic parallelization is difficult due to usage of indirect memory accesses through index arrays, e.g. col in val[col[j]], in these computations. One use of such data dependence analysis is to find opportunities for array privatization, which is an approach to increase available parallelism in a loop by providing each parallel thread its own copy of arrays where in each iteration the array reads are dominated by array writes in the same iteration. In this paper, we expand opportunities for compile-time array privatization in sparse computations by using newly formulated index array properties and a novel concept we call content-based privatization. Furthermore, we discuss existing opportunities to use our approach for detecting private arrays in existing library implementations of sparse computations.
AB - Sparse computation, where sparse formats are used to compress nonzero values of big data, are commonly used in real world applications. However, the compiler-based data dependence analysis of sparse computations needed for automatic parallelization is difficult due to usage of indirect memory accesses through index arrays, e.g. col in val[col[j]], in these computations. One use of such data dependence analysis is to find opportunities for array privatization, which is an approach to increase available parallelism in a loop by providing each parallel thread its own copy of arrays where in each iteration the array reads are dominated by array writes in the same iteration. In this paper, we expand opportunities for compile-time array privatization in sparse computations by using newly formulated index array properties and a novel concept we call content-based privatization. Furthermore, we discuss existing opportunities to use our approach for detecting private arrays in existing library implementations of sparse computations.
KW - Dependence analysis
KW - First private arrays
KW - Privatization
KW - Sparse computation
UR - http://www.scopus.com/inward/record.url?scp=85125328561&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85125328561&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-95953-1_3
DO - 10.1007/978-3-030-95953-1_3
M3 - Conference contribution
AN - SCOPUS:85125328561
SN - 9783030959524
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 29
EP - 37
BT - Languages and Compilers for Parallel Computing - 33rd International Workshop, LCPC 2020
A2 - Chapman, Barbara
A2 - Moreira, José
PB - Springer Science and Business Media Deutschland GmbH
T2 - 33rd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2020
Y2 - 14 October 2020 through 16 October 2020
ER -