SCIENCE@home

Automatic Hierarchical Parallelization of Linear Recurrences

Sepideh Maleki,Martin Burtscher

Published 2018 in International Conference on Architectural Support for Programming Languages and Operating Systems

ABSTRACT

Linear recurrences encompass many fundamental computations including prefix sums and digital filters. Later result values depend on earlier result values in recurrences, making it a challenge to compute them in parallel. We present a new work- and space-efficient algorithm to compute linear recurrences that is amenable to automatic parallelization and suitable for hierarchical massively-parallel architectures such as GPUs. We implemented our approach in a domain-specific code generator that emits optimized CUDA code. Our evaluation shows that, for standard prefix sums and single-stage IIR filters, the generated code reaches the throughput of memory copy for large inputs, which cannot be surpassed. On higher-order prefix sums, it performs nearly as well as the fastest handwritten code from the literature. On tuple-based prefix sums and digital filters, our automatically parallelized code outperforms the fastest prior implementations.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    International Conference on Architectural Support for Programming Languages and Operating Systems

  • Publication date

    2018-03-19

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.1145/3173162.3173168
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-21 of 21 references · Page 1 of 1

CITED BY

Showing 1-11 of 11 citing papers · Page 1 of 1