Improving Execution Eficiency of Just-in-time Compilation based Qery Processing on GPUs.pdf

章芋文

13页

0次

2022-08-29

免费下载

Improving Execution Eiciency of Just-in-time Compilation

based ery Processing on GPUs

Johns Paul

National University of Singapore

idsjp@nus.edu.sg

Bingsheng He

National University of Singapore

hebs@nus.edu.sg

Shengliang Lu

National University of Singapore

lusl@nus.edu.sg

Chiew Tong Lau

Nanyang Technological University, Singapore

asctlau@ntu.edu.sg

ABSTRACT

In recent years, we have witnessed signicant eorts to improve

the performance of Online Analytical Processing (OLAP) on graph-

ics processing units (GPUs). Most existing studies have focused

on improving memory eciency since memory stalls can play an

essential role in query processing performance on GPUs. Motivated

by the recent rise of just-in-time (JIT) compilation in query process-

ing, we investigate whether and how we can further improve query

processing performance on GPU. Specically, we study the execu-

tion of state-of-the-art JIT compile-based query processing systems.

We nd that thanks to advanced techniques such as database com-

pression and JIT compilation, memory stalls are no longer the most

signicant bottleneck. Instead, current JIT compile-based query pro-

cessing encounters severe under-utilization of GPU hardware due to

divergent execution and degraded parallelism arising from resource

contention. To address these issues, we propose a JIT compile-based

query engine named Pyper to improve GPU utilization during query

execution. Specically, Pyper has two new operators, Shue and

Segment, for query plan transformation, which can be plugged into

a physical query plan in order to reduce divergent execution and

resolve resource contention, respectively. To determine the inser-

tion points for these two operators, we present an analytical model

that helps insert Shue and Segment operators into a query plan

in a cost-based manner. Our experiments show that 1) the analyti-

cal analysis of divergent execution and resource contention helps

to improve the accuracy of the cost model, 2) Pyper signicantly

outperforms other GPU query engines on TPC-H and SSB queries.

PVLDB Reference Format:

Johns Paul, Bingsheng He, Shengliang Lu, and Chiew Tong Lau. Improving

Execution Eciency of Just-in-time Compilation based Query Processing

on GPUs. PVLDB, 14(2): 202 - 214, 2021.

doi:10.14778/3425879.3425890

PVLDB Artifact Availability:

The source code, data, and/or other artifacts have been made available at

https://github.com/Xtra-Computing/Pyper.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International

License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of

this license. For any use beyond those covered by this license, obtain permission by

emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights

licensed to the VLDB Endowment.

Proceedings of the VLDB Endowment, Vol. 14, No. 2 ISSN 2150-8097.

doi:10.14778/3425879.3425890

1 INTRODUCTION

In recent years, we have witnessed a signicant eort in improving

the performance of Online Analytical Processing (OLAP) systems

on graphics processing units (GPUs) [

]. More

recently, JIT compilation-based systems (hereafter referred to as

compiled systems) [

–

] have evolved as the state-of-the-art

query execution systems on GPUs. JIT compilation has the major

advantage to reduce unnecessary materialization of intermediate

data at operator/kernel boundaries within query pipelines and to

reduce the instruction count within GPU kernels. On the other hand,

many eorts have focused on improving the memory eciency

since memory stalls play an important role in query processing

performance on GPUs [

–

]. Given all these optimizations,

it is time to revisit the query execution on GPUs and identify the

opportunities to improve query processing performance on GPUs.

Taking a closer look at existing compiled systems [

–

], we

nd that they work by rst breaking down the query plan associated

with each query into pipelines and then generating a single kernel

for each pipeline of relational operators. We refer to this compilation

strategy as a monolithic approach, since it generates a monolithic

kernel for each pipeline. While this monolithic approach eliminates

the amount of intermediate data materialization, we have identied

two major performance issues.

First, the generated kernels in the monolithic approach often have

a large number of neste d branch instructions per kernel. Hence, the

thread warps executing the kernels generated by the monolithic

approach can have a high degree of divergence, resulting in poor

utilization of a large number of GPU cores.

Second, the high resource requirements of the generated kernels

lead to low parallelism on GPU. Overall, the monolithic approach

generates kernels containing multiple relational operators, which

require even more registers and shared memory resources. That

means the monolithic approach exaggerates the problem of resource

contention on the GPUs since threads can only be scheduled for

execution on GPUs if there are enough free hardware resources

available. Therefore, the monolithic approach also leads to degraded

parallelism on GPUs and cannot fully utilize the large number of

parallel cores on the GPU.

To demonstrate the impact of the two execution eciency issues,

we present the execution time break down of the code generated

from the monolithic approach for TPC-H [

] (queries without sub-

query) and SSB [

] in Figure 1. We divide the execution time

into three components: 1) estimated overhead of divergence, 2) esti-

mated overhead of resource contention, and 3) others. The overhead

202

Q10

Q12

Q14

Q19

Q1.1

Q1.2

Q1.3

Q2.1

Q2.2

Q2.3

Q3.1

Q3.2

