一种基于归并树的全排序加速器及应用

摘要

本发明的基于归并树的全排序加速器，包括：主控模块，接收运算信号，并根据所述运算信号确定排序、合并的次数、排序点数以及读写地址；输出控制信号，控制合并的开始和结束；运算单元，由若干比较器组成，根据所述运算信号执行比较逻辑运算，输出中间结果；FIFO存储单元，由若干寄存器组成，接收所述中间结果并存储，根据所述传输信号，执行中间结果的读写操作；主控制器与每一比较器、寄存器形成映射形成一个结点，所有结点形成归并树的处理结构。有益效果：资源开销较小使用更加灵活，同时有良好的并行性来满足高吞吐量系统的需求。

权利要求

1.一种基于归并树的全排序加速器，其特征在于包括：

主控模块，接收运算信号，并根据所述运算信号确定排序、合并的次数、排序点数以及读写地址；输出控制信号，控制合并的开始和结束；

运算单元，由若干比较器组成，根据所述运算信号执行比较逻辑运算，输出中间结果；

FIFO存储单元，由若干寄存器组成，接收所述中间结果并存储，根据所述控制信号，执行中间结果的读写操作；

主控制器与每一比较器、寄存器形成映射形成一个结点，所有结点形成归并树的处理结构，主控模块根据排序点数确定需要调用归并树的次数，并根据运算信号输出传输信号，所述传输信号更改主控模块与FIFO存储单元的互联。

2.根据权利要求1所述的基于归并树的全排序加速器，其特征在于，所述传输信号在存储单元不满时向FIFO存储单元写入数据；在存储单元不空时向FIFO存储单元读数据。

3.根据权利要求1所述的基于归并树的全排序加速器，其特征在于，主控模块在点数为N时，调用次数为log8N，并且主控模块会根据当前归并次数确定所述读写地址。

4.根据权利要求1所述的基于归并树的全排序加速器，其特征在于，还包括读写控制模块，所述中间结果通过读写控制模块进行传输，读写控制模块包括：读数据控制器，根据所述传输信号控制SRAM存储单元的读数据使能信号和读数据地址；

写数据控制器，根据所述归并树的根结点对应寄存器中的中间结果，控制SRAM的写数据使能信号和写数据地址；

SRAM存储单元，根据写数据使能信号、写数据地址进行写数据操作，根据读数据使能信号和读数据地址进行读数据操作；

内存交换开关，根据读数据使能信号与写数据使能信号变换主控制器与SRAM存储单元间的读写接口。

5.根据权利要求1所述的基于归并树的全排序加速器，其特征在于，所述归并树为一个满二叉树结构。

6.根据权利要求5所述的基于归并树的全排序加速器，其特征在于，所述运算单元由7个比较器组成。

7.根据权利要求6所述的基于归并树的全排序加速器，其特征在于，所述归并树为一个

3层的满二叉树结构，归并树的终端结点存储的为FIFO存储单元对应于当前终端结点的中间结果，并且终端结点将该中间结果作为对应比较器的输入值，其余结点存储的为当前结点的子结点对应比较器的输出值，所述的终端结点存储的中间结果被赋给父结点的寄存器时，形成所述传输信号，向FIFO存储单元发送读数据请求。

8.如权利要求1-7任一项所述的基于归并树的全排序加速器，其特征在于所述全排序加速器可应用于任意点数的快速全排序。

说明书

一种基于归并树的全排序加速器及应用

技术领域

[0001] 本发明涉及全排序数字集成电路设计，尤其涉及一种基于归并树的全排序加速器及应用。

背景技术

[0002] 排序是一个经典问题, 其功能是将一个无序的数据序列调整为一个有序序列。随着计算机的问世及其蓬勃发展, 排序已成为计算机程序设计中的一种基本运算。在现今的计算机系统中, 花费在排序的时间占系统CP U 运行时间的很大比重。据统计, 在计算机完成的所有工作中有25% -50%涉及到数据的排序, 特别是一些商用计算机, 其批处理系统中15% -70% 的CPU时间用在排序上。排序的研究价值不仅在于它有很重要的实用意义, 而且还在于它所解决的问题涉及大量数据元素的相关操作, 因而不可避免地使解决该问题的复杂性和难度增加。各种内、外排序的研究与应用充分证实了这一点。

[0003] 目前，在数字电路领域多采用较大的排序网络实现较快的归并和基数排序，或者采用消耗资源较少但并行度不高、速度较慢的冒泡和堆排序来实现向量的全排序。一般排序网络需要大量的比较器和寄存器，性能很高但支持的排序点数固定、开销很大，即数字电路设计所消耗的逻辑资源多、芯片面积大。冒泡排序虽然消耗的资源很少，但运算时间会随着数据量的增大指数级地增长。

发明内容

