Accelerating Tree-Based Irregular Applications by Exploiting SIMD Parallelism

Tree structures are one of the most pervasive data structures. Many tree-based applications feature abundant amount of data level parallelism (DLP), and modern SIMD architectures, such as GPUs and the SIMD instruction extension to CPUs, appear well-suited. However, due to the high irregularity in control flow and data accesses of these applications, exploiting DLP on SIMD architectures is difficult and transforming the SIMD resources into real performance is challenging. This thesis focuses on two such irregular applications: intensive tree search and repeated tree traversals, and proposes two corresponding approaches on CPUs and GPUs. The first proposed approach is Poker, a permutation-based SIMD approach for vectorizing intensive search queries over B+-trees on the SIMD instruction extension to CPUs. B+-trees are popular indexing structures in read-mostly in-memory database systems, in which they are repeatedly searched by numerous independent queries but remain unchanged for a long period. The vectorization of queries in such a problem is hampered by irregular memory accesses. The key insight is to combine vector loads and path-encoding-based permutations to alleviate memory latency while keeping the number of key comparisons required for a query to a minimum. Implemented as a C++ template library, Poker represents a general-purpose solution for vectorizing such an intensive tree search problem on multi-core CPU processors equipped with SIMD units. The next proposed approach is RegTT, a new parallelization approach that orchestrates an efficient execution of a repeated tree traversal algorithm on GPUs. Unlike intensive tree search, repeated tree traversals allow a query to visit each tree node exactly once unless truncated otherwise. Given abundant queries, their efficient parallelization on GPUs is hindered by branch divergence, load imbalance and memory access irregularity, as the nodes and their visitation orders differ significantly under different queries. Based on a key insight into several truncation-induced tree traversal regularities, RegTT employs a new traversal algorithm by beginning with breadth-first traversal, then reordering the queries being processed (based on their truncation histories) and finally switching to depth-first traversal. This enables as many threads as possible in the same warp to visit the same node simultaneously, enhancing both GPU resource utilization and memory coalescing. Both Poker and RegTT are evaluated on representative benchmarks, and their advantages are demonstrated with significant speedups over state-of-the-art works