基于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://m.rjjo.cn/resource/share/2000003903。
作者信息：
寇遠博，邱澤宇，王 亮，黃建強
(青海大學 計算機技術與應用系，青海 西寧810016)
此內容為AET網站原創，未經授權禁止轉載。