Triton Join Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects.pdf

Bigbig

106

16页

1次

2022-07-12

免费下载

Triton Join: Eiciently Scaling to a Large Join State

on GPUs with Fast Interconnects

Clemens Lutz

∗

clemens.lutz@tu-berlin.de

TU Berlin

Berlin, Germany

Sebastian Breß

†

sebastian.bress@snowake.com

Snowake

Berlin, Germany

Steen Zeuch

steen.zeuch@dfki.de

DFKI GmbH

Berlin, Germany

Tilmann Rabl

tilmann.rabl@hpi.de

HPI, University of Potsdam

Potsdam, Germany

Volker Markl

volker.markl@tu-berlin.de

DFKI GmbH, TU Berlin

Berlin, Germany

ABSTRACT

Database management systems are facing growing data volumes.

Previous research suggests that GPUs are well-equipped to quickly

process joins and similar stateful operators, as GPUs feature high-

bandwidth on-board memory. However, GPUs cannot scale joins

to large data volumes due to two limiting factors: (1) large state

does not t into the on-board memory, and (2) spilling state to main

memory is constrained by the interconnect bandwidth. Thus, CPUs

are often the better choice for scalable data processing.

In this paper, we propose a new join algorithm that scales to

large data volumes by taking advantage of fast interconnects. Fast

interconnects such as NVLink 2.0 are a new technology that connect

the GPU to main memory at a high bandwidth, and thus enable

us to design our join to eciently spill its state. Our evaluation

shows that our Triton join outperforms a no-partitioning hash join

by more than 100

on the same GPU, and a radix-partitioned join

on the CPU by up to 2

. As a result, GPU-enabled DBMSs are

able to scale beyond the GPU memory capacity.

CCS CONCEPTS

• Information systems

→

Database management system en-

gines; Join algorithms.

KEYWORDS

Modern hardware, GPU, data transfer bottleneck, out-of-core, TLB

ACM Reference Format:

Clemens Lutz, Sebastian Breß, Steen Zeuch, Tilmann Rabl, and Volker

Markl. 2022. Triton Join: Eciently Scaling to a Large Join State on GPUs

with Fast Interconnects. In Proceedings of the 2022 International Conference on

Management of Data (SIGMOD ’22), June 12–17, 2022, P hiladelphia, PA, USA.

ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/3514221.3517911

∗

Research partially conducted while the author was employed by DFKI GmbH.

†

Work done while the author was employed by TU Berlin.

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than the

author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or

republish, to post on servers or to redistribute to lists, requires prior specic permission

and/or a fee. Request permissions from permissions@acm.org.

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

ACM ISBN 978-1-4503-9249-5/22/06.. . $15.00

https://doi.org/10.1145/3514221.3517911

GPU TLB

GPU

Memory

CPU > GPU

GPU > CPU

Our contribution

0.00

0.75

1.50

2.25

0 512 1024 1536 2048

Build & Probe Relation Size (Million Tuples / Relation)

Throughput (G Tuples/s)

CPU Radix Join GPU No-Partitioning Join GPU Triton Join

Figure 1: Out-of-core state results in a performance cli and

a slow-down, despite using a fast interconnect. In contrast,

our Triton join gracefully scales to joins with a large state.

1 INTRODUCTION

GPUs are being commercially adopted to accelerate query process-

ing [

]. They are available from all major cloud vendors, including

Amazon EC2, Google Compute Engine, and Microsoft Azure, and

are being integrated into academic [

106

122

] and

