GPU LSM: A dynamic dictionary data structure for the GPU

Saman Ashkiani; Shengren Li; Martin Farach-Colton; Nina Amenta; John D. Owens

doi:10.1109/IPDPS.2018.00053

GPU LSM: A dynamic dictionary data structure for the GPU

Saman Ashkiani, Shengren Li, Martin Farach-Colton, Nina Amenta, John D. Owens

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.

Original language	English (US)
Title of host publication	Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	430-440
Number of pages	11
ISBN (Print)	9781538643686
DOIs	https://doi.org/10.1109/IPDPS.2018.00053
State	Published - Aug 3 2018
Event	32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 - Vancouver, Canada Duration: May 21 2018 → May 25 2018

Publication series

Name	Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

Conference

Conference	32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018
Country/Territory	Canada
City	Vancouver
Period	5/21/18 → 5/25/18

Keywords

Batched update
Dynamic data structure
GPU
Log structured merge tree
Range query

ASJC Scopus subject areas

Artificial Intelligence
Computer Networks and Communications
Hardware and Architecture
Information Systems and Management

Access to Document

10.1109/IPDPS.2018.00053

Cite this

Ashkiani, S., Li, S., Farach-Colton, M., Amenta, N., & Owens, J. D. (2018). GPU LSM: A dynamic dictionary data structure for the GPU. In Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018 (pp. 430-440). Article 8425197 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2018.00053

GPU LSM: A dynamic dictionary data structure for the GPU. / Ashkiani, Saman; Li, Shengren; Farach-Colton, Martin et al.
Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 430-440 8425197 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ashkiani, S, Li, S, Farach-Colton, M, Amenta, N & Owens, JD 2018, GPU LSM: A dynamic dictionary data structure for the GPU. in Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018., 8425197, Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018, Institute of Electrical and Electronics Engineers Inc., pp. 430-440, 32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, Canada, 5/21/18. https://doi.org/10.1109/IPDPS.2018.00053

Ashkiani S, Li S, Farach-Colton M, Amenta N, Owens JD. GPU LSM: A dynamic dictionary data structure for the GPU. In Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 430-440. 8425197. (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018). doi: 10.1109/IPDPS.2018.00053

Ashkiani, Saman ; Li, Shengren ; Farach-Colton, Martin et al. / GPU LSM : A dynamic dictionary data structure for the GPU. Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 430-440 (Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018).

@inproceedings{0df29cf3c189498b8390f79ceb217476,

title = "GPU LSM: A dynamic dictionary data structure for the GPU",

abstract = "We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.",

keywords = "Batched update, Dynamic data structure, GPU, Log structured merge tree, Range query",

author = "Saman Ashkiani and Shengren Li and Martin Farach-Colton and Nina Amenta and Owens, {John D.}",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018 ; Conference date: 21-05-2018 Through 25-05-2018",

year = "2018",

month = aug,

day = "3",

doi = "10.1109/IPDPS.2018.00053",

language = "English (US)",

isbn = "9781538643686",

series = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "430--440",

booktitle = "Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018",

}

TY - GEN

T1 - GPU LSM

T2 - 32nd IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018

AU - Ashkiani, Saman

AU - Li, Shengren

AU - Farach-Colton, Martin

AU - Amenta, Nina

AU - Owens, John D.

PY - 2018/8/3

Y1 - 2018/8/3

N2 - We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.

AB - We develop a dynamic dictionary data structure for the GPU, supporting fast insertions and deletions, based on the Log Structured Merge tree (LSM). Our implementation on an NVIDIA K40c GPU has an average update (insertion or deletion) rate of 225 M elements/s, 13.5x faster than merging items into a sorted array. The GPU LSM supports the retrieval operations of lookup, count, and range query operations with an average rate of 75 M, 32 M and 23 M queries/s respectively. The trade-off for the dynamic updates is that the sorted array is almost twice as fast on retrievals. We believe that our GPU LSM is the first dynamic general-purpose dictionary data structure for the GPU.

KW - Batched update

KW - Dynamic data structure

KW - GPU

KW - Log structured merge tree

KW - Range query

UR - http://www.scopus.com/inward/record.url?scp=85052232891&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052232891&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2018.00053

DO - 10.1109/IPDPS.2018.00053

M3 - Conference contribution

AN - SCOPUS:85052232891

SN - 9781538643686

T3 - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

SP - 430

EP - 440

BT - Proceedings - 2018 IEEE 32nd International Parallel and Distributed Processing Symposium, IPDPS 2018

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 21 May 2018 through 25 May 2018

ER -

GPU LSM: A dynamic dictionary data structure for the GPU

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this