Load imbalance mitigation optimizations for GPU-accelerated similarity joins

Benoit Gallet, Michael Gowanlock

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

5 Scopus citations

Abstract

The distance similarity self-join is widely used in database applications and is defined as joining a table on itself using a distance predicate. The similarity self-join is often used in spatial applications and is a building block of other algorithms, such as those used for data analysis. In this paper, we propose several new optimizations mitigating load imbalance of a GPU-accelerated self-join algorithm. The data-dependent nature of the self-join makes the algorithm potentially unsuitable for the GPU's architecture, due to variance in workloads assigned to threads. Consequently, we propose a method that reduces load imbalance and subsequent thread divergence between threads executing in a warp by considering the total workload assigned to each thread, and forcing the GPU's hardware scheduler to group threads with similar workloads within the same warp. Also, by leveraging a grid-based index, we propose a new balanced computational pattern for both reducing the number of distance calculations and the workload variance between threads. Moreover, we exploit additional parallelism by increasing the workload granularity to further improve computational throughput and workload balance within warps. Our solution achieves a speedup of up to 9.7x and 1.6x on average against another GPU algorithm, and up to 10.7x with an average of 2.5x against a CPU state-of-the-art parallel algorithm.

Original languageEnglish (US)
Title of host publicationProceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages396-405
Number of pages10
ISBN (Electronic)9781728135106
DOIs
StatePublished - May 2019
Event33rd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2019 - Rio de Janeiro, Brazil
Duration: May 20 2019May 24 2019

Publication series

NameProceedings - 2019 IEEE 33rd International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2019

Conference

Conference33rd IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2019
Country/TerritoryBrazil
CityRio de Janeiro
Period5/20/195/24/19

Keywords

  • GPGPU
  • Load balancing
  • Query Optimization
  • Range Query
  • Self-join

ASJC Scopus subject areas

  • Information Systems and Management
  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Load imbalance mitigation optimizations for GPU-accelerated similarity joins'. Together they form a unique fingerprint.

Cite this