Position-Dependent Arrays and Their Application for High Performance Code Generation

Federico Pizzuti, Michel Steuwer, Christophe Dubach

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

Abstract / Description of output

Modern parallel hardware promises unprecedented performance, for the gifted few experts who can program it correctly. Code generators from high-level languages provide an attractive alternative, promising to deliver high performance automatically. Existing projects such as Accelerate, Futhark, Halide, or Lift show that this approach is feasible. Unfortunately, existing efforts focus on computations over tensors: regularly shaped higher dimensional arrays. This limits the expressiveness of these approaches and excludes many interesting data structures that are commonly encoded manually in memory, such as trees or triangular matrices.

This paper presents an extended array type that lifts this restriction. For multidimensional arrays, the size of a nested array might depend on its position in the surrounding arrays, which enables the expression of computations over less regularly shaped data structures. However, these positiondependent arrays bring new challenges for high-performance code generation, as determining the position of the elements in memory becomes more challenging.

This paper shows how these challenges are addressed by extending the existing Lift type system and compiler. The experimental results show that this approach enables the efficient code generation of triangular matrix-vector multiplication, with performance improvements over cuBLAS on an Nvidia GPU by up to 2×. Furthermore, we show a use case for a low-level optimization for avoiding unnecessary out-ofbound checks in stencils, leading to up to 3× improvements over already optimized generated stencil codes.

Original languageEnglish
Title of host publicationFHPNC 2019: Proceedings of the 8th ACM SIGPLAN International Workshop on Functional High-Performance and Numerical Computing
PublisherACM Association for Computing Machinery
Number of pages13
ISBN (Print)9781450368148
Publication statusPublished - 18 Aug 2019
EventFHPNC 2019 Functional High-Performance and Numerical Computing
: ICFP 19 Berlin
- Berlin, Germany
Duration: 18 Aug 201918 Aug 2019


WorkshopFHPNC 2019 Functional High-Performance and Numerical Computing
Abbreviated titleFHPNC
Internet address

Keywords / Materials (for Non-textual outputs)

  • Irregular data structures
  • Dependent Types
  • LIFT


Dive into the research topics of 'Position-Dependent Arrays and Their Application for High Performance Code Generation'. Together they form a unique fingerprint.

Cite this