沙漏排序：一种新颖的并行排序算法及其实现-计算机科学-机器学习-排序-算法.pdf

1

沙漏排序：一种新颖的并行排序算法及其

实现

DanielBáscones,BorjaMorcillo

摘要—排序是计算机科学中的一个基本问题。在许多过程排序。这些最终被优化为[6]到log复杂度和

中发挥作用，它在一个顺序机器上执行时受到由log定义log资源，但代价是更高的常数因子，这不幸地使它

的下界复杂度限制。通过增加并行比较数量的并行化技术，这一们在大多数情况下变得不切实际。最后，证明了在一个

限制可以降低到亚线性时间。然而，这增加了实现成本，从而限

CREWPRAM（并发读独占写并行随机存取机）架构

制了这些技术的应用。此外，随着数组大小的增加，在输入和输

本出排序器生成的数据之间移动大量数据会出现瓶颈。这可能会施下，并行归并排序算法[7]可以在log时间内使

译加比排序本身更严格的时间要求。在这篇论文中，提出了一种新用仅个处理器对数组进行排序。

型并行排序器，专门用于输入是并行而输出为串行的情况。设计在实践中，当问题规模较小且速度至关重要的时候

中随后在量子LDPC解码器的背景下通过FPGA实现和验证。

会使用硬件加速的排序网络[8]。对于较大的数据集通

1首个元素的输出延迟达到log，之后其余部分流出，整个排序

v时间为log。与其他并行排序方法不同，时钟速度不会随常使用的并行排序技术[9]会在通用硬件上工作：它们

6

2退化，并且资源与输入大小呈线性关系。通过顺序排序和巧妙的数据交错来划分、排序和合并

3数组。

6IndexTerms—排序，FPGA，并行化

1.然而，在需要对大数据集进行比log更快

7I.介绍的排序时存在一个缺口：由于资源使用的原因，硬件加

0

5速的排序网络变得不可行，而通用硬件上的并行技术

2ORTING算法是许多参与计算过程的核心。出现

:可能不够快。已经有人努力弥合这一缺口，并且有两

vS在数据库、调度、数据分析、网络、推荐系统、计

i种方法脱颖而出：1)遍历一个小的排序网络[10]。这将

x算生物学中，最近还出现在计算机图形或人工智能领

r硬件使用量减少了一个因子log，增加了线性时间的

a域。因此，它们是最受研究的算法家族之一，并且经常

延迟。2)通过选择输入/输出宽度并按块流式传输数据

是在任何基础算法课程中最先被研究的内容。

[11]来权衡时间和空间复杂度。[12]进一步探讨了这两

该正式证明概述了排序的最小log复杂

种方法，它们都利用仅以固定数量的数据并行处理

性，并由D.Knuth发表于[1]，同时还包括一组达到该

这一特点，减少了硬件的复杂性，并将处理时间增加了

界限的算法。归并排序（归功于JohnvonNe