写在文前

本文期望系统地介绍可并行硬件中的在线排序算法。传统在线排序算法对时间复杂度的度量主要基于通用架构，而本文介绍的算法将面向可高度并行的异构硬件优化，并且笔者认为跳脱出传统硬件思维能启发对排序算法的更深层次的理解。本文行文会介于综述与课程之间，会循序渐进地向不了解的读者介绍算法，同时也会介绍多种现有的算法理论。

术语表

虽然本文作为课程一般不出现前置的算法表，但因为涉及到硬件知识较多，在这里列出

术语/符号	意义
N	指排序数组长度/键个数
排序键/键/Key	指排序数组中的一个元素
FPGA	现场可编程门阵列
FF	触发器/寄存器
RAM	随机存取存储器
BRAM	块存储器，以块状封装
IO	输入输出模块/单元
FIFO	硬件上指寄存器组成的队列结构，只需要一个时间周期就可以执行push或pop
时间周期	简单理解为同步硬件进行执行的最小时间单位，等同于传统时间复杂度的单位
串行操作	硬件上指必须等待前序硬件输出的操作

基础介绍

1.1 什么是在线排序算法？

1.1.1 在线算法

笔者认为算法问题往往可以总结为一个（可能带有状态机）的输入输出系统。而传统算法问题往往不考虑输入数据时的延迟，认为所有输入数据都可以在可以忽略的时间内输入算法运算模块。但在现实的计算机应用环境中，如果输入数据量巨大导致需要从大容量低速外部存储（例如机械硬盘）中提取，或算法本身时间复杂度就为线性导致输入数据时间不可忽略，那么就需要尽量在部分数据到达时，就开始一部分的算法计算，节省等待所有数据的时间。

同时，也有部分算法问题本身的设置就需要在线算法进行解决，典型的问题设置是算法需要对每个单独的数据输入做出实时的响应。例如操作系统中的页面调度问题，需要算法实时响应页面的调取、替换请求，而不是等待所有请求到达后再进行全局最优解的计算。

因此，笔者认为在线算法主要有两种形式：

基于现实计算硬件的瓶颈优化的在线算法

在通用计算架构下的例子：插入排序
基于问题设置原生的在线算法

在通用计算架构下的例子：LRU 替换算法

需要指出的是，本文介绍的算法属于第一种，是基于可并行硬件的内存访问瓶颈与内部存储空间限制做出的优化算法。

在线算法往往会讨论“竞争比”，指在线算法相对于对应的离线最优算法复杂度的放大倍数。但在本文中不会讨论，因为如果完全无视硬件上的带宽容量瓶颈，在可并行硬件上构建出的“离线算法”时间复杂度为，无法与在线算法形成竞争比，且这样的算法基本不可能实现（在下文会详细讨论）。

1.1.2 排序算法

排序算法本身不需要过多赘述，但在这里我们要限定本文讨论的排序算法范围。

本文讨论的排序算法限于面向没有显式上下界的，连续的，可能非数字的排序键的算法。因此桶排序、基数排序等排序算法是不符合的，只能使用纯基于比较的算法，比如归并排序、插入排序。

同时我们希望排序算法拥有以下“好”的特性：

稳定：如果输入数据有两个字段具有相同的键，它们以相同的顺序输出，那么排序是稳定的。
原位：一个包含N个元素的数组可以使用N个元素存储空间进行排序，也有一些算法在排序过程中需要额外的存储。
适应：对于已经排序的数据来说是有效的。如果数据已经排序，一些算法可能会运行得更快，即只需要O(N)的时间复杂度。

课后习题：

请思考下，我们学过的什么排序算法能达到上述特性？为什么？

1.1.3 在线排序算法

基于上文对在线算法的解析，我们可以很容易地得出在线排序算法所具有的特征：

对于一个输入的代排序数组，其每个排序键是独立到达算法模块的
对于一个输出的已排序数组，其每个排序键是独立输出算法模块的

针对硬件来说，独立到达/输出指的便是一个时间周期内只能到达/输出k个数且，可以理解为，排序算法的时间复杂度需要加上额外的。

