Extending index-array properties for data dependence analysis

Mahdi Soltan Mohammadi, Kazem Cheshmi, Maryam Mehri Dehnavi, Anand Venkat, Tomofumi Yuki, Michelle Mills Strout

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

8 Scopus citations

Abstract

Automatic parallelization is an approach where a compiler analyzes serial code and identifies computations that can be rewritten to leverage parallelism. Many data dependence analysis techniques have been developed to determine which loops in a code can be parallelized. With code that includes indirect array accesses through what are commonly called index arrays, such data dependence analysis is restricted in the conclusions that can be drawn at compile time. Various approaches that use index array properties such as monotonicity have been shown to more effectively find parallel loops. In this paper, we extend the kinds of properties about index arrays that can be expressed, show how to convert loop-carried data dependence relations and relevant index-array properties to constraints that can be provided to the Z3 SMT solver, and evaluate the impact of using such index-array properties on identifying parallel loops in a set of numerical benchmarks.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 31st International Workshop, LCPC 2018, Revised Selected Papers
EditorsMary Hall, Hari Sundar
PublisherSpringer
Pages78-93
Number of pages16
ISBN (Print)9783030346263
DOIs
StatePublished - 2019
Event31st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2018 - Salt Lake City, United States
Duration: Oct 9 2018Oct 11 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11882 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference31st International Workshop on Languages and Compilers for Parallel Computing, LCPC 2018
Country/TerritoryUnited States
CitySalt Lake City
Period10/9/1810/11/18

Keywords

  • Automatic parallelization
  • Data dependence analysis
  • SMT solvers
  • Sparse matrices

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Extending index-array properties for data dependence analysis'. Together they form a unique fingerprint.

Cite this