Accelerating the unacceleratable: Hybrid CPU/GPU algorithms for memory-bound database primitives

Michael Gowanlock, Ben Karsin, Zane Fink, Jordan Wright

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

3 Scopus citations

Abstract

Many database operations have a low compute to memory access ratio. In heterogeneous systems, where a graphics processing unit (GPU) is interconnected via PCIe, the data transfer bottleneck is perceived as insurmountable to achieving performance gains on these memory-bound database primitives. On the other hand, several compute-bound database operations have been shown to achieve significant performance gains using the GPU. This leads to CPU-only memory-bound applications having an increasingly non-negligible impact on database query throughput. In this paper we examine several of these overlooked algorithms, including (i) batched predecessor searches; (ii) multiway merging; and, (iii) partitioning. We examine the performance of parallel CPU-only, GPU-only, and hybrid CPU/GPU approaches, and show that hybrid algorithms achieve respectable performance gains. We develop a model that considers main memory accesses and PCIe data transfers, which are two major bottlenecks for hybrid CPU/GPU algorithms. The model lets us analytically determine how to distribute work between the CPU and GPU to maximize resource utilization while minimizing load imbalance. We show that our model can accurately predict the fraction of work to be sent to each architecture, and consequently, confirms that these overlooked database primitives can be accelerated despite their memory-bound nature.

Original languageEnglish (US)
Title of host publication15th International Workshop on Data Management on New Hardware, DaMoN 2019
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450368018
DOIs
StatePublished - Jul 1 2019
Event15th International Workshop on Data Management on New Hardware, DaMoN 2019, Held with ACM SIGMOD/PODS 2019 - Amsterdam, Netherlands
Duration: Jul 1 2019 → …

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Conference

Conference15th International Workshop on Data Management on New Hardware, DaMoN 2019, Held with ACM SIGMOD/PODS 2019
Country/TerritoryNetherlands
CityAmsterdam
Period7/1/19 → …

Keywords

  • GPGPU
  • Heterogeneous systems
  • Hybrid algorithms
  • In-memory database
  • Memory-bound algorithms

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Accelerating the unacceleratable: Hybrid CPU/GPU algorithms for memory-bound database primitives'. Together they form a unique fingerprint.

Cite this