[0004] 本发明的目的是克服上述背景技术的不足，提供一种基于归并树的排序树加速器，其支持点数可变的、资源消耗较少的、排序性能较好的、支持并行和流水操作的全排序功能，为达到上述目的，本发明的技术方案是这样实现的：

[0005] 所述基于归并树的全排序加速器，包括：

[0006] 主控模块，接收运算信号，并根据所述运算信号确定排序、合并的次数、排序点数以及读写地址；输出控制信号，控制合并的开始和结束；

[0007] 运算单元，由若干比较器组成，根据所述运算信号执行比较逻辑运算，输出中间结果；

[0008] FIFO存储单元，由若干寄存器组成，接收所述中间结果并存储，根据所述传输信号，执行中间结果的读写操作；

[0009] 主控制器与每一比较器、寄存器形成映射形成一个结点，所有结点形成归并树的处理结构，主控模块根据排序点数确定需要调用归并树的次数，并根据运算信号输出传输信号，所述传输信号更改主控模块与FIFO存储单元的互联。

[0010] 所述基于归并树的全排序加速器的进一步设计在于，所述传输信号在存储单元不满时向FIFO存储单元写入数据；在存储单元不空时向FIFO存储单元读数据。

[0011] 所述基于归并树的全排序加速器的进一步设计在于，所述主控模块在点数为N时，调用次数为 ，并且主控模块会根据当前归并次数确定所述读写地址。

[0012] 所述基于归并树的全排序加速器的进一步设计在于，还包括读写控制模块，所述中间结果通过读写控制模块进行传输，读写控制模块包括：

[0013] 读数据控制器，根据所述传输信号控制SRAM存储单元的读数据使能信号和读数据地址；

[0014] 写数据控制器，根据所述归并树的根结点对应寄存器中的中间结果，控制SRAM的写数据使能信号和写数据地址 ；

[0015] SRAM存储单元，根据写数据使能信号、写数据地址进行写数据操作，根据读数据使能信号和读数据地址进行读数据操作；

[0016] 内存交换开关，根据读数据使能信号与写数据使能信号变换主控制器与SRAM存储单元间的读写接口。

[0017] 所述基于归并树的全排序加速器的进一步设计在于，所述归并树为一个满二叉树结构。

[0018] 所述基于归并树的全排序加速器的进一步设计在于，所述运算单元由7个比较器组成。

[0019] 所述基于归并树的全排序加速器的进一步设计在于，所述归并树为一个3层的满二叉树结构，归并树的终端结点存储的为FIFO存储单元对应于当前终端结点的中间结果，并且终端结点将该中间结果作为对应比较器的输入值，其余结点存储的为当前结点的子结点对应比较器的输出值，所述的终端结点存储的中间结果被赋给父结点的寄存器时，形成所述传输信号，向FIFO存储单元发送读数据请求。

[0020] 如所述的基于归并树的全排序加速器，提供一种基于归并树的全排序加速器的应用，所述全排序加速器可应用于任意点数的快速全排序。

[0021] 本发明的有益效果为：

[0022] 本发明提供的基于归并树的全排序加速器的有益效果在于资源开销较小使用更加灵活，同时有良好的并行性来满足高吞吐量系统的需求；归并树的结构在读数据控制器的协调下能够在的时间复杂度能实现N点向量数据的全排序。

附图说明

[0023] 图1是整个全排序加速器的结构示意图。

[0024] 图2是由7个比较器组成的归并树的结构示意图。

[0025] 图3是由7个比较器组成的归并树的原理示意图。

[0026] 图4是基于归并树的全排序加速器的数据流示意图。

[0027] 图5是读数据控制器支持的功能示意图。

[0028] 图6基于归并树的全排序加速器与冒泡排序和堆排序的性能对照示意表。

具体实施方式

[0029] 下面结合附图和具体实施方式对本申请作进一步详细的说明。

[0030] 如图1，基于归并树的全排序加速器，主要由主控模块、运算单元以及FIFO存储单元组成。主控模块，接收运算信号，并根据运算信号确定排序、合并的次数、排序点数以及读写地址；输出控制信号，控制合并的开始和结束；运算单元，由若干比较器组成，根据运算信号执行比较逻辑运算，输出中间结果；FIFO存储单元，由若干寄存器组成，接收中间结果并存储，根据传输信号，执行中间结果的读写操作。主控制器与每一比较器、寄存器形成映射形成一个结点，所有结点形成归并树的处理结构，主控模块根据排序点数确定需要调用归并树的次数，并根据运算信号输出传输信号，传输信号更改主控模块与FIFO存储单元的互联。

[0031] 上述传输信号在存储单元不满时向FIFO存储单元写入数据；在存储单元不空时向FIFO存储单元读数据。

[0032] 基于归并树的全排序加速器的进一步设计在于，主控模块在点数为N时，调用次数为 ，并且主控模块会根据当前归并次数确定读写地址。

