Tile-based Lightweight Integer Compression in GPU.pdf

Bigbig

226

14页

4次

2022-07-20

免费下载

Tile-based Lightweight Integer Compression in GPU

Anil Shanbhag

∗

Massachusetts Institute of

Technology

anil@csail.mit.edu

Bobbi W. Yogatama

∗

University of

Wisconsin-Madison

bwyogatama@cs.wisc.edu

Xiangyao Yu

University of

Wisconsin-Madison

yxy@cs.wisc.edu

Samuel Madden

Massachusetts Institute of

Technology

madden@csail.mit.edu

ABSTRACT

GPUs are increasingly used for high-performance and interactive

data analytics workloads due to their capability to accelerate com-

putation using massive parallelism. A key constraint of GPU-based

data analytics today is the limited memory capacity in GPU devices.

Data compression is a powerful technique that can mitigate the

capacity limitation in two ways: (1) tting more data into GPU

memory and (2) speeding up data transfer between CPU and GPU.

However, compression schemes for GPU today are still limited in

compression ratio and/or decompression speed. We identify two

limiting factors of existing approaches. First, existing decompres-

sion solutions require multiple passes of scanning the global mem-

ory to decode layers of compression schemes, incurring signicant

memory trac and hurting performance. We present the tile-based

decompression model to decompress encoded data in a single pass

over global memory and inline with query execution. Second, we

develop an ecient implementation of bit-packing-based compres-

sion schemes and their optimization techniques in the context of

GPU. Our evaluation shows that our schemes can achieve similar

compression rates to the best state-of-the-art compression schemes

in GPU (i.e., nvCOMP) while being 2.2× and 2.6× faster in decom-

pression speed and query running time.

CCS CONCEPTS

• Theory of computation → Data compression

;

• Computer

systems organization → Heterogeneous (hybrid) systems.

KEYWORDS

GPU data compression, GPU data analytics, bit-packing

ACM Reference Format:

Anil Shanbhag, Bobbi W. Yogatama, Xiangyao Yu, and Samuel Madden. 2022.

Tile-based Lightweight Integer Compression in GPU. In Proceedings of the

2022 International Conference on Management of Data (SIGMOD ’22), June

12–17, 2022, Philadelphia, PA, USA. ACM, New York, NY, USA, 14 pages.

https://doi.org/10.1145/3514221.3526132

1 INTRODUCTION

In the past decade, special-purpose graphics processing units

(GPUs) have evolved into general-purpose computing devices, with

general-purpose parallel programming models, such as CUDA [

]

∗

Both authors contributed equally (listed alphabetically)

This work is licensed under a Creative Commons

Attribution International 4.0 License.

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

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

https://doi.org/10.1145/3514221.3526132

and OpenCL [

]. Because of GPUs’ high compute power, they

have seen signicant adoption in deep learning and high perfor-

mance computing [

]. GPUs also have great potential to accelerate

memory-bound applications such as database systems, because

GPUs utilize High-Bandwidth Memory (HBM), a new class of RAM

that has signicantly higher bandwidth compared to traditional

DDR RAM used with CPUs. A single modern GPU can have up to

80 GB of HBM which is capable of delivering up to 2 TBps of mem-

ory bandwidth and 19.5 Tops of compute compared to 100GBps

of memory bandwidth and

1 Tops on a single CPU. This rise

in memory capacity, coupled with the ability to equip a modern

server with several GPUs (up to 20), means that it’s possible to have

hundreds of gigabytes of GPU memory on a modern server.

Several commercial systems, including Omnisci [

], Kinetica [

and BlazingDB [

], aim to provide real-time analytics capabilities

by using GPUs to store a large fraction (or all) of the working set.

A key constraint in these systems is the GPU memory capacity.

Currently, GPUs have at most 80 GB of memory which is used

both to cache the working set and as scratch memory for query

execution. Therefore, to accommodate working set larger than GPU

memory capacity, sharding between CPU and GPU or between

multiple GPUs is necessary [

]. However, this approach will

incur performance penalty due to slower communication across

PCIe. Data compression can play a critical role to address this issue

by achieving two goals: (1) Fit in more working set in a single

GPU memory and (2) Reduce the data transfer time across PCIe

by transferring the compressed data instead. Furthermore, data

compression is also applicable beyond the database eld as link

bandwidth is often the bottleneck in many applications that use

GPUs such as machine learning and image processing.

We identify two major limitations in GPU data compression

solutions today:

1) Cascading Decompression

GPU-based systems [

] have looked at frame-of-reference

(FOR) [

], delta coding (DELTA) [

], dictionary compression

(DICT) [

], run-length encoding (RLE) [

], and null suppres-

sion (NS) [

]. To minimize the size of the compressed data, existing

systems cascade multiple compression schemes such that the output

of one scheme is the input to another scheme. The database engine

decompresses one layer at a time. Such a cascading decompression

strategy leads to suboptimal performance as multiple GPU kernels

are launched and each requires reading from and writing data back

to the global memory. This causes high memory trac which may

lead to much worse performance compared to a design that does

not use any compression.

In this paper, we improve decompression performance by treat-

ing a thread block as the basic decompression unit, that decodes

one block of encoded entries. This way, we are able to cache a block

of data in on-chip caches and inline multiple decoding steps into

Session 19: Databases for Emerging Hardware

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

1390

a single kernel, resulting in a single pass over the data. Moreover,

we can even inline the decompression with query execution, re-

sulting in a single round-trip to the global memory for the whole

decompression step and query execution.

We call this tile-based decompression model which is inspired by

