In-Depth Analysis of OLAP Query Performance on Heterogeneous Hardware

We use primitives as basic building blocks of DBMS operations. Primitives in this context are atomic functions that are combined together to form an SQL operator. They can be parallelized and arranged together to execute partial or full SQL queries [7, 22]. We surveyed the primitives and detailed their alternative implementations in our paper [19]. Below are the primitives considered in this work:

Using these primitives, we build a Directed Acyclic Graph (DAG) for a given SQL query.

CPU: the key characteristics of CPUs are instruction pipelining, hierarchical caches and SIMD [24]. With pipelining, CPUs provide instruction-level parallelism but the overall execution in a system is delayed due to data and control-flow dependencies across instructions. This delay is hidden using out-of-order execution and branch prediction strategies. Another improvement in current CPU generations are the SIMD units i.e., vectorized execution of a single instruction across multiple values [12, 37]. These units can execute an instruction on a vector of data instead of just on a single value.

GPU: A GPU contains thousands of physical cores to support embarrassingly parallel operations. GPUs use a higher degree of Thread Level Parallelism (TLP) compared to CPUs in order to hide memory access latency. A GPU is capable of executing a large number of simple instructions in parallel, but does not have the capability of branch prediction. Therefore, control-flow-heavy operations cannot exploit the full parallelism in a GPU due to the serialization of diverging branches [21]. Finally, the biggest challenge in a GPU is the transfer time spent to move data from the CPU’s main memory to the GPU’s. This transfer overhead can over-shadow the performance benefits of GPU-acceleration [11].

FPGA: FPGAs are capable of realizing arbitrary logic circuits by mapping computation, i.e., mathematical (pure, stateless) functions, to hardware lookup tables (LUT). Additionally, modern FPGAs contain specialized hardware for more efficient processing, including large blocks of SRAM (BRAM), carry chains connecting neighboring LUTs and multiply-accumulate units (DSP). Finally, dynamic partial reconfiguration (DPR) allows the designer to exchange parts of the circuit at runtime. Traditionally, FPGAs are programmed using hardware description languages (HDL) that allow for low-level design specification on the register transfer level (RTL). As compiler technology improved, the concept of high-level synthesis (HLS) was developed. Here, the kernel is programmed in a higher-level language such as C++, and is then transformed automatically into a circuit. HLS provides a more software-like development environment, but can sometimes be less flexible and also incur a slight resource overhead compared to an RTL design [44].

For executing primitives on a CPU, we follow the operator-at-a-time execution model proposed by Boncz et al. [7]. This model executes one primitive at a time for all input data, in a tight loop. When one primitive in the query plan finishes execution, the next one starts. Though vectorized execution of these primitives provide performance benefits [50], this is not suitable for a heterogeneous environment, due to high data transfer delay.

Figure 1 shows an OpenMP implementation of the reduce-add primitive to be run on a multi-core CPU.

For data transfer in OpenMP, we simply forward the input pointer to the target function for execution.

Similar to CPUs, GPUs also follows operator-at-a-time execution. For each primitive (or kernel in the context of OpenCL), the runtime loads data as well as creating result space in the GPU based on the target kernel. The result space is estimated based on the input size, intents (data processed per thread) [31]. Once set, the kernel is executed.

A task sets the number of parallel local items and the work groups required for parallelizing the task on the GPU. These values are computed from the input size and parameters present in the task. Note that consecutive operations in GPU simply forward the data buffer without any expensive data routing.

In Figure 2, we show an example OpenCL implementation for the reduce-add primitive. It is worth mentioning, that the same kernel code can be used to run on a CPU instead of a GPU. Note the kernel’s additional parameter INTENT defining the number of inputs processed by a single work item.

Data transfer mechanism is different based on the target OpenCL device. For OpenCL execution on CPU, we simply forward the host pointer. In case of GPUs, we consider the case of a cold-store, where initially no data is available in GPU and data is transferred explicitly according to the incoming query. However, all intermediate results are stored in the GPU memory and only the final result is transferred back to the CPU.

While HLS solves most of the complexities in programming a FPGA, the software integration problem still remains. To connect FPGAs to a host server, there exist products such as Xillybus over PCIe [46] which provide both hardware interfaces and OS drivers, but any user program still has to be adapted specifically to every FPGA design. Thus, single-function accelerators are common in the industry [27, 32, 43]. Another option is to implement multiple functions in the same FPGA design, which limits the amount of resources every functional unit can occupy, and therefore potentially reduces performance. We have already analyzed these shortcomings with respect to Intel OpenCL for FPGAs [15]. To combat this, modern FPGAs allow for smaller parts of the fabric to be reconfigured with different circuits during runtime, instead of just loading a complete design into the FPGA at power up. Dynamic partial reconfiguration of reconfigurable partitions (RP) allows for function units (FU) to be exchanged at runtime, and therefore greatly increases flexibility, but also forces higher complexity upon the designer. One possibility to hide this additional complexity is to specify the design in such a way that a simpler representation of it can be devised: An overlay architecture abstracts away the raw image of FPGA hardware resources into a user representation more specific to their application.

All measurements are taken on a server equipped with an AMD Epyc 7351P 16-Core Processor, an AMD Radeon RX Vega 56 with 8GiB HBM and a Xilinx Zynq-7000 ZC706 evaluation card with 2GiB DDR3 DRAM and Debian Linux as the operating system.

