摘要

本文描述了一个通过高效利用SIMD指令和当今处理器缓存内存的，用于对一个数据结构进行排序的新算法。当前，通过SIMD指令实现的多路归并排序已经被作为一个对于int值排序的高效内存排序算法使用了。在使用SIMD指令对数组结构进行排序时，一个常用的方法是首先将每行记录的key和index打包成为一个int值，使用SIMD指令对kv对进行排序，然后基于有序的kv对重组数据行。这种方法可以有效地使用SIMD指令因为它在打包int值时对kv对排序，因此它可以使用高效的、基于SIMD的对int值的多路归并排序实现。然而，由于这种方法的随机和分散的内存访问，在最后的重组阶段会造成频繁的缓存丢失cache miss，因此这个阶段限制了单线程性能和多核的可伸缩性。本文提出的方法同样基于多路归并排序，但它可以避免重组数据的随机访问，同时还能高效利用SIMD指令。

一、简介

排序操作在很多软件系统中是一个基础操作。通过在合并操作中有效地使用SIMD指令，多路归并排序优于其他基于比较的排序算法，例如不适合使用SIMD指令的快排。多路归并算法又进一步减少了所需的主内存带宽，因为多路归并可以减少merge阶段，而归并的每一个阶段都需要访问所有的数据。

在实际的应用场景中，排序通常会基于结构中存在一个排序key对结构进行重组，我们将每一个结构体称之为record。在使用SIMD执行对大型纪录进行排序的时候，一个常见的方法是首先将每个记录的key和index打包成一个正数值，例如将一个32bit的整数值和32bit的索引值打包成为一个64位的正数值，然后使用SIMD指令对key-index对进行排序，最后根据有序的key-index对重组记录。这种方法如上所说可以有效地利用SIMD指令，但在重组阶段由于随机和分散的内存访问很容易造成缓存丢失cache miss。因此这个阶段限制了单线程性能和多核的扩展性，特别是当每一个record都比处理器的cache line小的时候。当record较小的时候，只有一部分传输数据会被实际使用到，大量的未使用数据会浪费内存带宽。

一个更直接的方法是不生产key-index对，直接对原始record进行排序，在每一个对比时移动所有的record。这种方法不需要随机访问以重组数据，但是它很难以利用SIMD指令，因为从多个记录中读取key到向量寄存器会分散内存访问，这会带来额外的开销，并抵消SIMD指令的好处。

本文提出了一种新的稳定排序算法，可以同时利用SIMD指令的高性能，同时避免随机内存访问带来的缓存丢失cache miss。本文提出的新算法，基于多路归并算法，对每个多路merge阶段执行了key编码和record重组，对比传统的key-index方法只在整个排序操作的开始阶段进行编码，只在最后部分进行记录重排。在每个多路合并阶段，从k个输入流读取数据（本文实现中k=32），并将合并后的结果写入输出流，我们会从每一个record中读取key并将key和streamID打包以使用一个int值（中间int值）表示这个record，通过SIMD指令来合并这些中间int值并最终基于中间int值中编码的streamID来对record重排序。和传统的key-index方法不同，如果k值和cache以及TLB相比不算太大，那么我们的方法将不会导致过多的cache miss。本文中我们还描述了如何通过使用32bit int值而不是64bit int值作为中间结果来提高单个SIMD指令中的数据并行度。

避免随机内存访问造成的内存带宽浪费对于多核处理器来说非常重要，因为处理器中内核的总计算能力的增长速度已经超过了系统内存的内存带宽。

二、背景

2.1 相关工作

由于许多广泛应用的排序算法，例如快排，不适合使用SIMD指令，多路归并排序算法通过使用SIMD指令获得了比它们更好的性能。基于向量化的归并，我们可以通过基于向量寄存器上实现一个标准的基于比较的合并操作，来整合一个无分支的排序网络，以减少分支预测失败的开销。

归并排序算法的发展史中，首先有使用SIMD指令实现的bitonic归并排序，然后向量化的多路归并排序算法出现了，在对32bit int排序时性能提升了3倍，接着一个使用大于向量寄存器数量的排序网络被提出，以增加指令级别的并行度。

向量化归并排序算法和基数排序算法的性能对比结果显示，在当前的最新CPU中，key size较小（例如小于8bytes）的情况下，基数排序可能比向量化归并排序性能更好。但是向量化归并排序算法具有高效SIMD指令和低内存带宽要求的特性，随着处理器的发展它可以整体获得比基数排序更好的性能。

本文主要光柱对于一个结构体数组的向量化归并排序，而不是简单一个int数组。对比前面提到两种多路归并排序方法，分别存在以下问题：

• 打包key-index的多路归并排序：在最后重组数据的阶段可能导致频繁的cache和TLB miss，因为这个阶段会随机访问主存。

