SIMD体系结构的高吞吐量B+树

发布时间:2022-05-11浏览次数:588

项目背景:

      B+树是最重要的数据结构之一,在各个领域得到了广泛的应用。随着并发查询和存储数据规模的增加,设计高效的B+树结构变得至关重要。由于计算资源丰富,SIMD体系结构为B+树提供了实现高查询吞吐量的潜在机会。然而,由于资源利用率低和内存性能差,以前的方法无法获得令人满意的性能结果。

项目成果:

      我们首先确定了B+树和SIMD体系结构之间的差距。并发B+树查询涉及许多全局内存访问和不同的差异,这与SIMD体系结构特征不匹配。基于这一观察,我们提出了Harmonia,一种新的B+树结构来弥补这些差距。Harmonia 结构设计如图1.所示。在Harmonia中,B+树结构分为关键区域和子区域。关键区域按宽度优先顺序存储节点及其关键点。子区域被组织为一个前缀和数组,它只在关键区域存储每个节点的第一个子索引。由于前缀和子区域较小,并且子索引可以通过索引计算来检索,因此大部分子索引可以存储在片上缓存中,从而实现良好的缓存局部性。为了提高效率,Harmonia还包括两个优化:部分排序聚合(PSA)和缩小线程组遍历(NTG),分别如图2. 所示。 对于PSA,我们在发出查询之前在时间窗口中对查询进行排序。由于相邻的排序查询更有可能共享相同的树遍历路径,因此当在SIMD单元中处理多个相邻查询时,合并内存访问的机会会增加。对于NTG,我们减少了每个查询的线程数,以避免无用的比较。当每个查询的线程组缩小时,可以将更多查询合并到一个SIMD单元中,这可能会增加执行差异。为了缓解查询组合带来的执行分歧问题,我们设计了一个模型来决定如何缩小查询的线程组, 进而缓解内存和执行差异,提高资源利用率。我们对Harmonia CPUGPU平台进行了评估。对28INTEL CPU的评估表明,Harmonia每秒可以实现2.07亿次查询,比基于CPUHB+Tree(最近最先进的B+tree设计方案)快约1.7倍。在Volta TITAN V GPU上,它每秒可以实现36亿次查询,比基于GPUHB+Tree3.4倍。具体参考论文[2]


 1. Harmonia 结构


 2. PSA 搜索方法


 3. NTG 搜索方法

发表论文:

[1] Yan Z, Lin Y, Peng L, Zhang W. ACM, 2019. Harmonia: a high throughput B+tree for GPUs[C]//Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming. , 2019Washington District of Columbia: : 133–144.

[2] Zhang W, Yan Z, Lin Y, Zhao C, Peng L. A high throughput b+tree for SIMD architectures[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 31(3): 707–720.