KNN-joins using a hybrid approach: Exploiting CPU/GPU workload characteristics

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

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication12th Workshop on General Purpose Processing using GPUs, GPGPU 2019 - Proceedings
PublisherAssociation for Computing Machinery, Inc
Pages33-42
Number of pages10
ISBN (Electronic)9781450362559
DOIs
StatePublished - Apr 13 2019
Event12th Annual Workshop on General Purpose Processing using Graphics Processing Unit, GPGPU 2019 - Providence, United States
Duration: Apr 13 2019 → …

Publication series

Name12th Workshop on General Purpose Processing using GPUs, GPGPU 2019 - Proceedings

Conference

Conference12th Annual Workshop on General Purpose Processing using Graphics Processing Unit, GPGPU 2019
Country/TerritoryUnited States
CityProvidence
Period4/13/19 → …

Keywords

  • Heterogeneous Systems
  • In-memory Database
  • Nearest Neighbor Search
  • Query Optimization

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Hardware and Architecture
  • Software

Fingerprint

Dive into the research topics of 'KNN-joins using a hybrid approach: Exploiting CPU/GPU workload characteristics'. Together they form a unique fingerprint.

Cite this