• 直接对原始record进行多路归并：很难高效地使用SIMD指令，因为key在内存中不是连续存储中，因此只能主动将key加载到向量寄存器中，从而也丢失了SIMD指令的好处：数据并行和分支预测消除。同时，这一方法也会导致更多的内存拷贝，因为它在排序阶段移动的是整个record。

本文提出的基于SIMD且缓存友好的向量化多路归并排序算法解决了上面两种方法在对结构体数组排序中带来的问题。

数据库的Join操作可以使用sort-merge join，它同样处于对SIMD指令应用和更少的内存带宽，随着处理器的发展可能会整体由于hash join。假设join操作产生了大量的输出，那么在join操作后的也可以使用本文提出的算法避免重组开销，以进一步提升sort-merge join的性能。同时，sort-merge join在遇到key和index对无法编码成64-bit int值时会造成性能降低。本文提出的方法可以避免这个问题，即使是对于大量的输入，因为它没有直接对record ID进行编码，正如我们在第3.2节中讨论的那样。

2.2 用于整数排序的向量化多路归并排序

2.2.1 使用SIMD指令进行归并排序

为了在整数的双向合并中充分利用SIMD指令，一个标准的技术是结合SIMD排序网络和基于比较的合并操作。

什么是排序网络呢？简单来说，排序网络就是通过一系列的比较器（comparators）来调整输入数据的次序，使无序的数据最终变成有序的输出。

一个很自然的问题是，我们已经有了那么多种排序算法，为什么还需要排序网络呢？个人觉得有以下几个原因。

普通的排序算法，不管是简单的冒泡排序、插入排序，还是效率更高的堆排序、归并排序、快速排序等，都是在串行的计算机上实现的。通过信息论或者决策树模型可以证明，基于比较的排序算法在最坏情况下必须要通过 Ω(nlogn)Ω(nlog⁡n) 次比较操作才能完成对 n 的数据的排序。因此，具有平均情况时间复杂度 Θ(nlogn)Θ(nlog⁡n) 的排序算法已经是最优的了。虽然桶排序、计数排序等可以实现线性时间的排序，但是它们都依赖于输入数据的某些特殊性质，并非通用的排序算法。那么，如何做到比 Θ(nlogn)Θ(nlog⁡n) 时间更快的排序呢？既然所需要的比较操作次数无法减少，那么一个可能的方法就是并行化，在同一时间完成多次比较，排序网络就可以做到这一点。

排序网络的另一个优点是适合于硬件实现。观察一下衡量排序网络性能的网络“深度”，会发现它居然和数字电路中的“关键路径”的概念不谋而合。我们知道关键路径决定了数字电路能够工作的速度，而排序网络的深度也决定了它能够以多快的速度完成排序。

下图中的a、b分别是一个向量化merge操作的伪代码和一个针对2个向量寄存器的bitonic merge操作的数据流。

 当一个向量寄存器只能存储更少的数据，例如在128-bit的SIMD架构上执行64-bit int值的计算，我们可以结合多个向量寄存器来模拟一个长向量寄存器。实现一个输入size大于实际向量寄存器的排序网络可以获得更好的性能，因为它通过重叠多个比较来隐藏指令的延迟，从而提高指令级的并行性。下图为一个使用SIMD的多路归并操作实例，多路参数k=8。

2.2.2 多路归并

多路归并增强了标准的双向归并。它重复了多路的merge操作，即从多于2个数据流读取输入记录并将合并后的记录输出到一个输出流中，来对所有的记录进行排序。多路归并将merging stage的数量从log2N减少到logkN，其中N是记录的总数，k是多路的参数。归并会在每个merging stage扫描所有的成员，因此，使用更大的k值可以同时减少stage的数量和所需的内存带宽要求。更少的内存带宽对于更高的单线程性能和多核下的扩展性来说都是至关重要的因素。

为了在多路归并排序中减少系统内存所需的内存带宽，使用上面的图1所示的2路向量化归并操作作为构建块，我们以流的方式执行由多个双向merge操作组成的多路merge操作，使用小内存缓冲区(在我们的实现中每个4 KB)，可以适配处理器的缓存内存。图2说明了我们如何在cache memory中实现多路merge操作。我们使用k=8（8-way merge）为例，如图中所示，一个8-waymerge操作会包含3层2-way merge操作。我们在一个单线程中执行这个完整的merge操作。中间结果会存储能适配cache memory的小内存buffer中；因此，我们只需要在最开始和最后去访问系统主存。当中间缓存为空时，我们会回到前一个层次的2-way merge来填充中间缓存。buffer被填充后，我们会基于新的record重新执行merge操作（pipeline操作）。我们会重复这些操作一直到将input stream消费完。

2.2.3 使用SIMD对小块进行Combsort

为了让向量化的归并操作执行更高效，每一个input stream都需要保证有足够的record数量。因此，我们首先使用另一种排序算法对小block进行排序，然后执行多路合并来合并这些已排序的block。