如果读者看到这里并仔细思考，可能会有以下疑惑：传统排序算法其实完全符合在线排序算法的问题设置，不需要额外改变，比如归并排序。归并排序本身复杂度为，增加并不会改变整体复杂度。且我们还有一个更优的方案：因为第一层归并为两两比较归并，因此每当有两个数到达，我们就进行比较，当数据完全输入后，我们恰好也完成了第一层的归并，时间复杂度甚至不需要加上数据输入的额外的。

这样的疑惑是正确的，这也是为什么我们一般不会讨论在通用计算架构上的在线排序算法。但在可并行硬件上则不同，我们期望排序算法的平均时间复杂度达到（甚至更低），因此我们不能忽略输入数据的延迟。至于如何设计的排序算法，下文会详细介绍。

1.2 可并行硬件

需要指出的是，“可并行硬件”这一概念在笔者的知识范围内并没有一个严格的学术定义，基本可以理解为相对于通用计算架构（传统CPU）存在的概念。因为“硬件”的定义本身就可以很宽泛，“可并行硬件”广义上可以指任何在一个时钟周期内进行多重逻辑操作的硬件。

本文讨论的“可并行硬件”指的是一类现有的量产硬件，如现场可编程门阵列 (FPGA)），图形处理单元(GPU)等。这一类硬件主要有以下特征：

较高的并行性

GPU或FPGA都能在同一时间周期内进行多次算数操作，运算次数能到达 $～$ ，相比之下CPU的多核能力一般只支持~。因此如果能利用其并行能力设计并行算法，我们能取得数量级级别的性能提升。
较低的运行频率

虽然并行硬件在某一时间周期内的并行性上远超过CPU，但是往往其时间周期较CPU更长。GPU频率一般比CPU慢1～2倍，FPGA则一般比CPU慢10倍以上。因此如果无法设计良好的并行算法，其最终运算效率可能不如CPU。

本文的主要算法介绍不会与硬件强耦合，仍然是介绍算法思想为主。但是具体的实现细节介绍过程中将以FPGA为例，但算法的设计是兼容当今的GPU硬件的。

算法介绍

本节将开始对可并行硬件中的在线排序算法进行介绍。

2.1 并行在线排序

2.1.1 硬件中的比较并行

本文讨论的排序算法的核心是比较，进行比较的次数直接决定了在通用计算架构上的时间复杂度，因为在一个单位时间内，CPU只能执行一个（部分向量指令中可以为多个，但仍有限）比较操作。例如传统插入排序需要次比较，所以时间复杂度为；传统归并排序通过合理利用已经比较过的信息，让比较次数降低到，所以时间复杂度降低到。

但在可并行硬件上，我们能够很简单地在同一时间周期内进行多次比较操作。在 FPGA 中，理论上能实现数量级的比较器同时并行，因此仅从比较的角度分析的话，并行硬件能在甚至时间复杂度内完成排序。

课后习题：

请思考下，即使你能拥有诸多比较器同时运行，真的就能让排序算法时间无限缩短吗？如果让你设计并行算法，你会如何设计？

2.1.2 硬件中的排序瓶颈

但是仔细分析排序算法，即便所有比较操作能够并行，我们仍然会遇到诸多瓶颈阻止我们真的将时间复杂度降低到，主要能总结为以下几点：

瓶颈1：有部分比较操作是必须串行的

在传统的基于比较的排序算法中，大多数比较操作之间是有依赖关系的，只能等待前序比较完成后才能完成。例如归并排序中，当前层的比较操作必须在下层归并的比较操作完成后才能开始。这限制了比较操作的完全并行。
瓶颈2：外部数据输入带宽有限

如果整体算法需要在时间复杂度内完成，那么要求所有数据必须要在有限单位时间内到达。但是这在不管何种硬件中是不现实的，即使数据能存储在主存中，传统主存的速度仅能支持一个时间周期内读取8~16个64位排序键。这也是前文提到的需要引入在线算法的原因之一，数据输入的时间复杂度应该为。
瓶颈3：算法内部数据访问带宽有限

