标题： 小时钟排序：一种新的并行排序算法及其实现 显示英文标题

标题： Hourglass Sorting: A novel parallel sorting algorithm and its implementation

摘要： 排序是计算机科学中的基本问题之一。 在许多过程中起着重要作用，它在顺序机器上执行时受到$\mathcal{O}(n\log{n})$的下限复杂性限制。 由于并行化技术可以增加并行进行的比较次数，因此可以将此限制降低到次线性时间。 然而，这会增加实现成本，从而限制了这些技术的应用。 此外，随着数组大小的增加，在输入处需要移动大量数据以及在该排序器的输出处生成的数据时会出现瓶颈。 这可能会导致比排序本身更严格的时间要求。 在本文中，提出了一种新的并行排序器，用于输入为并行但输出为串行的特定情况。 然后在量子 LDPC 解码器的背景下，在 FPGA 上实现了该设计并进行了验证。 在第一个元素的输出上实现了$\log{n}$的延迟，之后其余元素陆续输出，总排序时间为$n+\log{n}$。 与其他并行排序方法相反，时钟速度不会随着$n$而下降，且资源随输入大小线性扩展。 显示英文摘要

摘要： Sorting is one of the fundamental problems in computer science. Playing a role in many processes, it has a lower complexity bound imposed by $\mathcal{O}(n\log{n})$ when executing on a sequential machine. This limit can be brought down to sub-linear times thanks to parallelization techniques that increase the number of comparisons done in parallel. This, however, increases the cost of implementation, which limits the application of such techniques. Moreover, as the size of the arrays increases, a bottleneck arises in moving the vast quantities of data required at the input, and generated at the output of such sorter. This might impose time requirements much stricter than those of the sorting itself. In this paper, a novel parallel sorter is proposed for the specific case where the input is parallel, but the output is serial. The design is then implemented and verified on an FPGA within the context of a quantum LDPC decoder. A latency of $\log{n}$ is achieved for the output of the first element, after which the rest stream out for a total sorting time of $n+\log{n}$. Contrary to other parallel sorting methods, clock speed does not degrade with $n$, and resources scale linearly with input size.