基于CPU-FPGA异构系统的排序算法加速
2022年电子技术应用第1期
寇远博，邱泽宇，王 亮，黄建强
青海大学 计算机技术与应用系，青海 西宁810016
摘要：传统的排序方法主要以软件串行的方式实现，包括冒泡排序、选择排序等。这些算法往往采用顺序比较，运算的时间复杂度较高。近年来已经提出了一些并行度较高的排序算法，但是由于CPU的硬件特点，不能很好地利用这些算法的并行性。而FPGA具有良好的灵活性、并行性和集成性等特点，因此在FPGA上可以更好地发挥这些并行算法的优势，从而大大提高数据排序的实时性。基于此设计了一个CPU-FPGA异构系统，将一些排序算法移植到FPGA上，并进行功能验证和理论性能评估。结果显示，该系统对于并行性高的排序算法具有良好的加速效果，但逻辑资源消耗巨大，适用于实时性要求高的算法加速场景。
中图分类号：TP302.7
文献标识码：A
DOI：10.16157/j.issn.0258-7998.212431
中文引用格式：寇远博，邱泽宇，王亮，等. 基于CPU-FPGA异构系统的排序算法加速[J].电子技术应用，2022，48(1)：18-23，30.
英文引用格式：Kou Yuanbo，Qiu Zeyu，Wang Liang，et al. Sorting algorithm acceleration based on CPU-FPGA heterogeneous system[J]. Application of Electronic Technique，2022，48(1)：18-23，30.
文献标识码：A
DOI：10.16157/j.issn.0258-7998.212431
中文引用格式：寇远博，邱泽宇，王亮，等. 基于CPU-FPGA异构系统的排序算法加速[J].电子技术应用，2022，48(1)：18-23，30.
英文引用格式：Kou Yuanbo，Qiu Zeyu，Wang Liang，et al. Sorting algorithm acceleration based on CPU-FPGA heterogeneous system[J]. Application of Electronic Technique，2022，48(1)：18-23，30.
Sorting algorithm acceleration based on CPU-FPGA heterogeneous system
Kou Yuanbo，Qiu Zeyu，Wang Liang，Huang Jianqiang
Department of Computer Technology and Applications，Qinghai University，Xining 810016，China
Abstract：Traditional sorting methods are mainly implemented in software serial mode, including bubble sorting, selective sorting and so on. These algorithms often use sequential comparison, and the operation time complexity is relatively high. In recent years, some sorting algorithms with a high degree of parallelism have been proposed, but due to the hardware characteristics of the CPU, the parallelism of these algorithms cannot be used well. And FPGA has the characteristics of good flexibility, parallelism and integration, so the advantages of these parallel algorithms can be better utilized on FPGA, thereby greatly improving the real-time performance of data sorting. Based on this, the paper designs a CPU-FPGA heterogeneous system, transplants some sorting algorithms to FPGA, and performs functional verification and theoretical performance evaluation. The results show that the system has a good acceleration effect for sorting algorithms with high parallelism, but consumes huge logic resources, and is suitable for algorithm acceleration scenarios with high real-time requirements.
Key words :FPGA；sorting algorithm；heterogeneous system；algorithm acceleration
0 引言
排序问题是计算机科学中的经典问题，人们已对此提出了许多解决办法。而大规模数据的排序问题仍然是一个困难的问题。这一问题广泛发生在图计算领域，如社交网络、推荐系统等[1]。
传统的计算平台CPU和GPU存在计算效率低和高功耗的问题，不能很好地满足图计算领域的计算需求。为了解决这一问题，研究者们采用定制硬件平台来进行图数据的处理和算法的加速[2]。其中，基于FPGA的图计算加速器因满足复杂性高、数据规模大和基本操作多变的图计算的性能要求[3]受到青睐。
目前，国内外已经存在大量的基于FPGA的硬件加速器。GraphOps[4]提供了一个硬件库，可以让用户快速且轻松地构造用于图分析算法的节能型加速器。FlashGraph[5]在具有极端并行性的SSD文件系统之上实现了图处理引擎，它可以在性能损失最小的情况下利用SSD处理超大规模的图数据。FPGA开发门槛较高，但如果使用ThunderGP[6]，开发人员只需要使用C++编写API函数，ThunderGP就会自动生成一个高性能的加速器，极为方便。大规模世界图往往具有强大的社区结构，其中一小部分顶点比其他顶点的访问频率更高，利用这一潜在局部性，可以大幅提高图计算的性能[7]。除了单机图计算系统，一些典型的分布式的图计算系统，如ForeGraph[8]和FPGP[9]，也可以处理超大规模的数据。
本文详细内容请下载：http://www.chinaaet.com/resource/share/2000003903。
作者信息：
寇远博，邱泽宇，王 亮，黄建强
(青海大学 计算机技术与应用系，青海 西宁810016)
此内容为AET网站原创，未经授权禁止转载。