commercial GPU-enabled database management systems [

121

These GPU-enabled DBMSs see the most benet for join and group-

by aggregation queries with an in-GPU state [

132

145

However, database research suggests that GPUs cannot eciently

scale to large, out-of-core state due to the data transfer bottle-

neck [39, 43, 119, 132, 145].

The data transfer bottleneck is caused by the low bandwidth and

high latency of the interconnect between the GPU and the CPU [

This hardware limitation leads to a narrow scope where DBMSs

benet from GPUs. However, as we illustrate in Figure 1, higher

interconnect bandwidth is necessary, but not sucient for high

scalability. Even if the GPU is given a faster interconnect, the CPU

outperforms the GPU when joining two large data sets. Therefore,

we identify three fundamental challenges that need to be addressed

to widen the applicability of GPUs:

Scalability. GPU joins store their state in GPU memory to in-

crease throughput [

105

132

]. Due to the limited capac-

ity of GPU memory, GPU joins cannot eciently scale to a large

state [

]. In contrast, CPUs [

139

] have two orders-of-mag-

nitude higher memory capacity than GPUs [

100

]. Thus, we

must adapt GPU joins to spill their state to CPU memory in order

to achieve scalability.

Session 14: Modern Hardware and In-memory DBMS

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1017

Robustness. Spilling the join state to CPU memory results in a

performance cli [

]. These sharp performance drops are dicult

to account for in query optimizers, because cardinality estimates can

be signicantly wrong [

]. Thus, GPU-enabled DBMSs must

gracefully scale to large data sizes for a consistent user experience.

Eciency. State-of-the-art approaches reduce interconnect trans-

fers by shifting computations from the GPU to the CPU [

113

134

140

]. However, both interconnect bandwidth and CPU

cycles are scarce resources. DBMSs should use the GPU to ooad

computations from the CPU, while maximizing performance.

A newly emerging technology, fast GPU interconnects, has the

potential to help us address the above challenges. Fast interconnects

provide GPUs with high-bandwidth, cache-coherent access to main

memory. Recent examples include NVLink 2.0 [

] and 4.0 [

Innity Fabric [6], and Compute Express Link 2.0 [31].

In this work, we investigate how fast interconnects can improve

GPU join throughput. Our goal is to enable GPUs to process joins

with a state that exceeds the GPU memory capacity. Thus, we

consider joins smaller and larger than the GPU memory. For large

joins, we partition data out-of-core in CPU memory using the fast

interconnect to achieve data locality during the join. In contrast,

small joins require us to cache all intermediate results in GPU

memory to avoid unnecessary data transfers. We combine the GPU-

based partitioning and the caching in our new,

ierarchical

ybrid

hash join algorithm:

≡ the Triton join.

Overall, our contributions are as follows:

(1)

We investigate the requirements of an out-of-core GPU join

in regard to fast interconnects, and identify hardware bottle-

necks that limit scalability (Section 3).

(2)

We propose a new GPU radix partitioning algorithm that

takes advantage of fast interconnects to achieve a high band-

width and scale to large data volumes (Section 4).

(3)

We present our new Triton join algorithm, a scalable radix-

partitioned GPU hash join that partitions data using the GPU

and caches partitioned data in GPU memory (Section 5).

The further structure of this paper is as follows. In Section 2,

we briey introduce modern GPU hardware and joins. Next, we

motivate our approach by revisiting out-of-core GPU joins in Sec-

tion 3. After that, we demonstrate our out-of-core radix partitioning

approach in Section 4, and then overcome these challenges with our

Triton join in Section 5. In Section 6, we show our evaluation and

discuss our insights. Finally, we review related work in Section 7

and conclude in Section 8.

2 BACKGROUND

In this section, we provide an overview of the hardware architecture

of a fast-interconnect system, and of hardware-sensitive joins.

2.1 GPUs and Fast Interconnects

Fast interconnects are able to connect a GPU and a CPU with high

bandwidth, a unied address space, and system-wide cache-coher-

ence [

104

]. As an example, we show the architecture of an

IBM AC922 system [

] with an IBM POWER9 CPU and an Nvidia

V100 GPU in Figure 2. Although we focus on NVLink 2.0, other

fast interconnects such as Compute Express Link [

], Innity Fab-

ric [6], and OpenCAPI [103] specify a similar system architecture.

Streaming

GPU

CPU

Core Core Core Core

Coalescing Unit

L1 Cache &

Scratchpad

TLB

SM SM SM SM

L2 Cache

L2 TLB

IOMMU

Memory

Controller

IOTLB

Page Table Walkers

NVLink Processing Unit

GPU Mem

CPU Mem

High-Speed Hub

NVLink 2.0

Memory

Controller

MMU

75 GB/s

Memory

GB/s

170

GB/s

900

Multiprocessor

Registers

Figure 2: Hardware architecture of a system with a fast inter-

connect. The electrical bandwidths are annotated.

Overview. The system consists of one or more multi-core CPUs

and discrete GPUs. Each GPU is attached to a CPU by NVLink 2.0,

and has at least 16 GiB of on-board memory with 900 GB/s of

bandwidth [

]. Each CPU comes with up to 4 TiB of memory

attached at 170 GB/s [139].

GPU Architecture. GPUs such as Nvidia “Volta” [

] and

AMD “Vega” [

] execute threads in parallel on up to 84 streaming

multiprocessors (SM). Each SM schedules threads in hardware [

and provides up to 65 thousand registers to hide memory latencies

of up to 2 µs [

]. Each SM consists of 32–128 cores, on which 32

threads are physically executed together as a warp [

101

]. GPU pro-

gramming languages abstract multiple warps as a thread block [

101

]. Warps coalesce (i.e., group) adjacent memory accesses into a

single memory transaction to improve memory transfer eciency [

] and to reduce the memory address translation request rate [

118

The GPU caches memory accesses in its L1 and L2 caches [27].

Address Translation. CPUs and GPUs share a single address

space [

]. A program’s virtual addresses are translated into physi-

cal addresses on a memory access [

]. Translations are cached in

a hierarchy of translation lookaside buers (TLBs) [

126

]. Although

GPU vendors do not publish details, it is widely accepted that

“Pascal” and newer GPUs have two TLB levels [

The L1 TLB is private to each SM, while multiple SMs share a

L2 TLB [

]. In addition, CPU memory accesses are translated

by an I/O memory management unit (IOMMU) [21, 22, 27, 57]. The

IOMMU is part of the CPU and contains an IOTLB and 12 par-

allel page table walkers [

]. On a IOTLB miss, the page

table walkers fetch a translation from a page table stored as a radix

tree in CPU memory [

]. GPUs are able to coalesce page ta-

ble walks [

110

111

], and thus the IOMMU returns up to 16

translations at a time [

]. Both the GPU and the IOMMU support

4 KiB, 64 KiB and 2 MiB pages [

], and the IOMMU also

supports 1 GiB pages [21, 56].

NVLink 2.0. The GPU connects to the CPU at 75 GB/s in both

directions, for a total of 150 GB/s [

]. The connection is mediated

by a high-speed hub on the GPU [

], and an NVLink processing

unit on the CPU [

]. These units send and receive packets con-

sisting of a 16-byte header and 1–256 bytes of payload [

Small payloads incur additional overhead. Small reads are padded

to a 32-byte payload [

]. Small writes require a 16-byte “byte en-

able” header extension [

], that species which payload bytes to

write [

103

]. The GPU SMs support packets up to 128 bytes (i.e.,

an L1 cacheline [

]), and direct memory access copy engines

handle packets up to 256 bytes [

]. We calculate that the maximum

eective bandwidth is 62–65.7 GiB/s per direction.

Session 14: Modern Hardware and In-memory DBMS

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1018

of 16

免费下载

sigmod2022 paper

关注

评论