CuART - a CUDA-based, scalable Radix-Tree lookup and update engine.

Martin Koppehel; Tobias Groth; Sven Groppe; Thilo Pionteck

doi:10.1145/3472456.3472511

CuART - a CUDA-based, scalable Radix-Tree lookup and update engine.

Martin Koppehel, Tobias Groth, Sven Groppe, Thilo Pionteck

Otto von Guericke University Magdeburg

5 Citations (Scopus)

Abstract

In this work we present an optimized version of the Adaptive Radix Tree (ART) index structure for GPUs. We analyze an existing GPU implementation of ART (GRT), identify bottlenecks and present an optimized data structure and layout to improve the lookup and update performance. We show that our implementation outperforms the existing approach by a factor up to 2 times for lookups and up to 10 times for updates using the same GPU. We also show that the sequential memory layout presented here is beneficial for lookup-intensive workloads on the CPU, outperforming the ART by up to 10 times. We analyze the impact of the memory architecture of the GPU, where it becomes visible that traditional GDDR6(X) is beneficial for the index lookups due to the faster clock rates compared to High Bandwidth Memory (HBM).

Original language	English
Pages	12:1-12:10
DOIs	https://doi.org/10.1145/3472456.3472511
Publication status	Published - 2021

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 4 Quality Education
SDG 9 Industry, Innovation, and Infrastructure
SDG 11 Sustainable Cities and Communities
SDG 12 Responsible Consumption and Production
SDG 14 Life Below Water
SDG 15 Life on Land

Research Areas and Centers

Centers: Center for Artificial Intelligence Luebeck (ZKIL)
Research Area: Intelligent Systems

DFG Research Classification Scheme

4.43-03 Security and Dependability, Operating, Communication and Distributed Systems
4.43-06 Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics

Access to Document

10.1145/3472456.3472511

https://dblp.org/rec/conf/icpp/KoppehelGGP21

Cite this

@conference{231b53c6bfa24a6086f9952218431cb0,

title = "CuART - a CUDA-based, scalable Radix-Tree lookup and update engine.",

abstract = "In this work we present an optimized version of the Adaptive Radix Tree (ART) index structure for GPUs. We analyze an existing GPU implementation of ART (GRT), identify bottlenecks and present an optimized data structure and layout to improve the lookup and update performance. We show that our implementation outperforms the existing approach by a factor up to 2 times for lookups and up to 10 times for updates using the same GPU. We also show that the sequential memory layout presented here is beneficial for lookup-intensive workloads on the CPU, outperforming the ART by up to 10 times. We analyze the impact of the memory architecture of the GPU, where it becomes visible that traditional GDDR6(X) is beneficial for the index lookups due to the faster clock rates compared to High Bandwidth Memory (HBM).",

author = "Martin Koppehel and Tobias Groth and Sven Groppe and Thilo Pionteck",

note = "DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2021",

doi = "10.1145/3472456.3472511",

language = "English",

pages = "12:1--12:10",

}

TY - CONF

T1 - CuART - a CUDA-based, scalable Radix-Tree lookup and update engine.

AU - Koppehel, Martin

AU - Groth, Tobias

AU - Groppe, Sven

AU - Pionteck, Thilo

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2021

Y1 - 2021

N2 - In this work we present an optimized version of the Adaptive Radix Tree (ART) index structure for GPUs. We analyze an existing GPU implementation of ART (GRT), identify bottlenecks and present an optimized data structure and layout to improve the lookup and update performance. We show that our implementation outperforms the existing approach by a factor up to 2 times for lookups and up to 10 times for updates using the same GPU. We also show that the sequential memory layout presented here is beneficial for lookup-intensive workloads on the CPU, outperforming the ART by up to 10 times. We analyze the impact of the memory architecture of the GPU, where it becomes visible that traditional GDDR6(X) is beneficial for the index lookups due to the faster clock rates compared to High Bandwidth Memory (HBM).

AB - In this work we present an optimized version of the Adaptive Radix Tree (ART) index structure for GPUs. We analyze an existing GPU implementation of ART (GRT), identify bottlenecks and present an optimized data structure and layout to improve the lookup and update performance. We show that our implementation outperforms the existing approach by a factor up to 2 times for lookups and up to 10 times for updates using the same GPU. We also show that the sequential memory layout presented here is beneficial for lookup-intensive workloads on the CPU, outperforming the ART by up to 10 times. We analyze the impact of the memory architecture of the GPU, where it becomes visible that traditional GDDR6(X) is beneficial for the index lookups due to the faster clock rates compared to High Bandwidth Memory (HBM).

U2 - 10.1145/3472456.3472511

DO - 10.1145/3472456.3472511

M3 - Conference Papers

SP - 12:1-12:10

ER -

CuART - a CUDA-based, scalable Radix-Tree lookup and update engine.

Abstract

UN SDGs

Research Areas and Centers

DFG Research Classification Scheme

Access to Document

Fingerprint

Cite this