Scalable conditional induction variables (CIV) analysis

Cosmin E. Oancea, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the 2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages213-224
Number of pages12
ISBN (Electronic)9781479981618
DOIs
StatePublished - Mar 3 2015
Externally publishedYes
Event2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015 - San Francisco, United States
Duration: Feb 7 2015Feb 11 2015

Publication series

NameProceedings of the 2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015

Other

Other2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015
CountryUnited States
CitySan Francisco
Period2/7/152/11/15

ASJC Scopus subject areas

  • Applied Mathematics
  • Control and Optimization
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Scalable conditional induction variables (CIV) analysis'. Together they form a unique fingerprint.

  • Cite this

    Oancea, C. E., & Rauchwerger, L. (2015). Scalable conditional induction variables (CIV) analysis. In Proceedings of the 2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015 (pp. 213-224). [7054201] (Proceedings of the 2015 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CGO.2015.7054201