《電子技術應用》
您所在的位置:首頁 > 其他 > 設計應用 > 基于CPU-FPGA異構系統的排序算法加速
基于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.
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.viuna.cn/resource/share/2000003903




作者信息:

寇遠博,邱澤宇,王  亮,黃建強

(青海大學 計算機技術與應用系,青海 西寧810016)




wd.jpg

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 在线观看黄色大片 | 日韩欧美一区二区三区 | 亚洲国产情侣偷自在线二页 | 国产成人精品免费视频 | 成人免费网站视频www | a黄色毛片 | 日韩理论视频 | 成人毛片免费看 | 青春久草 | m3u8久久国产精品影院 | 久久久午夜精品理论片 | 手机午夜看片 | 真正免费一级毛片在线播放 | 黄色大片在线免费观看 | 男女视频在线免费观看 | 99久在线精品99re6视频 | 日本福利片在线观看 | 欧美黄www免费 | 亚洲午夜成激人情在线影院 | 亚洲精品成人网久久久久久 | 国产精品日韩专区 | 1717she精品国产真正免费 | 亚洲一区二区三区免费看 | 月婷婷色狠狠 | a一级爱做片免费 | 亚洲精品第四页中文字幕 | 怡春院院日本一区二区久久 | 夜夜骑日日 | 天天碰天天摸天天操 | 天天爽天天爽天天片a久久网 | 欧美亚洲激情 | 久久亚洲女同第一区 | 国产特黄特色a级在线视 | 国产精品免费看香蕉 | 天天操夜夜操视频 | 亚洲欧美一区二区三区在饯 | 91成人在线| 日韩特级毛片免费观看视频 | 一区二区三区免费在线 | 中文字幕s级优女区 | 欧美有码在线观看 |