Q3.3

Q3.4

Q4.1

Q4.2

Q4.3

100

Execution Time Breakdown (%)

Divergence Resource Contention

Others

Figure 1: Execution time breakdown of TPC-H and SSB

queries demonstrating the impact of divergent execution

and resource contention among threads.

of divergence and resource contention were estimated based on

the achieved execution eciency of the warps and GPU hardware

occupancy rate, both of which can be obtained using proling tools

from GPU vendors. The results of the breakdown clearly demon-

strate that divergent execution and resource contention among

the threads have a signicant impact on the overall performance

of both TPC-H and SSB queries. Overall these ineciencies can

contribute to more than 50% of the total execution time. Therefore,

divergence and resource contention have now become the most

signicant bottleneck for query processing on GPUs.

In this paper, we propose Pyper, a JIT compilation-based query

processing system to resolve GPUs’ divergence and resource con-

tention issues. Pyper introduces two new operators for query plan

transformation, Shue and Segment, to improve GPU hardware

utilization during query execution. Specically, Shue is applied

to a pipeline to reduce the execution divergence. Segment is used

to split a pipeline that has overwhelming resource usage into sev-

eral pipelines with lower resource usage but much higher thread

parallelism. The benets of the two operators come with overheads.

Thus, we develop a cost model to guide the optimal use of Shue

and Segment operators. The challenge is that we need to estimate

the impact of divergence and resource contention, which have been

overlooked in the previous studies [14, 15].

The major contributions of this paper are as follows.

•

We study the eciency of current JIT compilation-based

query processing approaches and identify their severe under-

utilization of GPU hardware due to divergent execution and

degraded parallelism arising from resource contention.

•

We propose Pyper to address the execution eciency issues

of existing JIT compilation-based systems, by introducing

two new operators (Shue and Segment) and an analytical

model to determine the usage of the two operators in a cost-

ecient manner.

•

We conduct in-depth experiments demonstrating the benet

of using the Shue and Segment operators as well as the

accuracy of our analytical model. Our experiments show

that Pyper is able to improve the performance of TPC-H

and SSB queries on average by 1.60x and 1.52x, compared

to Hawk [5]. Pyper further achieves 5.01x and 2.55x perfor-

mance improvement over Omnisci [

] for TPC-H and SSB

queries respectively.

The rest of this paper is organized as follows. In Section 2.1, we

present the GPU hardware’s background and the related work on

JIT query compilation. We then present the architecture design of

Pyper in Section 3. We present the details of the analytical model

and query optimizer in Sections 4 and 5, respectively. We present

the experiments in Section 6 and conclude in Section 7.

2 BACKGROUND AND RELATED WORK

2.1 GPU Hardware & CUDA

A single GPU consists of multiple streaming multiprocessors (SMs),

each of which consists of multiple CUDA cores. All CUDA cores in

an SM share resources like the registers and shared memory. Due

to this sharing, the workload scheduler in GPU only schedules new

threads for execution on an SM, if there are enough registers and

shared memory resources available. GPUs also have an L2 cache

and a global memory that are shared among all the SMs. Each

thread block is given exclusive access to shared memory, i.e., data

in shared memory cannot be shared across dierent thread blocks.

Warp-at-a-time execution model:

In the CUDA programming

model, a program executed by the GPU is known as a kernel. A

kernel is executed as a grid of thread blocks, which can further

be divided into warps (groups of 32 threads). Each thread block

is assigned to a single SM, and the CUDA cores inside each SM

executes the threads in a SIMD fashion, at the granularity of a

single warp. Hence, during any given execution cycle, an entire

warp of threads can only execute a single instruction. That means,

during each instruction issue cycle, only threads that can execute

the same instruction will be activated, and the resources allocated

to the other threads would be wasted. Thus, branch divergence can

be a serious performance issue on GPU executions.

Resource constraints per thread:

For the eciency of GPU

executions, registers, and shared memory are the key resources

that constrain the number of parallel thread executions. Warps can

only be scheduled for execution on GPUs if there are enough free

hardware resources available.

2.2 JIT Query Compilation

JIT compilation-based systems (hereafter referred to as compiled sys-

tems) [

–

] have been developed to further reduce unnecessary

materialization of intermediate data at operator/kernel boundaries

within query pipelines and to reduce the instruction count within

GPU kernels. In the following, we review the related work of JIT-

based query engines on GPUs (more related work can be found at

our technical report [29]).

LLVM based database systems like Voodoo [

], HetExchange [

HAPE [

], OmniSci (formerly known as MapD) and OpenCL based

HorseQC [

] and Hawk [

] were proposed to generate optimized

executable code for heterogeneous systems containing both CPUs

and GPUs. Both Voodoo [

] and Hawk [

] attempt to generate code

to execute on a variety of parallel architectures. HetExchange [

] de-

veloped abstraction for device-oblivious operators and exploited the

heterogeneous parallelism of modern servers with multiple CPUs/G-

PUs. HorseQC [

] extends the operator-at-a-time approach by

203

of 13

免费下载

paper vldb

关注

评论