Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures

TY - GEN

T1 - Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures

AU - Bøgh, Kenneth Sejdenfaden

AU - Chester, Sean

AU - Sidlauskas, Darius

AU - Assent, Ira

PY - 2017/5/9

Y1 - 2017/5/9

N2 - Multicore CPUs and cheap co-processors such as GPUs create opportunities for vastly accelerating database queries. However, given the differences in their threading models, expected granularities of parallelism, and memory subsystems, effectively utilising all cores with all co-processors for an intensive query is very difficult. This paper introduces a novel templating methodology to create portable, yet architecture-aware, algorithms. We apply this methodology on the very compute-intensive task of calculating the skycube, a materialisation of exponentially many skyline query results, which finds applications in data exploration and multi-criteria decision making. We define three parallel templates, two that leverage insights from previous skycube research and a third that exploits a novel point-based paradigm to expose more data parallelism. An experimental study shows that, relative to the state-of-the-art that does not parallelise well due to its memory and cache requirements, our algorithms provide an order of magnitude improvement on either architecture and proportionately improve as more GPUs are added.

AB - Multicore CPUs and cheap co-processors such as GPUs create opportunities for vastly accelerating database queries. However, given the differences in their threading models, expected granularities of parallelism, and memory subsystems, effectively utilising all cores with all co-processors for an intensive query is very difficult. This paper introduces a novel templating methodology to create portable, yet architecture-aware, algorithms. We apply this methodology on the very compute-intensive task of calculating the skycube, a materialisation of exponentially many skyline query results, which finds applications in data exploration and multi-criteria decision making. We define three parallel templates, two that leverage insights from previous skycube research and a third that exploits a novel point-based paradigm to expose more data parallelism. An experimental study shows that, relative to the state-of-the-art that does not parallelise well due to its memory and cache requirements, our algorithms provide an order of magnitude improvement on either architecture and proportionately improve as more GPUs are added.

KW - GPU

KW - multicore

KW - parallel algorithms

KW - skyline

KW - skycube

KW - template methodology

U2 - 10.1145/3035918.3035962

DO - 10.1145/3035918.3035962

M3 - Article in proceedings

SN - 978-1-4503-4197-4

SP - 447

EP - 462

BT - SIGMOD 2017 - Proceedings of the 2017 ACM International Conference on Management of Data

PB - Association for Computing Machinery

CY - ACM New York, NY, USA

T2 - ACM International Conference on Management of Data

Y2 - 14 May 2017 through 19 May 2017

ER -