TY - GEN
T1 - Slicing Analysis and Indirect Accesses to Distributed Arrays
AU - Das, Raja
AU - Saltz, Joel
AU - von Hanxleden, Reinhard
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1994.
PY - 1994
Y1 - 1994
N2 - An increasing fraction of the applications targeted by parallel computers makes heavy use of indirection arrays for indexing data arrays. Such irregular access patterns make it difficult for a compiler to generate efficient parallel code. Previously developed techniques addressing this problem are limited in that they are only applicable for a single level of indirection. However, many codes using sparse data structures access their data through multiple levels of indirection. This paper presents a method for transforming programs using multiple levels of indirection into programs with at most one level of indirection, thereby broadening the range of applications that a compiler can parallelize efficiently. A central concept of our algorithm is to perform program slicing on the subscript expressions of the indirect array accesses. Such slices peel off the levels of indirection, one by one, and create opportunities for aggregated data prefetching in between. A slice graph eliminates redundant preprocessing and gives an ordering in which to compute the slices. We present our work in the context of High Performance Fortran; an implementation in a Fortran D prototype compiler is in progress.
AB - An increasing fraction of the applications targeted by parallel computers makes heavy use of indirection arrays for indexing data arrays. Such irregular access patterns make it difficult for a compiler to generate efficient parallel code. Previously developed techniques addressing this problem are limited in that they are only applicable for a single level of indirection. However, many codes using sparse data structures access their data through multiple levels of indirection. This paper presents a method for transforming programs using multiple levels of indirection into programs with at most one level of indirection, thereby broadening the range of applications that a compiler can parallelize efficiently. A central concept of our algorithm is to perform program slicing on the subscript expressions of the indirect array accesses. Such slices peel off the levels of indirection, one by one, and create opportunities for aggregated data prefetching in between. A slice graph eliminates redundant preprocessing and gives an ordering in which to compute the slices. We present our work in the context of High Performance Fortran; an implementation in a Fortran D prototype compiler is in progress.
UR - https://www.scopus.com/pages/publications/105051523066
U2 - 10.1007/3-540-57659-2_9
DO - 10.1007/3-540-57659-2_9
M3 - Conference contribution
AN - SCOPUS:105051523066
SN - 9783540576594
T3 - Lecture Notes in Computer Science
SP - 152
EP - 168
BT - Languages and Compilers for Parallel Computing - 6th International Workshop, 1993
A2 - Banerjee, Utpal
A2 - Gelernter, David
A2 - Nicolau, Alex
A2 - Padua, David
PB - Springer Science and Business Media Deutschland GmbH
T2 - 6th Annual Workshop on Languages and Compilers for Parallel Computing, 1993
Y2 - 12 August 1993 through 14 August 1993
ER -