内部数据访问的瓶颈不同于第2点中提到的数据输入数率，这里指的是当数据已经完全到达了算法模块中，算法模块中内部的数据访问速度会高于数据输入，但仍然是有限的。但如果整体算法需要在时间复杂度内完成，那么意味着所有数据必须在有限周期内被任意比较器访问与写回，这对于小量数据是可能的是不现实的。

但需要注意的是，虽然任意数据在单一周期内被任意比较器访问是不现实的，但所有数据在一周期内被访问是可能的，只要每个数据对应的比较器是有限的。

2.1.3 硬件中的非在线排序

为了应对上述的三点瓶颈，得到小于通用计算架构中时间复杂度的排序算法，有一些针对硬件的非在线排序算法被提出。典型的有奇偶排序网络。下图展示了奇偶排序网络的运行过程：

其中条横线代表一个排序键，每条连接两个排序键的竖线代表一次比较与交换操作，每两条竖向虚线之间代表一个时间周期。

奇偶排序网络实际上是归并排序的一种优化版本，每次比较交换操作都会把对应的两个数按照排序需求顺序排好。

在不考虑数据输入时间的情况下，这个算法需要的比较次数为，但因为每个时间周期内有次比较同时在执行，因此最终时间复杂度为，这显然小于的典型排序算法时间复杂度，甚至小于，我们在并行硬件上实现了CPU上望尘莫及的排序速度！

这告诉我们，在并行硬件中的排序算法设计不一定要最小化比较次数，而更应该关注如何在单位时间内并行更多的比较操作，减少比较操作之间的依赖。

从图中可以看到每个时间周期内在保证每个排序键仅能访问一次的前提下，比较操作尽可能地并行了，这尽可能地解决了瓶颈1。但是这个算法因为并非是在线算法，需要所有数据已经到达排序模块后才能开始，所以并没有解决瓶颈2。同时因为从图中可以看出，这个算法需要所有的排序键在同一周期内可以被任意比较器访问，所以并没有完全解决瓶颈3。

因此这个算法虽然能达到极快的排序速度，但是因为受到瓶颈3的影响，这个算法无法扩展到常见的排序键长度问题上，仅能支持数量级的排序键数量。同时因为并非在线算法，所以实际时间复杂度为。

2.2 在线插入排序

为了完全解决瓶颈2与瓶颈3，我们需要引入在线排序算法。

2.2.1 算法描述

从零设计出这个在线算法是困难的，特别是针对硬件不太了解的读者。但是笔者可以将这个思考过程尽量抽象化：

插入排序本身需要次比较，但如果我们能在每个时间周期中达到次比较的并行，那么我们最终能达到时间复杂度的排序算法。因此，我们至少需要N个比较器。
而因为我们需要满足在线算法的定义，因此我们需要让数据在输入的过程中就开始被处理。在计算机科学中，这样的边输入边输出的结构通常被抽象为一个队列。
因为我们要尽量让比较器并行，因此可以让比较器均匀地分布在队列中，对队列中存在的元素进行操作。队列的长度应该就是比较器的个数，也就是N。

于是我们脑中应该有了一个在线插入排序器的雏形：一个队列结构，数据从一端流入，最终从另一端流出，因为队列长度为N，因此一个排序键从流入到流出所需的时间是，因为所有排序键是连续输入排序器中的，所以整体排序时间也是。

上面的设想在添加一些细节后，就可以得到真正的在线并行插入排序结构，在硬件学界，它称之为显式脉冲阵列：

显式脉冲阵列的整体结构与上文中的抽象相差不远，是由N个排序单元与相接的FIFO组成的串行结构。不同的是，队列中的每个单元不仅仅是一个比较器：其中缘由也很简单，比较器终究需要至少两个操作数，而队列是一进一出，必然需要额外结构来支撑比较。

具体从图中来说，每个单元中接收输入FIFO 的输入，从输出FIFO 输出，且除了一个比较器外，还有一个用于存储一个排序键的寄存器，设其中存储的排序键为。阵列中的每个单元都是相同的。

假设需要的排序顺序为升序。每当输入一个排序键，会与当前中的进行比较，较小的值会被输入到中，而较大的值会成为新的。抽象来说，每个排序单元执行的指令为：

while in >> x:
	l = min(x, l);
	out << max(x, l);

