乒乓论文提纲

2022-11-15

论文题目：基于FPGA的乒乓线性归并排序算法的研究与实现

摘要：在大数据和物联网时代,数据在数据中心和一系列嵌入式设备中大多以数据流的形式进行交互,基于FPGA可以设计出高吞吐量、低能耗的多级流水结构,因此适用于各种连续到达的流式计算任务。同时排序是在数据库、图像处理、数据压缩等领域广泛应用的关键操作,具有流式计算的特点。对于流式数据的排序,基于元组序列的线性排序算法已被证明相对其他算法在整体性能上更有优势,作为一种新的FPGA高性能排序算法,这种算法拓展了数学上的序理论,并结合FPGA的结构特性,实现了全流水、高并发的设计。虽然基于元组序列的线性排序算法相较于其它排序算法更适应FPGA结构,同时具备良好伸缩性和可扩展性,但受限于片上寄存器存储资源,其在FPGA上只能排序少量数据。这限制了该算法在实际排序问题上的应用场景,因此设计一种能够排序更大规模的FPGA排序算法显得尤为重要。针对这个问题,本文在前期线性排序算法成果基础之上,提出了乒乓线性归并排序算法,该算法由乒乓线性排序器、BRAM FIFO、归并树三部分组成。在输入阶段,通过两个线性排序器的不断乒乓切换,将输入数据划分为不同的有序子序列,并缓存在BRAM FIFO中。之后以每两个周期一层的速度逐层构建归并树,构建完成之后每个周期可以输出n个最值。在归并树的设计中本文为每一层的n元数据结点添加了大小为2n的缓存单元来解耦层与层之间的依赖关系,与FPGASORT的工作相比本文的归并算法更具可伸缩性。整个线性归并排序器是全流水的,不考虑归并树构建的常数时间,与最先进的线性排序器一样,时间复杂度也是O（N）。基于所提出的算法,本文使用System Verilog语言实现了FPGA上的乒乓线性归并排序器。首先对基于元组序列的线性排序器进行了实现,并利用有限状态机（FSM）切换两个线性排序器的乒乓输入输出以及归并树的跳转状态,在归并树的实现中,本文设计了微核—结点单元（Node Unit,NU）,将结点内的比较,存储和结点间的通信进行封装。NU可以根据数据位宽、数据并行度和吞吐量进行自定义。所有的NU执行相同的操作,并且通过简单的通信组成了整个归并树。这有利于简化FPGA中的电路实现,使排序器可以达到更高的频率。与当前最新工作相比,乒乓线性归并排序器在保证吞吐量和可扩展特性的基础之上,提升了FPGA的片上数据处理能力。本文在Xilinx KCU1500 FPGA加速板上进行了实验,乒乓线性归并排序器与最新线性排序算法相比,在相同实验环境下最大数据处理量扩大227.2倍,同时吞吐量可达4.16 Gbps,与传统CPU上的快速排序算法相比吞吐量可提高29.71倍。

关键词：线性排序算法;现场可编程逻辑门阵列（FPGA）;流式数据;并行计算

学科专业：计算机应用技术

摘要

abstract

第1章绪论

1.1 研究背景及意义

1.2 研究现状

1.3 本文工作

1.4 论文结构与内容安排

第2章经典FPGA排序算法

2.1 排序网络算法

2.2 插入排序算法