Skip to main navigation Skip to search Skip to main content

Slicing Analysis and Indirect Accesses to Distributed Arrays

  • University of Maryland, College Park
  • Rice University

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

20 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationLanguages and Compilers for Parallel Computing - 6th International Workshop, 1993
EditorsUtpal Banerjee, David Gelernter, Alex Nicolau, David Padua
PublisherSpringer Science and Business Media Deutschland GmbH
Pages152-168
Number of pages17
ISBN (Print)9783540576594
DOIs
StatePublished - 1994
Event6th Annual Workshop on Languages and Compilers for Parallel Computing, 1993 - Portland, United States
Duration: Aug 12 1993 → Aug 14 1993

Publication series

NameLecture Notes in Computer Science
Volume768 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th Annual Workshop on Languages and Compilers for Parallel Computing, 1993
Country/TerritoryUnited States
CityPortland
Period08/12/93 → 08/14/93

Fingerprint

Dive into the research topics of 'Slicing Analysis and Indirect Accesses to Distributed Arrays'. Together they form a unique fingerprint.

Cite this