需要注意的是，当某个单元流出一个排序键时，其他所有单元也同时在流出一个排序键，所有具有值单元在同一时间周期内是完全并行的。

第号单元的输出结果传递给线性阵列的下一个（即第号）单元的输入（因为号的就为号的）。
从排序键的角度来说，当某个排序键输入阵列中，它会依次与存储在每个单元中的值进行比较，直到找到正确的位置，这与传统插入排序的思想相似。如果新的输入排序键大于阵列所有的值，它将停在第一个单元，其他所有值将向尾部平移一个单元；如果新的输入排序键小于阵列所有的值，此值会在阵列中一直传输，在N个时间周期后会被存放在最尾部的单元中。当所有的数据都处理完时，最小的元素存放在第N−1号单元，此时让阵列依次流出值即可。

可以看出，因为算法可以在数据输入过程中进行比较排序，解决了瓶颈2，同时因为每个比较器只会与，因此本算法突破了瓶颈3。

2.2.2 算法示例

以下给出一个算法执行的简单例子，假设输入的数据是 4、5、1、2，我们希望进行升序排序，我们有以下显式脉冲阵列

graph LR
0[unit 0 ] --> 1[unit 1 ]
1[unit 1 ] --> 2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]

时间周期 0：

graph LR
i[4 5 1 2 ] --> 0[unit 0 ]
0[unit 0 ] --> 1[unit 1 ]
1[unit 1 ] --> 2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 1：
单元0 输入 2，2 暂存

graph LR
i[4 5 1 ] --> 0[unit 0 \n 2]
0[unit 0 \n 2] --> 1[unit 1 ]
1[unit 1 ] --> 2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 2：
单元0 输入 1，2 暂存，1输出

graph LR
i[4 5  ] --> 0[unit 0 \n 2]
0[unit 0 \n 2] --> |1|1[unit 1]
1[unit 1] --> 2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 3：
单元0 输入 5，5 暂存，2输出
单元1 输入 1，1 暂存

graph LR
i[4 ] --> 0[unit 0 \n 5]
0[unit 0 \n 5] --> |2|1[unit 1 \n 1]
1[unit 1 \n 1] --> 2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 4：
单元0 输入 4，5 暂存，4输出
单元1 输入 2，2 暂存，1输出

graph LR
i[ ] --> 0[unit 0 \n 5]
0[unit 0 \n 5] --> |4|1[unit 1 \n 2]
1[unit 1 \n 2] --> |1|2[unit 2 ]
2[unit 2 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 5：
单元1 输入 4，4 暂存，2输出
单元2 输入 1，1 暂存

graph LR
i[ ] --> 0[unit 0 \n 5]
0[unit 0 \n 5] --> 1[unit 1 \n 4]
1[unit 1 \n 4] --> |2|2[unit 2 \n 1]
2[unit 2 \n 1 ] --> 3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 6：
单元2 输入 2，2 暂存，1输出

graph LR
i[ ] --> 0[unit 0 \n 5]
0[unit 0 \n 5] --> 1[unit 1 \n 4]
1[unit 1 \n 4] --> 2[unit 2 \n 2]
2[unit 2 \n 2 ] --> |1|3[unit 3 ]
3[unit 3 ] --> o[-]

时间周期 7：
单元3 输入 1，1 暂存

graph LR
i[ ] --> 0[unit 0 \n 5]
0[unit 0 \n 5] --> 1[unit 1 \n 4]
1[unit 1 \n 4] --> 2[unit 2 \n 2]
2[unit 2 \n 2 ] --> 3[unit 3 \n 1]
3[unit 3 \n 1 ] --> o[-]

时间周期 7+4=11：
单元3 2 1 0 依次输出暂存值

graph LR
i[ ] --> 0[unit 0]
0[unit 0] --> 1[unit 1]
1[unit 1 ] --> 2[unit 2]
2[unit 2] --> 3[unit 3]
3[unit 3] --> o[5 4 2 1]

2.3 在线归并排序

2.3.1 算法描述

前文介绍了基于插入排序改造的并行在线算法。但其实还有一种基于归并排序的在线并行排序算法。其同样是由一个个排序单元与相联的FIFO组成。但不同的是，因为每个单元所做的是归并操作，所以接收两个输入FIFO 与，输出为一个FIFO ，其单元结构可以抽象为：

如果进行升序排序，单元每次从两个输入FIFO中挑选较小的一个输入到输出FIFO中。

而排序器整体设计也不会是串行的，而是树状的（思考下传统归并排序的执行过程就能理解），下图给出了一个针对的归并排序网络。

每个黑色箭头代表一个FIFO，每个灰色横条代表一个归并排序单元。输入数据从左向右（或从右向左）依次填入FIFO。可以看到需要个比较器。每个时间周期内，所有单元都会挑选两个输入 FIFO 中较小的数进行输出，因此图中最下端也就是最终输出端每周期会输出1个排序键。

此算法需要的比较次数与传统归并排序相等，为，但每个时间周期中有个比较器同时并行，因此整体时间复杂度依然为。

课后习题：

为什么每个时间周期中并行的排序器数量不是和插入排序算法一样的个？是什么导致了有排序器无法并行？

提示：可以从归并排序的输出向输入反向考虑

2.3.2 算法示例

以下给出一个算法执行的简单例子，假设输入的数据是 4、5、1、2，我们希望进行升序排序，我们有以下归并排序器：

graph TD
i0[-] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] --> 2[unit 2]
1[unit 1] --> 2[unit 2]

