A hybrid CPU/GPU approach for optimizing sorting throughput

Michael Gowanlock, Ben Karsin

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

The GPU is an effective architecture for sorting due to its massive parallelism and high memory bandwidth. However, for input datasets that exceed global memory capacity, the communication overhead between host (CPU) and GPU may degrade the overall performance of heterogeneous approaches. Thus, to achieve performance gains over multi-core parallel CPU algorithms, heterogeneous sorting using the GPU needs to obviate communication overheads. We provide a detailed overview of current host-GPU data transfer mechanisms and advance several methods of mitigating the associated performance bottlenecks. Using these methods, we develop a heterogeneous CPU/GPU sorting algorithm that effectively exploits the architecture. Furthermore, we demonstrate that, while out-of-place GPU sorting achieves the best performance, an in-place sort has the potential to further reduce some host-side bottlenecks, which encourages several future research priorities. Our approaches mitigate several bottlenecks, as demonstrated on single- and dual-GPU platforms, achieving speedups up to 3.47× over the parallel reference implementation on the CPU. We discuss future research for heterogeneous sorting in the multi-GPU NVLink era.

Original languageEnglish (US)
Pages (from-to)45-55
Number of pages11
JournalParallel Computing
Volume85
DOIs
StatePublished - Jul 2019
Externally publishedYes

Keywords

  • GPGPU
  • Heterogeneous architectures
  • Sorting

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A hybrid CPU/GPU approach for optimizing sorting throughput'. Together they form a unique fingerprint.

Cite this