Expanding Opportunities for Array Privatization in Sparse Computations

Mahdi Soltan Mohammadi, Mary Hall, Michelle Mills Strout

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

Abstract

Sparse computation, where sparse formats are used to compress nonzero values of big data, are commonly used in real world applications. However, the compiler-based data dependence analysis of sparse computations needed for automatic parallelization is difficult due to usage of indirect memory accesses through index arrays, e.g. col in val[col[j]], in these computations. One use of such data dependence analysis is to find opportunities for array privatization, which is an approach to increase available parallelism in a loop by providing each parallel thread its own copy of arrays where in each iteration the array reads are dominated by array writes in the same iteration. In this paper, we expand opportunities for compile-time array privatization in sparse computations by using newly formulated index array properties and a novel concept we call content-based privatization. Furthermore, we discuss existing opportunities to use our approach for detecting private arrays in existing library implementations of sparse computations.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 33rd International Workshop, LCPC 2020
EditorsBarbara Chapman, José Moreira
PublisherSpringer Science and Business Media Deutschland GmbH
Pages29-37
Number of pages9
ISBN (Print)9783030959524
DOIs
StatePublished - 2022
Event33rd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2020 - Virtual, Online
Duration: Oct 14 2020Oct 16 2020

Publication series

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

Conference

Conference33rd International Workshop on Languages and Compilers for Parallel Computing, LCPC 2020
CityVirtual, Online
Period10/14/2010/16/20

Keywords

  • Dependence analysis
  • First private arrays
  • Privatization
  • Sparse computation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Expanding Opportunities for Array Privatization in Sparse Computations'. Together they form a unique fingerprint.

Cite this