时间周期0：
单元0 0输入4 无输出

graph TD
i0[-] -->|4|0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] --> 2[unit 2]
1[unit 1] --> 2[unit 2]

时间周期1：
单元0 1输入5 输出4
单元2 0输入4 无输出

graph TD
i0[-] --> 0[unit 0]
i1[-] -->|5|0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] -->|4|2[unit 2]
1[unit 1] --> 2[unit 2]

时间周期2：
单元0 输出5
单元1 0 输入1 无输出
单元2 0输入5 无输出

graph TD
i0[-] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] -->|1|1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] -->|5 4|2[unit 2]
1[unit 1] --> 2[unit 2]

时间周期3：
单元1 1 输入2 输出1
单元2 1输入1 无输出

graph TD
i0[-] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] -->|2|1[unit 1]
0[unit 0] -->|5 4|2[unit 2]
1[unit 1] -->|1|2[unit 2]

时间周期4：
单元1 输出2
单元2 1输入2 输出 1

graph TD
i0[4] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] -->|5 4|2[unit 2]
1[unit 1] -->|2|2[unit 2]
2[unit 2] --> o[1]

时间周期5：
单元2 输出 2

graph TD
i0[4] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] -->|5 4|2[unit 2]
1[unit 1] --> 2[unit 2]
2[unit 2] --> o[2 1]

时间周期6：单元2 输出 4

graph TD
i0[4] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] --> 1[unit 1]
0[unit 0] -->|5|2[unit 2]
1[unit 1] -->2[unit 2]
2[unit 2] --> o[4 2 1]

时间周期7：
单元2 输出 5

graph TD
i0[4] --> 0[unit 0]
i1[-] --> 0[unit 0]
i2[-] --> 1[unit 1]
i3[-] -->1[unit 1]
0[unit 0] -->2[unit 2]
1[unit 1] -->2[unit 2]
2[unit 2] --> o[5 4 2 1]

课后习题：

在学习完两种传统排序算法改造的在线并行算法后，请思考下为什么快速排序无法改造为在线并行算法？

提示：可以从瓶颈入手思考

总结与思考

本文探讨了针对基于比较的在线排序算法，在不局限单比较器后可以进行的改良。核心期望读者对制约传统排序算法时间复杂度的核心问题有更深的理解，并且了解当引入并行性考虑后，我们应该如何设计算法。

思考题：

在GPU架构中，FIFO结构并不能被高效实现，但是GPU拥有比FPGA更快的内部数据交换速度（见瓶颈3），我们能使用怎样的并行排序算法？可以查阅 Nvidia Cuda 库中的排序实现源码进行学习。

kaihongH的playground

可并行硬件中的在线排序算法
点击返回顶部

首页

归档

可并行硬件中的在线排序算法

术语表