对于小block的初始化排序，我们可以使用向量化的combsort（梳排序）。combsort扩展了冒泡排序，它会比较非相邻元素，而不是像冒泡排序一样值对比相邻元素。将值与较大的分隔值进行比较可以极大地提高性能，因为每个值都能更快地向最终位置移动。在每个迭代中，分离值都会除以一个称为收缩因子的数字(在我们的实现中是1.3)，直到它变成1。然后最后重复分离值1的循环，直到所有的数据都有序。combsort的平均计算复杂度近似NlogN。向量化的combsort可以消除几乎所有依赖数据的条件分支，因此不会受分支预测失败的影响。由于其简单性和较小的误预测开销，向量化的combsort比向量化的路归并排序在对小块进行排序时具有更高的性能。然而，由于其糟糕的内存访问局部性，当数据对于处理器的缓存内存来说太大时，向量化combsort的性能会急剧下降。这就是为什么向量化combsort最适合在执行向量化多路归并排序之前对小块进行排序的原因。

梳排序(Comb sort)是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。梳排序是改良自冒泡排序和快速排序，其要旨在于消除乌龟，亦即在阵列尾部的小数值，这些数值是造成冒泡排序缓慢的主因。相对地，兔子，亦即在阵列前端的大数值，不影响冒泡排序的效能

2.2.4 多线程并行

通过使用这两种算法，向量化的多路（k-way）归并排序和向量化的combsort，我们可以使用通过两个阶段使用p thread来对所有的数据进行排序，其中p是线程的数量：

1. 将所有要排序的数据划分为p个块，并为每个块分配一个线程，使用多个线程并行排序。每个线程独立地执行向量化归并排序，并在每个输入序列小于预定义的大小(b条记录)时切换到向量化combsort。

2. 通过多线程执行向量化k-way归并排序来合并p个有序的块

在第一个阶段，每个线程都不需要和其他线程保持同步。为了并行化第二个阶段，多个线程必须在一个多路合并操作上合作，以充分利用线程级并行性，因为块的数量会比线程的数量要小。我们将每个input stream划分为p个sub stream，利用二分搜索并行化一个merge操作。然后第i个线程与来自k个输入流的第i个子流合并。另外，如果每个线程中的数据量不平衡，它会对线程中的数据进行rebalance。在将多个input stream拆分为sub stream后，线程运行时就无须互相同步。因为block数量b是一个与N无关的常量，整个计算过程的复杂度取决于向量化归并排序的复杂度，即O(NlogN)，即便是在最差的场景中。

三、排序结构的改进

本章中，我们假设每个record都是定长的。我们先假设每个key都是32bit，后面再来讨论如何处理更大的key。

3.1 SIMD和缓存友好的多路归并操作

为了避免代价巨大的record重组，我们使用了一个混合方法来将原始数据和key-index结合起来。上面的图2展示了当要排序的record是一个结构体时，直接方法（直接归并原始数据）的多路merge操作。我们基于图2中的多路merge来使用SIMD指令使它更高效。

图2中用于merge结构体的多路merge操作的问题在于，它需要一个gather操作来从多个record中读取key并放到向量寄存器中，因为每个record都有一个payload，会有一部分数据不是用来排序的。现代处理器的SIMD指令在数据从连续内存中加载和存储时性能最佳。

图3展示了我们所提出的基于SIMD和缓存友好的多路merge操作。为了让gather操作的负载尽可能的小，我们在多路merge操作的开始截断将key和streamID编码成为int值（中间int值），即在第一层级的2-way merge操作从主存中读取record的时候，并通过SIMD指令merge它们。在多路merge的最后，我们会基于merge过的中间int值对record进行重排。在这个阶段，我们顺序地从k个input stream中读取数据并将它们顺序地写到一个合并后的output stream中。如果k不是太大，这可以避免过多由于随机访问带来的cache miss和TLB miss。因为merge操作是针对中间int值执行的，我们不需要在除了第一层级的merge操作之外再执行gather操作以读取key。

图4对比了这三种方法。我们所提出的方法和key-index方法对比，我们对record进行了多次重组，而不是仅执行一次，这避免了在重组阶段的大内存复制开销带来的cache miss。当record的size小于cache line size时，随机内存访问的成本会超过附加的（顺序的）内存拷贝成本。

在我们的方法中，多路的数量k是一个对性能至关重要的参数。因为我们需要在多路merge的开始就执行key的提取，并在merge的结尾将整个record从input stream拷贝到output stream中，较大的k值会减少提取key和拷贝record的开销。然而，当k变得太大时，在多路merge操作的结尾拷贝record的操作可能会导致许多cache和TLB miss。因此，k值必须小于TLB的数量，来避免这一问题。同样，大的k值会导致多路merge操作使用的中间buffer的总量更大。因此，太大的k值可能会导致merge操作中的cache miss。

