Scalable conditional induction variables (CIV) analysis

Cosmin Eugen Oancea; Lawrence Rauchwerger

doi:10.1109/CGO.2015.7054201

Scalable conditional induction variables (CIV) analysis

Cosmin Eugen Oancea, Lawrence Rauchwerger

Department of Computer Science

5 Citations (Scopus)

Abstract

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 Alter, 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.

Original language	English
Title of host publication	Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'15)
Number of pages	12
Publisher	IEEE Computer Society Press
Publication date	3 Mar 2015
Pages	213-224
ISBN (Electronic)	978-1-4799-8161-8
DOIs	https://doi.org/10.1109/CGO.2015.7054201
Publication status	Published - 3 Mar 2015
Event	13th Annual IEEE/ACM International Symposium on Code Generation and Optimization - San Fransisco, United States Duration: 7 Feb 2015 → 11 Feb 2015 Conference number: 13

Conference

Conference	13th Annual IEEE/ACM International Symposium on Code Generation and Optimization
Number	13
Country/Territory	United States
City	San Fransisco
Period	07/02/2015 → 11/02/2015

Access to Document

10.1109/CGO.2015.7054201

Cite this

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. p. 213-224.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Oancea, CE & Rauchwerger, L 2015, Scalable conditional induction variables (CIV) analysis. in Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'15). IEEE Computer Society Press, pp. 213-224, 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, San Fransisco, United States, 07/02/2015. https://doi.org/10.1109/CGO.2015.7054201

@inproceedings{0c074bbe96a941a2ac14906afc23ee06,

title = "Scalable conditional induction variables (CIV) analysis",

abstract = "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 Alter, 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.",

author = "Oancea, {Cosmin Eugen} and Lawrence Rauchwerger",

year = "2015",

month = mar,

day = "3",

doi = "10.1109/CGO.2015.7054201",

language = "English",

pages = "213--224",

booktitle = "Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO'15)",

publisher = "IEEE Computer Society Press",

note = "13th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO '15 ; Conference date: 07-02-2015 Through 11-02-2015",

}

TY - GEN

T1 - Scalable conditional induction variables (CIV) analysis

AU - Oancea, Cosmin Eugen

AU - Rauchwerger, Lawrence

N1 - Conference code: 13

PY - 2015/3/3

Y1 - 2015/3/3

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 Alter, 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 Alter, 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 -