A fast vectorized sorting implementation based on the ARM scalable vector extension (SVE).
A fast vectorized sorting implementation based on the ARM scalable vector extension (SVE).
复制标题
DOI：
10.7717/peerj-cs.769
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Bramas B
中科院分区：
文献类型：
--
作者：
Bramas B
开发人员实现算法的方式以及这些实现在现代 CPU 上的行为方式取决于这些算法的设计和组织。矢量化单元 (SIMD) 是少数可以且必须明确控制的 CPU 部件之一。在 HPC 社区中，x86 CPU 及其矢量化指令集几十年来一直是事实上的标准。指令集的每个新版本通常都是向量长度加倍以及新的操作。每一代人都在推动适应和改进以前的实现。 ARM 可扩展向量扩展 (SVE) 的发布从根本上改变了一切，原因有几个。首先，我们预计 ARM 处理器将在未来几年内装备许多超级计算机。其次，SVE 的接口在几个方面与 x86 扩展不同，因为它提供不同的指令，使用谓词来控制大多数操作，并且具有仅在执行时已知的向量大小。因此，使用 SVE 对如何适应算法（包括已经在 x86 上进行了充分优化的算法）提出了新的挑战。在本文中，我们基于著名的快速排序和双调排序算法移植了一种混合排序。我们使用 Bitonic 排序来处理小分区/数组，并使用矢量化分区实现来划分分区。我们解释如何使用谓词以及如何管理非静态向量大小。我们还解释了如何有效地实现排序内核。我们的方法只需要一个 O(log N) 的数组来用于分区阶段的递归调用，无论是顺序还是并行情况。我们在现代 ARMv8.2 (A64FX) CPU 上测试我们的方法的性能，并通过对整数、双浮点数和整数的键/值对进行排序/分区来评估我们实现的不同层。我们的结果表明，我们的方法比 GNU C++ 排序算法平均加速 4 倍。
The way developers implement their algorithms and how these implementations behave on modern CPUs are governed by the design and organization of these. The vectorization units (SIMD) are among the few CPUs’ parts that can and must be explicitly controlled. In the HPC community, the x86 CPUs and their vectorization instruction sets were de-facto the standard for decades. Each new release of an instruction set was usually a doubling of the vector length coupled with new operations. Each generation was pushing for adapting and improving previous implementations. The release of the ARM scalable vector extension (SVE) changed things radically for several reasons. First, we expect ARM processors to equip many supercomputers in the next years. Second, SVE’s interface is different in several aspects from the x86 extensions as it provides different instructions, uses a predicate to control most operations, and has a vector size that is only known at execution time. Therefore, using SVE opens new challenges on how to adapt algorithms including the ones that are already well-optimized on x86. In this paper, we port a hybrid sort based on the well-known Quicksort and Bitonic-sort algorithms. We use a Bitonic sort to process small partitions/arrays and a vectorized partitioning implementation to divide the partitions. We explain how we use the predicates and how we manage the non-static vector size. We also explain how we efficiently implement the sorting kernels. Our approach only needs an array of O(log N) for the recursive calls in the partitioning phase, both in the sequential and in the parallel case. We test the performance of our approach on a modern ARMv8.2 (A64FX) CPU and assess the different layers of our implementation by sorting/partitioning integers, double floating-point numbers, and key/value pairs of integers. Our results show that our approach is faster than the GNU C++ sort algorithm by a speedup factor of 4 on average.