Non-affine extensions to polyhedral code generation

Anand Venkat, Manu Shantharam, Mary Hall, Michelle Mills Strout

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

38 Scopus citations

Abstract

This paper describes a loop transformation framework that extends a polyhedral representation of loop nests to rep- resent and transform computations with non-affine index arrays in loop bounds and subscripts via a new interface between compile-time and run-time abstractions. Polyhe- dra scanning code generation, which historically applies an affine mapping to the subscript expressions of the statements in a loop nest, is modified to apply non-affine mappings in- volving index arrays that are represented at compile time by uninterpreted functions; non-affne loop bounds involv- ing index arrays are also represented. When appropriate, an inspector is utilized to capture the non-affine subscript mappings, and a generalized loop coalescing transformation is introduced as a non-affine transformation to support non- Affine loop bounds. With this support, complex sequences of new and existing transformations can then be composed. We demonstrate the effectiveness of this framework by optimiz- ing sparse matrix vector multiplication operations target- ing GPUs for different matrix structures and parallelization strategies.This approach achieves performance that is com- parable to or greater than the hand-tuned CUSP library; for two of the implementations it achieves an average 1.14× im- provement over CUSP across a collection of sparse matrices, while the third performs on average within 8% of CUSP.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2014
PublisherAssociation for Computing Machinery
Pages185-195
Number of pages11
ISBN (Print)9781450326704
DOIs
StatePublished - 2014
Externally publishedYes
Event12th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2014 - Orlando, FL, United States
Duration: Feb 15 2014Feb 19 2014

Publication series

NameProceedings of the 12th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2014

Conference

Conference12th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2014
Country/TerritoryUnited States
CityOrlando, FL
Period2/15/142/19/14

Keywords

  • Code generation
  • Inspector/executor
  • Loop coalescing
  • Non-affine
  • Polyhedral model

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Non-affine extensions to polyhedral code generation'. Together they form a unique fingerprint.

Cite this