FPGA – Physical Setup: Our FPGA provides 218600 LUTS, 437200 FFs, 545 BRAMs, 900 DSPs [45]. The SoC comprises of Zynq PS: two ARM9-cores and one DDR memory controller. Based on the SoC and PCIe endpoint (i.e. the fixed-function units) layout, we implement the I/O-pins to DDR memory controller. Similarly based on the layout as well as the locations and number of DSP resources, we choose a \(4\times 7\) tiles grid for .

Each FU can at most use 1200 LUTs, 2400 FFs and 20 DSP units. Fig. 6 shows an abstract representation of both the logical and physical design, the latter of which is constrained by placement requirements for the PCIe core and DDR3 memory controller. For the same reason, only the two leftmost tiles on the bottom row are equipped with an extended interface, which in addition to the normal data streaming connections also allows random memory access. These tiles are sized slightly larger and occupy 1600 LUTs, 3200 FFs, 10 BRAMs, and 20 DSP units, but they still fit within the regular grid structure. All streaming connections within the overlay architecture are set to 32 bits. The complete design requires 73949 LUTs, 75203 FFs, 37.5 BRAM and no DSP units. In relation to the available resources, this is 34% of LUTs, 17% of FF and 7% of BRAM. Given the requirements of the DDR3 memory controller, the overlay architecture is clocked at 200Mhz.

We test the devices’ general processing throughput by launching an increasing number of aggregate operators, with each input column consisting of 10 million integers. CPU and GPU process the aggregates sequentially, but with wide data parallelism within each primitive, while on the FPGA, functional parallelism between the aggregates is employed. The resulting execution times for the four primitive implementations on our three devices are shown in Fig. 7. The data shows that GPU, just as expected, by far outperforms CPU and FPGA due to its high memory bandwidth and optimized atomic operations. With its lower clock rate and limited throughput per DMA channel, the FPGA is much slower for a single aggregate than the other devices. However since all FUs can run completely independently from each other (or in a hardware pipeline), with statically allocated bandwidth per connection, the FPGA handles functional parallelism efficiently: Performance is nearly constant when increasing the number of concurrent reduce operations until memory controller, or rather, system interconnect bandwidth limits are reached. The step down in performance after three concurrent aggregates happens because at that point, the faster memory controller becomes saturated and additional aggregates have to fall-back to the slower memory. Finally, the grey line in Fig. 7 shows the theoretical maximum throughput for the FPGA, which is almost reached.

Due to their operator-at-a-time execution, performance of both CPU and GPU degrades linearly with increasing numbers of concurrent reduce operations. In case of the single aggregation, the runtime is less than 1ms for CPU OpenMP and GPU OpenCL versions. Hence, they are not vidible in the Fig. 7. The GPU shows a near linear growth in execution time, as it executes one reduce after another. Still, the GPU performs well for reduce compared to other implementations. Even with the OpenMP variant of CPU being nearly twice as fast as the OpenCL version, they are slower compared to GPU.

Unlike the primitives of query 6, a hash join implementation requires large amounts of intermediate data to be stored in order to determine the join pairs. Such random memory accesses are particularly expensive in FPGAs. To analyse the performance of joins, we can limit ourselves to just the primitives required for them, since they will be the most expensive primitives in the overall query pipeline.

We split the hash join into its two primitives: hash-table build and hash-table probe. We use linear probing for collision resolution and multiplicative hashing as hash function. On the FPGA, the join primitives can be loaded into the extended tiles equipped with random memory access. Since these tiles still need to fit within the regular grid of the physical design, their resources are constrained in similar ways as the pure streaming tiles. To circumvent these limitations, we could break these primitives out of the grid or implementing them in the static part. This would allow for higher-performance implementations at the cost of flexibility, for example by implementing large domain-specific caches. Another performance limitation is that the memory interface generated by the HLS compiler is not well-optimized for concurrent random memory access.

The execution time for hash join is given in Fig. 8. Due to the given limitations, we see a larger performance penalty for FPGA in comparison to the other devices.

Based on our results, the performance of OpenCL-based CPU hash-build is comparatively slower than that of OpenMP based implementation (cf. Fig. 11). However the OpenCL hash-build in CPU is faster than that of the OpenMP implementation. Such performance difference comes from threading strategies present in the implementations – OpenMP is coarse grained and OpenCL is fine grained [35]. Such performance from OpenCL and OpenMP are still worse compared to the GPU. Here, the massive parallel nature of the GPU is useful in probing multiple input values thereby having better performance than CPU.

We report performance measurements for table sizes from 1000 rows up to 128 million rows which almost fills up the entire memory on the smallest device.

The communication overhead to start computation in non-CPU devices is included in the results. Looking at the data from this angle allows us to analyze end-to-end latency from the database system optimizer’s point of view, including performance and quality of the host drivers. The figures detailing query execution time, including data transfer to PCIe devices, are organized as follows: Fig. 9 covers the whole range of input rows and includes all transfer times and extra overhead, in this case just the reconfiguration time for the FPGA. To facilitate a comparison focused on pure compute performance, Fig. 10 shows execution time only.

Finally, Fig. 11 shows the execution time of the single primitives for the platforms that do operator-at-a-time execution. Since the FPGA overlay architecture executes all primitives in parallel in a hardware pipeline, it is not included. This data shows strong evidence for implementing architecture-specific primitives. This is especially clear for the materialization primitive, which underperforms on GPU due to architectural disadvantages. In contrast, for the reduction, the GPU can bring its specialized hardware for atomic operations to bear.