基于FPGA的浮点数线性排序器设计

李大琳 陈涛

摘要：本文实现了一种基于FPGA的可重构浮点数线性排序器。该排序器基于经典的插入排序算法，将插入排序算法并行化，在比较操作的实现上，采用浮点数比较核，使排序器总体性能较现有实现有明显提升。

关键词：浮点数;并行排序;可重构;插入排序

中图分类号：TP312 文献标识码：A 文章编号：1007-9416（2019）11-0143-02

0 引言

排序是计算机应用领域中非常重要、研究和应用都非常广泛的一类问题。例如，在数据处理、数据库、数据压缩、分布式计算、图像处理和计算机图形学中排序算法都有着非常广泛的应用[1]。为了充分提升排序问题的解决效率，提升算法运行速度，研究人员除了设计出针对不同问题的各种排序算法之外，还结合排序问题的可并行性特点，结合具体处理器（CPUs，GPUs以及FPGAs）的结构特点设计出了很多并行排序算法。其中，基于FPGAs的并行排序算法在性能、功耗比上表现得最优，但是现有排序器多数为定点数排序器，且在问题规模发生变化时，排序器适应性很差[2]。本文在插入排序算法的基础上，针对数据库研究中存在的大量浮点数排序问题，设计出一套基于Xilinx公司的FPGAs的可重构浮点数线性排序器。

1 排序器设计

排序算法的基础是待排序数据之间的比较。插入排序算法的基本原理是将新进数据与已有有序序列进行逐次比较，以获得新数据在队列中的位置，从而形成新的有序序列。本文将插入排序算法并行化，新的排序机制如图1所示。图中每一个节点代表一个比较/插入单元。单元的数量等于待排序数据的数量。新的待插入输入数据被广播到所有节点，用以和所有现有数据进行比较，并且找到新数据的正确位置。根据算法是要做升序排序或者降序排序，最右侧的节点获取最小或者最大值。待排数据从左侧进入，从序列右侧读出。在这个排序操作过程中，排序操作和数据输入操作同时进行。

以升序排序模式为例，在这种情况下，序列的最小值位于节点队列的最右侧节点。在其中任一个节点，得到一个从前序节点输入的数据a，以及当前节点数据b。为实现升序排序，节点执行条件判断：b≤a。新的待插入数据与所有节点中的数据进行比较。通常情况下，数据a 一般不是最大值，因此序列中的每一个节点内的数据关系可能是下面三个中的一个：

（1）c≥a： c被插入当前节点，a和其右侧所有节点被向右移动。（2）c≥b：c被插入到a的右侧，并且b以及其右侧所有节点右移。（3）c

2 排序器实现

2.1 浮点数排序节点设计

浮点数排序节点设计如图2所示。排序节点由浮点数比较器、多路选择器、数据存储寄存器和控制逻辑实现。在浮点数比较器的设计上，为了保证性能，本设计采用了Xilinx公司的浮点数比较IP核，该核可按照IEEE-754的数据标准实现32位标准浮点数和16位短浮点数比较，比较过程按浮点数格式分段进行，而不采用浮点数减法方式进行，因此在比较器构成资源使用和最终实现的最高主频上都比现有浮点数减法方案优化很多。

2.2 浮点数排序器的设计

N个排序节点串联构成一个排序器，N为待排序数据数量，如图3所示。有两个系统状态标签以流水线工作方式互联所有节点。排序器通过这两个标签来驱动节点内的控制逻辑，以确定新数据的准确插入位置。一个标签代表激活的节点，以进位标志（CY）的方式在节点中间传递。另外一个标签（LE）反映新的待插入数据和节点当前已有数据之间的比较结果。如果新数据比当前数据大，则LE标签复位，否者LE标签置位。

2.3 可重构排序器设计

本文所设计排序器使用SystemVerilog语言实现，所有排序器位宽、排序器节点数定义部分均使用参数化设计，使用者可以根据实际问题的规模重新定义参数后实现排序器。

3 测试结果

本文测试环境使用xilinx公司的Zynq7020芯片，芯片內包含两个Arm A9内核和Artex系列FPGA。试验把运行在A9内核上的标准插入排序算法和运行在Artex系列FPGA上的并行排序算法进行比较，时间结果显示，并行算法相对于经典算法的加速比达25倍。

4 结论

本文设计了一种基于FPGA的可重构浮点数线性排序器，在浮点数比较环节使用了Xilinx公司系统的浮点数比较核，在系统在面积和频率性能上都比现有使用浮点数减法运算的实现有明显提升。

参考文献

[1] Matai J，Richmond D，Lee D，et al.Resolve：Generation of High-Performance Sorting Architectures from High-Level Synthesis[C].the 2016 ACM/SIGDA International Symposium.ACM，2016.

[2] Marcelino R，Neto，Horácio，Cardoso，Joo M P.Sorting units for FPGA-Based embedded systems[J].Ifip International Federation for Information Processing，2008（271）：11-22.