Clustering Throughput Optimization on the GPU

Michael Gowanlock, Cody M. Rude, David M. Blair, Justin D. Li, Victor Pankratius

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

10 Scopus citations

Abstract

Large datasets in astronomy and geoscience often require clustering and visualizations of phenomena at different densities and scales in order to generate scientific insight. We examine the problem of maximizing clustering throughput for concurrent dataset clustering in spatial dimensions. We introduce a novel hybrid approach that uses GPUs in conjunction with multicore CPUs for algorithmic throughput optimizations. The key idea is to exploit the fast memory on the GPU for index searches and optimize I/O transfers in such a way that the low-bandwidth host-GPU bottleneck does not have a significant negative performance impact. To achieve this, we derive two distinct GPU kernels that exploit grid-based indexing schemes to improve clustering performance. To obviate limited GPU memory and enable large dataset clustering, our method is complemented by an efficient batching scheme for transfers between the host and GPU accelerator. This scheme is robust with respect to both sparse and dense data distributions and intelligently avoids buffer overflows that would otherwise degrade performance, all while minimizing the number of data transfers between the host and GPU. We evaluate our approaches on ionospheric total electron content datasets as well as intermediate-redshift galaxies from the Sloan Digital Sky Survey. Our hybrid approach yields a speedup of up to 50x over the sequential implementation on one of the experimental scenarios, which is respectable for I/O intensive clustering.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages832-841
Number of pages10
ISBN (Electronic)9781538639146
DOIs
StatePublished - Jun 30 2017
Externally publishedYes
Event31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017 - Orlando, United States
Duration: May 29 2017Jun 2 2017

Publication series

NameProceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017

Conference

Conference31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017
Country/TerritoryUnited States
CityOrlando
Period5/29/176/2/17

Keywords

  • Computer-Aided Discovery.
  • DBSCAN
  • GPGPU
  • Parallel Clustering
  • Query Optimization

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Clustering Throughput Optimization on the GPU'. Together they form a unique fingerprint.

Cite this