This article is based on the paper “Interleaved Multi-Vectorizing,” which has been accepted by VLDB 2020. The content below is personally interpreted by the first author Zhuhe Fang(Zhihu ID: 方竹河). For more details, please refer to the paper and video links at the end.
VLDB (Very Large Database) conference started in 1975 and is one of the three leading conferences in the field of databases worldwide. It covers research and development achievements in the area of large-scale databases and aims to promote and communicate academic work in databases and related fields globally.
What is SIMD Vectorization
SIMD (Single Instruction Multiple Data) is a type of instruction set supported by modern CPUs that allows a single instruction to operate on multiple data items. This provides a new form of data parallelism, reducing instruction overhead. As shown in Figure 1, if a vector can operate on four data items at once, then four scalar additions can be performed using a single vectorized addition. It is important to note that SIMD vectorization applies the same operation to several different data items, rather than applying different operations to multiple data items.
Figure 2 SIMD Instructions Eliminating If StatementsSIMD Encounters Cache Miss Limitations
In recent years, SIMD-related research has frequently appeared in the top three database conferences (SIGMOD, VLDB, and ICDE). It is widely used in operations such as joins, sorting, filtering, aggregation, compression, partitioning, and Bloom filters in databases. Many studies indicate that SIMD can bring performance improvements of several times or even more than ten times. However, it is important to note that these experimental results mainly come from small data loads. In cases of large data, the benefits of SIMD are almost lost. We conducted an experiment comparing the performance of SIMD vectorization and common scalar implementations in the probe operation of hash joins. We used a common chained hash table, where each hash bucket is implemented with a pointer list.
As shown in Figure 3, each tuple in table S will find a corresponding hash bucket in the hash table based on the hash operation (Hash) and traverse each node in that bucket for comparison (Match).
The experimental results are shown in Figure 4, where we see that the performance of the SIMD implementation is similar to that of the basic scalar code (scalar), and both decrease as the data volume increases. This result differs from previous related papers that used linear hash tables or cuckoo hash tables with better locality. In chained hash tables, the probe operation suffers from severe cache misses due to frequent and random memory access. The cost of a cache miss can be as high as around 200 CPU cycles, while a simple addition instruction only costs a few CPU cycles. SIMD cannot overcome the cache miss bottleneck, thus losing its advantages.
Multi-Vector Interleaved Execution
There has been a lot of related research on cache miss issues, but directly combining them with the control flow divergence problem encountered in SIMD vectorization (i.e., data in a vector entering different execution branches) leads to vectorized code failing to fully utilize the memory-level parallelism (handling multiple CPU access requests at once) provided by existing CPUs and the data-level parallelism provided by SIMD.
Therefore, this paper proposes Interleaved Multi-Vectorizing (IMV), which is multi-vector interleaved execution. Its main idea is to interleave the execution of multiple vectorized instruction streams. If a cache miss occurs in any instruction stream, it triggers data prefetching (software prefetching) and switches to the execution of other instruction streams. This interleaved execution fully overlaps the memory access of multiple vectorized instruction streams with CPU computation.
In addition, to address the control flow divergence problem in vectorized code, this paper proposes a residual vector state to eliminate bubbles in the vector. This technique can reduce cache misses, branch prediction errors, and computational costs during the join process.
Figure 5 Multi-Vector Interleaved Execution
As shown in Figure 5, there are two vectorized instruction streams on the left and right. When one computation operation is completed (H0), it performs software prefetching for the data needed for the next operation and then switches to the computation operation of another instruction stream (H1). When H1 completes its computation and prefetches just like H0, the execution flow switches back to the previous instruction stream for comparison (M2, also a computation operation), and so on for the subsequent interleaved execution of computations and memory accesses. Since the lengths of each hash bucket are inconsistent, after one comparison operation (M2), Ta and Tc’s probes are finished, while Tb and Td still have 1 and 2 nodes to compare, respectively. At this point, the current vector has only two valid slots remaining. We move this residual vector to a temporary vector dedicated to residual vector states. Furthermore, this temporary residual vector merges with future residual vectors into a complete vector, continuing with subsequent operations. For example, in M12, the temporary residual states of Tb and Td fill into the new residual state, forming a complete vectorized operation M12. As seen in the figure, all vector slots are fully utilized, and sufficient memory access requests are issued.
Experimental Results
We compared the performance of IMV with various other methods in Hash Join Probe (HJP) and Binary Tree Search (BTS).
Figure 6 Performance Comparison of IMV with Other MethodsAs shown in Figure 6,in most cases, the performance of IMV is superior to other methods, being 2.38 times, 1.39 times, 2.22 times, 2.74 times, and 4.85 times faster than AMAC (interleaved execution of scalar code), FVA (fully vectorized AMAC), RAV (directly vectorized AMAC), SIMD (direct SIMD encoding), and Naive (basic scalar implementation), respectively.This experiment used Intel Vtune to further analyze the advantages of IMV through microarchitecture metrics, as shown in Figure 7. This figure explains why IMV is significantly faster than other methods.
Figure 7 Execution Time BreakdownIMV not only reduces memory access overhead but also eliminates incorrect speculative execution.The results of Naive (pure scalar implementation) indicate that the execution time of HJP and BTS is mainly consumed by memory access. Although AMAC optimizes memory access to improve performance, it is severely limited by incorrect speculative execution. Compared to Naive and AMAC, SIMD only eliminates branch errors on the CPU with minimal effect due to the presence of numerous cache misses. Overall, merely reducing memory access or eliminating branches is insufficient to accelerate HJP, BTS, and similar applications.Fortunately, these two goals can be achieved by combining vectorization and prefetching in RVA, FVA, and IMV.IMV outperforms RVA and FVA because it provides a better way to handle vectorization control flow divergence.The original paper includes more experiments, showing that IMV does not significantly improve performance in hash join build and hash aggregation involving reads and writes due to write conflicts; however, IMV is efficient when applied to complete SQL queries compared to existing methods.
Conclusion
This paper proposes a multi-vector interleaved execution technique that interleaves the execution of multiple vectorized instruction streams. When one instruction stream accesses data, it simply issues a data prefetch instruction and switches to another execution instruction stream, hoping to overlap data access with computations from multiple execution instruction streams.Additionally, to address the control flow divergence issue in vectorized code, this paper proposes a residual vector state to integrate with divergent vector states and eliminate bubbles within the vector. This technique is applicable not only to join operations but also to the execution of entire pipelines.For more details, please refer to the paper and my sharing video on Paper Reading, and feel free to discuss at the VLDB 2020 conference.* Paper link:http://www.vldb.org/pvldb/vol13/p226-fang.pdf* Video sharing:https://www.bilibili.com/video/BV1iJ411C7Jj?from=search&seid=14374794260837645052
Tip:
The underlined parts above have links. Due to WeChat’s external link restrictions,
you can click【Read the Original】to enter the Zhihu column
to view the original text and interact with the author ～
About Submission:
We accept submission requests through【Zhihu Column “The Beauty of Distributed Systems”】. The column editorial team will review submissions in the background and publish them on the Zhihu column as soon as they are approved ～
We welcome everyone to click 【Read the Original】 to follow our Zhihu column, and we hope like-minded partners will join us to create and share together!
