Scalable conditional induction variables (CIV) analysis
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Scalable conditional induction variables (CIV) analysis. / Oancea, Cosmin Eugen; Rauchwerger, Lawrence.
Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'15). IEEE Computer Society Press, 2015. s. 213-224.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Scalable conditional induction variables (CIV) analysis
AU - Oancea, Cosmin Eugen
AU - Rauchwerger, Lawrence
N1 - Conference code: 13
PY - 2015
Y1 - 2015
N2 - Subscripts using induction variables that cannot be expressed as a formula in terms of the enclosing-loop indices appear in the low-level implementation of common programming abstractions such as filter, or stack operations and pose significant challenges to automatic parallelization. Because the complexity of such induction variables is often due to their conditional evaluation across the iteration space of loops we name them Conditional Induction Variables (CIV).This paper presents a flow-sensitive technique that summarizes both such CIV-based and affine subscripts to program level, using the same representation. Our technique requires no modifications of our dependence tests, which is agnostic to the original shape of the subscripts, and is more powerful than previously reported dependence tests that rely on the pairwise disambiguation of read-write references.We have implemented the CIV analysis in our parallelizing compiler and evaluated its impact on five Fortran benchmarks. We have found that that there are many important loops using CIV subscripts and that our analysis can lead to their scalable parallelization. This in turn has led to the parallelization of the benchmark programs they appear in.
AB - Subscripts using induction variables that cannot be expressed as a formula in terms of the enclosing-loop indices appear in the low-level implementation of common programming abstractions such as filter, or stack operations and pose significant challenges to automatic parallelization. Because the complexity of such induction variables is often due to their conditional evaluation across the iteration space of loops we name them Conditional Induction Variables (CIV).This paper presents a flow-sensitive technique that summarizes both such CIV-based and affine subscripts to program level, using the same representation. Our technique requires no modifications of our dependence tests, which is agnostic to the original shape of the subscripts, and is more powerful than previously reported dependence tests that rely on the pairwise disambiguation of read-write references.We have implemented the CIV analysis in our parallelizing compiler and evaluated its impact on five Fortran benchmarks. We have found that that there are many important loops using CIV subscripts and that our analysis can lead to their scalable parallelization. This in turn has led to the parallelization of the benchmark programs they appear in.
U2 - 10.1109/CGO.2015.7054201
DO - 10.1109/CGO.2015.7054201
M3 - Article in proceedings
SP - 213
EP - 224
BT - Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'15)
PB - IEEE Computer Society Press
T2 - 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization
Y2 - 7 February 2015 through 11 February 2015
ER -
ID: 164443797