在k=N时，key-index方法和我们提出的方法几乎是等价的，当k = 2时，我们的方法几乎和direct方法一样。因此，我们的方法是由参数k参数化的两种现有方法的泛化，但我们发现k的最佳值在这两种方法对应的两个极值之间。在我们的实现中，我们使用k = 32 = 2^5。这意味着每一个多路merge操作都包含了5个level的merge，每一个level都会执行2-way的向量化merge操作。与直接方法相比，我们可以减少提取键的开销(包括收集操作的开销)，并仅将对象复制到1/5。使用大k可以进一步降低这些成本，但是增加的缓存丢失会导致净性能下降，如性能评估所示。表1总结了这三种方法。

3.2 Key和StreamID编码

在我们的方法中，我们将key和它的streamID（范围0~k-1）编码成为一个中间int值，而不是像key-index方法中的一个key-index对（0~N-1）。k比N小得多。我们只需要对streamID而不是index进行编码，因为每个input stream的record已经是有序的；因此，他们不会在最终的output stream中反转。我们可以通过为每个input stream维护一个指向下一个要复制的record的指针，并在将record从该stream复制到output stream时递增指针，来保证合并的记录被排序。我们使用较高的bits对key进行编码，以便根据编码后的key对中间int值进行排序，并将streamid编码到较低的位中。

这种处理方式带来了一个好处是，对比key-index方法，我们提出的方法可以对更大的数组进行排序。在key-index方法中，只可以对2^32(=4G)的记录进行排序，因为当key是32位而中间整数是64位时，我们只有32位来编码key。在我们的方法中，没有对记录总数的限制，因为我们只将streamID编码为中间的整数值，它是一个独立于记录总数的可配置参数。我们被k而不是记录数N所限制。然而，这并不是一个问题，因为k必须小于缓存和TLB条目的数量才能获得良好的性能，因此k不能太大。我们在计算中使用k = 32，只需要5位就可以对streamID进行编码。这意味着我们可以将一个更大的key进行编码，可到59位(= 64- 5)位，并结合streamamid编码为每个64位整数。

3.3 向量化归并操作的优化技术

在本节中，我们将介绍一些优化技术，以提高SIMD指令的效率，以及我们在第3.2节中采用的方法的总体执行性能。

3.3.1 增加数据并行度

正如在第3.2节中所讨论的，在编码在中间整数中的ID (streamID或index)的大小方面，我们的方法比现有的键索引方法有优势。通过利用这一优势，我们可以通过将一个key-streamID对编码成为32-bit int而不是64-bit int来增加每个SIMD指令中的数据并行性。

当对key-streamID编码成为32bit int时，我们可以只包含32bit key的一部分，具体方法为获取每个有序stream中key的最大值和最小值，根据它们的相似度进行位压缩。理想情况下，假设最小值为0x00000001，最大值为0x00000011，那说明我们很轻易的选择最低的8bit作为最重要的bits，作为key。但在极端情况，可能也会出现无法压缩的情况。部分key编码有可能出现冲突的情况，会导致output stream中record顺序不对，因此，在从input stream向output stream拷贝时就需要进行准确性检查，检查会花费一些开销，但在key冲突较小时这部分开销对比使用4-wide SIMD带来的收益很小，但若数据量很大，则说明partial key的冲突可能很频繁，此时进行partial key编码就不再合适了。

3.3.2 向量寄存器中的排序网络

向量寄存器中的向量merge操作在向量化归并排序是至关重要的。向量寄存器中的merge操作可以通过使用向量 min/max 指令和向量 permute指令以没有任何条件分支的方式实现。但具体的merge指令选择和处理器的类型和所支持的指令集是相关的。

在这项工作中，我们使用了一个更简单的数据流，适用于具有有限排列能力的指令集，例如SSE。我们的数据流可以仅通过min、max和rotate指令来实现，以在两个向量寄存器中合并32位整数值，如图5所示。尽管它用了更多的比较操作（相较于图1），但它避免了使用复杂的permute指令，从而带来了性能上的提升：

3.4 结构体的向量化CombSort

向量化CombSort方法使用在我们对小block进行排序时，考虑到数据量可能小到能够适配处理器的cache memory，随机内存访问的开销可能并不大。

向量化CombSort的优化方法和多路归并基本一致，可以使用key-index对进行编码并排序，并充分压缩中间数据大小以提高数据并行度。

3.5 对大Key记录排序

对大Key记录排序来说，技术基本上和我们前面设定的32bit key一致，只是中间数据长度增加后会减少数据并行度。同样可以提取key的关键部分进行partial-key排序，如果发现key冲突太过于频繁，可以将相同key的数据提取出来单独使用剩下的key值进行排序。

四、评估

参考论文原文

五、总结