Engineering a high-performance GPU B-tree

Muhammad A. Awad, Saman Ashkiani, Rob Johnson, Martín Farach-Colton, John D. Owens

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

    Abstract

    We engineer a GPU implementation of a B-Tree that supports concurrent queries (point, range, and successor) and updates (insertions and deletions). Our B-tree outperforms the state of the art, a GPU log-structured merge tree (LSM) and a GPU sorted array. In particular, point and range queries are significantly faster than in a GPU LSM (the GPU LSM does not implement successor queries). Furthermore, B-Tree insertions are also faster than LSM and sorted array insertions unless insertions come in batches of more than roughly 100k. Because we cache the upper levels of the tree, we achieve lookup throughput that exceeds the DRAM bandwidth of the GPU. We demonstrate that the key limiter of performance on a GPU is contention and describe the design choices that allow us to achieve this high performance.

    Original languageEnglish (US)
    Title of host publicationPPoPP 2019 - Proceedings of the 24th Principles and Practice of Parallel Programming
    PublisherAssociation for Computing Machinery
    Pages145-157
    Number of pages13
    ISBN (Electronic)9781450362252
    DOIs
    StatePublished - Feb 16 2019
    Event24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019 - Washington, United States
    Duration: Feb 16 2019Feb 20 2019

    Publication series

    NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP

    Conference

    Conference24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019
    Country/TerritoryUnited States
    CityWashington
    Period2/16/192/20/19

    Keywords

    • B-tree
    • Data structures
    • Dynamic
    • GPU
    • Mutable

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'Engineering a high-performance GPU B-tree'. Together they form a unique fingerprint.

    Cite this