Partition-based SIMD processing and its application in columnar database systems
The Single Instruction Multiple Data (SIMD) paradigm is considered the core principle for optimizing query processing in columnar database systems. So far, only LOAD/STORE instructions are deemed efficient enough to achieve the expected acceleration, and it is believed that GATHER/SCATTER operations should be avoided as much as possible. However, the GATHER instruction provides a very flexible way to fill data from non-contiguous memory locations into SIMD registers. As discussed in this paper, if used appropriately, GATHER can achieve performance comparable to the LOAD instruction. We outline a new access pattern that allows for fine-grained, partition-based SIMD implementation. We then apply this partition-based processing to columnar database systems, demonstrating the efficiency and applicability of our new access pattern through two representative examples.
1. Introduction
Single Instruction Multiple Data (SIMD) is a parallel concept characterized by applying a unified operation to multiple data elements within a single instruction simultaneously. Modern CPUs support such SIMD instructions along with AVX extensions, with Intel CPUs being a representative example. SIMD extensions include two aspects: SIMD registers, which are larger than traditional scalar registers; and SIMD instructions. The SIMD instruction set includes arithmetic operations, Boolean operations, logical and arithmetic shifts, and data type conversions. Additionally, specific SIMD instructions can load data from main memory into SIMD registers and write it back. On one hand, data elements stored contiguously in memory can be accessed through LOAD and STORE instructions. On the other hand, GATHER and SCATTER instructions reflect an alternative for non-contiguous memory access. However, the general guideline is to avoid using GATHER/SCATTER whenever possible due to significant performance losses. Currently, there is no clear understanding of the performance of GATHER/SCATTER. One of the main contributions of this paper is a systematic evaluation of the GATHER instruction across different Intel CPUs, along with a study of strided access patterns. The evaluation results indicate that the performance of the GATHER instruction primarily depends on the application of the strided access and the stride size. If used appropriately, GATHER can achieve performance close to that of the LOAD instruction. Another contribution is the introduction of the partition-based SIMD access concept, proposing a new block-strided access pattern, and comparing it in a simple analytical query model and integer compression algorithms.
2. GATHER Evaluation
Given thatAggSum performance depends on loading instructions, we use aggregation-sum (AggSum) operations for evaluation.AggSum iteratively computes over the input array, performing addition at each iteration, and finally writes the total (a single value) back to main memory. Figure 1a uses a linear access pattern, utilizing LOAD instructions for iterative computation. The strided variant uses a strided access pattern, utilizing GATHER instructions. The GATHER instruction requires a data base address and a stride length. Based on this, the strided access pattern can be divided into two types: Figure 1b is the traditional stride-full style, loading data according to the stride until the end of the array (using a stride of 2). After processing sequentially, the head moves once and continues with another iteration, thus processing all data sequentially. Figure 1c logically partitions the input array, proposing the stride-block style. In this example, the stride is defined as 2, and the block size is 8. This means that each block of size 8 requires running 2 times the size of 4 SIMD registers. Therefore, it cannot be executed as a whole immediately like stride-full. This style is more cache-friendly than stride-full.
3. Partition-Based SIMD
The above experiments demonstrate that in both single-threaded and multi-threaded environments, SIMD registers can experiment with GATHER operations to access elements in non-contiguous memory, achieving performance comparable to LOAD instruction accessing contiguous memory. However, the GATHER instruction requires an appropriate access pattern to reach its peak performance. According to the evaluations above, the strided access pattern variant stride-block satisfies the following properties P1 and P2:
P1: Input data is logically partitioned into blocks of a certain size, each block size:
wherek is the number of SIMD register channels, which varies according to data types; for example, a 128-bit vector register can be divided into 8 channels of 16-bit data.
g>=1, as the page gap factor.pagesize is determined by the operating system, typically4kb.
P2: Continuously processing logical blocks, with the access pattern within each block being a byte-strided access pattern.
The block-strided access pattern is illustrated in the following figure:
The number of SIMD channelsk is 4, thus the logical partitioning of input data consists of4 pages, gap factorg is1. Ifg>1, then ablock consists ofg*k contiguous pages, with one channel responsible forg pages. This means thatg defines the gap between two accessed pages, with the access pattern within each block using a stride-g access pattern.
This access pattern supports a fine-grained, page-partitioned SIMD processing concept. Our partition-based SIMD processing concept implicitly partitions the data through access patterns and partitions, allocating pages to SIMD channels. SIMD channels operate on their local pages.
Understanding: This is equivalent to logically partitioning a long string of input data into blocks, with each block allocating g*k pages. If g>1, for example, is 2, then within the block, GATHER instructions are used to access with a stride of 2. Iterating once, k pages are accessed concurrently; after the head pointer moves to complete the access, it shifts one page, iterating twice to access the subsequent pages concurrently. What is the utility of this method? Can it be applied to GATHER? Filtering the data for dumping, with a non-fixed stride, seems not to require this fixed stride approach.
4. Application Cases
4.1 Vectorized Query Processing
A scenario for applying partition-based SIMD is vectorized queries based on column storage. Each query operator iteratively processes multiple values in a vector. The advantage is good instruction cache and CPU utilization, while maintaining low materialization costs. However, choosing an appropriate vector size is not straightforward. Smaller vectors improve data cache utilization but increase instruction cache misses. Larger vectors increase materialization costs and decrease data cache utilization. Therefore, our partition-based SIMD processing concept aims to explicitly cache the data required for processing multiple pages currently and in the future, improving the performance of this processing model compared to linear access.
For records satisfying the predicate condition on columnB, an aggregation sum operation is performed on columnA. The necessary operators are implemented: filter and AggSum. The Filter operator first broadcasts the predicate value to the SIMD register, then each iteration filters the data from columnB into the SIMD register, comparing it with the predicate vector register. The loading operation uses either LOAD instructions (linear access pattern) or GATHER instructions (block-strided access pattern). AVX2 and AVX512 support vector register operations for comparison. The result is converted into a bitmask, reducing materialization costs. The nth bit is 1, indicating that the nth element in the SIMD register meets the filter condition. No additional positional information is stored alongside the bitmask, so operators using this bitmask must implicitly decode specific information. When using AVX512, this conversion is done dynamically. Efficient implementation in AVX2 is more challenging.
In AVX2, _mm256_cmpeq_epi32 compares two SIMD registers (containing 32-bit integers) and produces a SIMD register value of the same size. Equal bits correspond to 1, otherwise 0. The result is converted into a bitmask using _mm256_castsi256_ps. The _mm256_movemask_pd wraps the highest bits of each 64-bit element into a word. Although this process seems costly, our experiments show this reduces memory by 32 times, mitigating the additional computational cost of memory-bound algorithms.
The AggSum operator initializes a result SIMD register to 0 upon the first call. After processing a complete vector, the operator returns this SIMD register. The same register is then used as input for each subsequent call, modified within each processed vector. Once all data is processed, the sum value is aggregated into the SIMD register and returned. For each vector, the AggSum operator transfers relevant data from columnA into a SIMD register, loading the bitmask from the previous operator.
It is important to note that the data transfer method must align with the previous operator. While AVX512 natively supports masks, we need to create a special mask SIMD register for AVX2 and use it to zero out invalid data. This SIMD register contains all bits set to 0 or 1. Thus, the mask can first be broadcast to the SIMD register, using lane-id and binary AND operations. Consequently, each channel in the SIMD register contains either a value of 1 or 0 corresponding to the respective bit. All elements in the SIMD register are reduced by 1, where -1 equals all bits set to 1. Finally, the resulting SIMD register is negated and ANDed with the data SIMD register.
In the evaluation, three dimensions are considered: 1) the filtering selectivity; 2) vector size; 3) page gap factor. Single-thread evaluation results: 1) 1024 vector size (AVX2 using uint32_t); 2) 2084 vector size (AVX512, uint64_t). Since we implemented the AggSum branch, the overall query throughput depends on the filtering selectivity. This branch checks the filtering bitmask results, as AggSum operations only apply to values that meet the conditions. If the bitmask is all 0, that group of values is skipped. Based on the evaluation results, it is believed that the partition-based SIMD processing concept can be efficiently applied to vectorized processing models.
Understanding: Applying the partition-based processing only to loading seems to have no practical value. If loading could be applied to indexed Gathers, it would allow for flexible handling of filtered data, making it much more meaningful.
References
2022: https://link.springer.com/article/10.1007/s13222-022-00431-0