[0033] 本实施例的基于归并树的全排序加速器还包括读写控制模块，中间结果通过读写控制模块进行传输，读写控制模块主要由读数据控制器、写数据控制器、SRAM存储单元以及内存交换开关组成。读数据控制器，根据传输信号控制SRAM存储单元的读数据使能信号和读数据地址；写数据控制器，根据归并树的根结点对应寄存器中的中间结果，控制SRAM的写数据使能信号和写数据地址；SRAM存储单元，根据写数据使能信号、写数据地址进行写数据操作，根据读数据使能信号和读数据地址进行读数据操作；内存交换开关，根据读数据使能信号与写数据使能信号变换主控制器与SRAM存储单元间的读写接口。

[0034] 如图1所示的基于归并树的全排序加速器，提供一种基于归并树的全排序加速器的应用，全排序加速器可应用于任意点数的快速全排序。

[0035] 以下给出一具体示例，该示例中运算单元由7个比较器组成。归并树为一个3层的满二叉树结构，归并树的终端结点存储的为FIFO存储单元对应于当前终端结点的中间结果，并且终端结点将该中间结果作为对应比较器的输入值，其余结点存储的为当前结点的子结点对应比较器的输出值，归并树的终端结点存储的中间结果被赋给父结点的寄存器时，形成传输信号，向FIFO存储单元发送读数据请求。在整个方案的主要步骤如图4所示：

[0036] （1）将N个数据均匀放入8个存储体（存储体1 存储体8）中；~

[0037] （2）每次读取每个存储体的一个数进行排序，得到N/8个数据长度为8的有序向量，均匀放入8个存储体(存储体9 存储体16)中；~

[0038] （3）每次读取每个存储体(存储体9 存储体16)的一个8长度的有序向量进行合并。~
得到N/64个数据长度为64的有序向量，均匀放入8个存储体(存储体1 存储体8)中；
~

[0039] （4）重复上述（2），（3）步骤，直到读取每个存储体的一个N/8长度的有序向量进行合并。得到1个数据长度为N的有序向量，这就是最终的结果。

[0040] 主控模块在图1中用①标明。主控模块负责以下三个功能：根据点数确定排序/合并的次数；更改控制单元与存储体的互联；控制合并的开始和结束。

[0041] 归并树在图1中用⑤标明，其结构如图2所示。其中寄存器的具体结构如下：其中最高位为1位有效信号，第33到63位存放数据在原向量中的位置，低32位存放原数据。

[0042] 归并树的具体工作流程如图3所示，（1）一个二叉树的两个子结点的数据进入比较器，根据比较器结果确定这个二叉树的结点存入较大（小）的数，以及它在原向量中的位置。（2）一旦最上面的叶结点的数据成为比较器输出，它的原位置的最高位就置为0，表示向外请求读入新数据。（3）一旦一个结点成为比较器输出，它的所有子结点就向下推进。整个流程实现了8个有序序列的归并。

[0043] 在图1中的④标明了FIFO，FIFO在不满时向读数据控制器发送读数据请求并写入数据；在不空时则根据归并树的读数据请求来读出数据。这样保证在归并树请求数据时能够立刻得到数据。

[0044] 读数据控制器在图1中用②标明。它主要负责根据当前需要归并的点数和FIFO的空满情况来向FIFO写数据。对于归并的点数，它支持如图5的两种存储体数据不对齐的情况：（a）每个存储体每次合并m点，但有几个存储体k多合并一次；(b)每个存储体合并一次，但有一个存储体合并的点数与其他不同。对于FIFO只要FIFO不满并且给出的点数还没达到归并的点数，就向SRAM请求读数据并写入FIFO中。

[0045] 写数据控制器在图1中用③来标明。写数据控制器根据归并树当前的归并次数来确定将结果数据写入的存储体位置，从而保证结果数据以固定长度为单位均匀写入各个存储体中，以便下次并行读取。

[0046] 内存交换开关在图1中用⑥来标明。内存交换开关负责根据当前的归并次数切换所需读写的存储体。

[0047] 为证明进一步验证本设计在实际应用中的性能，以一款冒泡排序和堆排序作为参照，说明本发明的优势。

[0048] 本实施例完成的设计可支持长度为8-32K的浮点数全排序，在40nm CMOS工艺下的工作主频达1GHz。图6展示了本实施例与传统冒泡排序和堆排序的性能对照。可见本设计的基于归并树的全排序加速器在实施应用中有很好的性能优势，并随着序列长度的增加性能优势越明显，序列长度为32K点时与堆排序的加速比可达到2.76，与冒泡排序的加速比可达3016。

[0049] 本发明介绍了一种全排序数字集成电路设计。其特点是速度快、点数灵活可变、所用资源少（7个比较器），在数据量较大的数字信号处理中如数据检索，雷达信号分析等能发挥重要作用。

[0050] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。