Parallel Prefix Sum with SIMD

前缀和操作是一种有广泛应用的有用原语。对于数据库系统而言，它是许多重要操作符（包括连接、排序和过滤查询）的构建块。本文研究了使用SIMD指令和多线程计算前缀和的不同方法。对于SIMD，我们实现并比较了水平和垂直计算方法，以及使用gather/scatter指令的理论上高效的平衡树版本。对于多线程，内存带宽可能成为前缀和计算的瓶颈。我们提出了一种新的方法，将数据分成缓存大小的较小分区，以实现更好的数据局部性并减少来自RAM的带宽需求。我们还研究了四种不同的计算子过程组织方式，具有不同的性能和可用性特征。在实验中，我们发现使用我们的分区技术进行前缀和计算的最有效方法比已经使用SIMD和多线程的两个标准库实现快3倍。

论文研究的问题是如何使用SIMD指令和多线程计算前缀和，并提高计算效率。这是否是一个新问题？

论文提出了一种新的分区技术，将数据分成大小适合缓存的小分区，以实现更好的数据本地性，并减少对RAM的带宽需求。此外，论文还探讨了四种不同的计算子程序组织方式，具有不同的性能和可用性特点。

论文中实现并比较了水平和垂直计算，以及使用gather/scatter指令的理论上高效的平衡树版本。实验结果表明，使用分区技术的前缀和计算比使用SIMD和多线程的两个标准库实现更快，最高可达3倍。

最近在这个领域中，还有一些相关的研究，如《Efficient Parallel Prefix Sums on GPUs》和《Parallel Prefix Sum (Scan) with CUDA》。