TY - GEN
T1 - KNN-joins using a hybrid approach
T2 - 12th Annual Workshop on General Purpose Processing using Graphics Processing Unit, GPGPU 2019
AU - Gowanlock, Michael
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/4/13
Y1 - 2019/4/13
N2 - K Nearest Neighbor (KNN) joins are used in many scientific domains for data analysis, and are building blocks of several well-known algorithms. KNN-joins find the KNN of all points in a dataset. However, KNN searches are computationally expensive, and many GPU KNN algorithms focus on the high-dimensional case that plainly gives a performance advantage to the GPU rather than the CPU. Consequently, in this work, we focus on a hybrid CPU/GPU approach for the low-dimensional KNN-join problem. In particular, we utilize a work queue that prioritizes computing data points in high density regions on the GPU, and low density regions on the CPU, thereby taking advantage of each architecture's relative strengths. Our approach, HybridKNN-Join, is shown to effectively augment a state-of-the-art multi-core CPU algorithm. We propose optimizations that (i) maximize GPU query throughput by assigning the GPU larger batches ofwork than the CPU; (ii) increaseworkload granularity to optimize GPU resource utilization; and, (iii) limit load imbalance between CPU and GPU architectures. Furthermore, the work queue utilized in our approach shows promise for the general purpose division of work for other hybrid CPU/GPU algorithms.
AB - K Nearest Neighbor (KNN) joins are used in many scientific domains for data analysis, and are building blocks of several well-known algorithms. KNN-joins find the KNN of all points in a dataset. However, KNN searches are computationally expensive, and many GPU KNN algorithms focus on the high-dimensional case that plainly gives a performance advantage to the GPU rather than the CPU. Consequently, in this work, we focus on a hybrid CPU/GPU approach for the low-dimensional KNN-join problem. In particular, we utilize a work queue that prioritizes computing data points in high density regions on the GPU, and low density regions on the CPU, thereby taking advantage of each architecture's relative strengths. Our approach, HybridKNN-Join, is shown to effectively augment a state-of-the-art multi-core CPU algorithm. We propose optimizations that (i) maximize GPU query throughput by assigning the GPU larger batches ofwork than the CPU; (ii) increaseworkload granularity to optimize GPU resource utilization; and, (iii) limit load imbalance between CPU and GPU architectures. Furthermore, the work queue utilized in our approach shows promise for the general purpose division of work for other hybrid CPU/GPU algorithms.
KW - Heterogeneous Systems
KW - In-memory Database
KW - Nearest Neighbor Search
KW - Query Optimization
UR - http://www.scopus.com/inward/record.url?scp=85064740441&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064740441&partnerID=8YFLogxK
U2 - 10.1145/3300053.3319417
DO - 10.1145/3300053.3319417
M3 - Conference contribution
AN - SCOPUS:85064740441
T3 - 12th Workshop on General Purpose Processing using GPUs, GPGPU 2019 - Proceedings
SP - 33
EP - 42
BT - 12th Workshop on General Purpose Processing using GPUs, GPGPU 2019 - Proceedings
PB - Association for Computing Machinery, Inc
Y2 - 13 April 2019
ER -