基于FPGA的高性能变长合并排序加速器设计与实现

• 作者: 田森 庄耀宇 张俊杰 杨丹
• 来源期刊: 电子测量技术
• 关键词: FPGA 合并排序 变长 高性能 加速器
• 年，卷（期）: 2020,（21）
• 所属期刊栏目: 研究与设计|Research and Design
• 页码范围: 51-57
• 页数: 7页
• 分类号: TN802|TP331
• 语种: 中文
• DOI: 10.19651/j.cnki.emt.2004983

摘要

排序作为基本的计算问题,广泛应用于多种场景,如数据库、机器学习等,传统通用处理器实现的排序算法受限于cache与内存速度差异,性能提升有限,越来越多场景采用FPGA进行硬件加速.随着机器学习、人工智能等新兴技术的出现,需要处理的数据量呈指数增长,基于FPGA实现大数据量排序的排序器通常为合并排序器,合并排序器能够以迭代的方式实现大数据量排序,而现有基于FPGA实现的合并排序器不支持变长合并排序,在实际应用中仍有巨大挑战.针对现有的合并排序器的问题,提出了一种基于FPGA的高性能变长合并排序加速器,该排序结构通过对基本合并树添加控制逻辑的方式实现变长合并排序.为了使得该排序结构能够实现任意长度的大数据量排序,提出了一种新颖的数据存储结构以及读取控制方法,实现了变长合并树输入队列有序.为了验证提出的加速器的正确性以及评估加速器性能,在开发板KCU1500上实现了该结构,当排序70M个双精度浮点类型数据时,相比软件排序,提出的排序加速器性能是软件排序的6倍.