Accelerating Nested Data Parallelism: Preserving Regularity

Lars van den Haak, Trevor L. McDonnel, Gabriele K. Keller, Ivo Gabe de Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    3 Downloads (Pure)

    Abstract

    Irregular nested data-parallelism is a powerful programming model which enables the expression of a large class of parallel algorithms. However, it is notoriously difficult to compile such programs to efficient code for modern parallel architectures. Regular data-parallelism, on the other hand, is much easier to compile to efficient code, but too restricted to express some problems conveniently or in a manner to exploit the full parallelism. We extend the regular data-parallel programming model to allow for the parallel execution of array-level conditionals and iterations over irregular nested structures, and present two novel static analyses to optimise the code generated for these programs which reduces the costs of this more powerful irregular model. We present benchmarks to support our claim that these extensions are effective as well as feasible, as they enable to exploit the full parallelism of an important class of algorithms, and together with our optimisations lead to an improvement in absolute performance over an implementation limited to exploiting only regular parallelism.
    Original languageEnglish
    Title of host publicationEuro-Par 2020
    Subtitle of host publicationParallel Processing - 26th International Conference on Parallel and Distributed Computing, Proceedings
    EditorsMaciej Malawski, Krzysztof Rzadca
    Place of PublicationCham
    PublisherSpringer
    Pages426-442
    Number of pages17
    ISBN (Electronic)978-3-030-57675-2
    ISBN (Print)978-3-030-57674-5
    DOIs
    Publication statusPublished - 18 Aug 2020

    Publication series

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

    Keywords

    • Arrays
    • GPGPU
    • Nested data parallelism
    • Parallel functional programming

    Fingerprint Dive into the research topics of 'Accelerating Nested Data Parallelism: Preserving Regularity'. Together they form a unique fingerprint.

    Cite this