Crystal [

]. Tile-based decompression allows us to decode at close to

memory bandwidth speed, resulting in a very low decompression

overhead over the previous compression work for GPU. It also

eliminates the need for sophisticated compression planners used by

past works [

], since instead of balancing the trade-o between

decompression time and compression ratio, we can simply choose

the scheme with the best compression ratio — all schemes achieve

similar performance. To the best of our knowledge, this is the rst

paper to decompress cascaded compression schemes in a single

kernel pass and inline with the query execution.

2) Ecient Decompression of Bit-Packed Schemes

Besides the organization of dierent compression schemes, the

decompression speed of individual schemes is also limited in GPU

today. Prior works on CPU compression [16] have shown that bit-

aligned packing compression schemes manage to achieve better

compression ratio compared to byte- and word-aligned packing.

Supporting ecient bit-level packing in GPU is challenging due to

the SIMT programming model and the relatively limited instruction

set to perform bit-level alignment, which is not a problem in CPU

compression schemes due to more powerful CPU instructions.

In this paper, we design optimized bit-packing based compres-

sion schemes and their optimization techniques in the context of

GPU. Specically, we introduce three new bit-packing based com-

pression schemes:

GPU-FOR

does bit-packing in conjunction with

Frame-Of-Reference (FOR) and work well with uniform data and

can handle skew;

GPU-DFOR

uses delta encoding with bit-packing

and FOR, targeting sorted or semi-sorted data;

GPU-RFOR

uses RLE

encoding with bit-packing and FOR, targeting data with high av-

erage run length. These schemes are designed to oer improved

compression ratios while still being able to decode data in parallel

across thousands of threads at close to memory bandwidth speeds.

Overall, our compression schemes can be decoded 2.2

faster than

previous implementations.

We integrate the tile-based decompression model and

GPU-FOR

GPU-DFOR

, and

GPU-RFOR

into the Crystal framework [

], an open-

source highly optimized GPU data analytics engine. We encapsu-

late decompression into a device function that enables program-

mers to change a kernel operating on an uncompressed array to a

compressed column with a single line of code. Our compression

schemes target integer, decimal, and dictionary-encoded strings

and support all query operations that run on these data types. In

data analytics workloads, prior works [

] and commercial

systems [

] typically apply dictionary encoding on top of string

columns to encode them to integers.

In summary this paper makes the following contributions:

•

We introduce tile-based decompression, a decompression strategy

that allows us to decode the data in a single pass at close to

memory bandwidth speed and inline with query execution.

•

We present three optimized bit-packing based compression

schemes (

GPU-FOR

GPU-DFOR

, and

GPU-RFOR

) that can be used

to store data compactly on the GPU.

•

We present an integration of the decompression routines into

the Crystal framework and demonstrate ease of use.

•

We present an evaluation

on multiple synthetic benchmarks

and on the Star Schema Benchmark (SSB). On SSB, our schemes

can achieve similar compression rates to the best state-of-the-art

compression schemes in GPU (i.e., nvCOMP) while being 2.2

and 2.6

faster in decompression speed and query running time.

The rest of the paper is organized as follows: related work and

background are discussed in Section 2. We introduce the tile-based

decompression model in Section 3. We present the data format and

the unpacking implementation on the GPU for

GPU-FOR

GPU-DFOR

and

GPU-RFOR

in Section 4, 5, and 6 respectively. Section 7 discusses

the integration into Crystal. Section 8 discusses the usage and choice

of compression scheme, parameter, and other relevant discussion.

Section 9 evaluates the performance and compression ratio of our

approach against other schemes on GPU. Finally, we conclude in

Section 10.

2 BACKGROUND AND RELATED WORK

In this section, we review the basics of GPU architecture and de-

scribe past approaches to data compression on GPUs and CPUs.

2.1 GPU Architecture

Performance of database operations on GPU is bound by the mem-

ory subsystem (either shared or global memory) [

]. The lowest

and largest memory in the hierarchy is the global memory. A mod-

ern GPU can have global memory capacity of up to 80 GB with

memory bandwidth of up to 2000 GBps. Each GPU has a number

of compute units called Streaming Multiprocessors (SMs). Each SM

has a number of cores and a xed set of registers. Each SM also

has a shared memory (SMEM) which serves as a scratchpad that is

controlled by the programmer and can be accessed by all the cores

in the SM. Accesses to global memory from a SM are cached in the

L2 cache (L2 cache is shared across all SMs) and optionally also in

the L1 cache (L1 cache is local to each SM).

Processing on the GPU is done by a large number of threads

organized into thread blocks (each run by one SM). Thread block

size can vary from 32 to 1024 threads. Thread blocks are further

divided into groups of threads called warps (usually consisting of

32 threads). The threads of a warp execute in a Single Instruction

Multiple Threads (SIMT) model, where each thread executes the

same instruction stream on dierent data. The device groups global

memory loads and stores from threads in a single warp such that

multiple loads/stores to the same cache line are combined into a

single request. Maximum bandwidth can be achieved when a warp’s

accesses to global memory target neighboring locations.

The programming model allows users to explicitly allocate global

memory and shared memory. Shared memory has an order of mag-

nitude higher bandwidth than global memory (10 TBps vs. 900 GBps

on the Nvidia V100 GPU) but has much smaller capacity (a few MB

vs. multiple GB). Finally, registers are the fastest layer of the mem-

ory hierarchy. If a thread block needs more registers than available,

The source code is available at https://github.com/anilshanbhag/gpu-compression

Session 19: Databases for Emerging Hardware

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

1391

of 14

免费下载

关注

评论