《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 基于CPU-FPGA異構(gòu)系統(tǒng)的排序算法加速
基于CPU-FPGA異構(gòu)系統(tǒng)的排序算法加速
2022年電子技術(shù)應(yīng)用第1期
寇遠(yuǎn)博,,邱澤宇,王 亮,,黃建強(qiáng)
青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系,,青海 西寧810016
摘要: 傳統(tǒng)的排序方法主要以軟件串行的方式實(shí)現(xiàn),包括冒泡排序,、選擇排序等。這些算法往往采用順序比較,運(yùn)算的時(shí)間復(fù)雜度較高,。近年來已經(jīng)提出了一些并行度較高的排序算法,但是由于CPU的硬件特點(diǎn),,不能很好地利用這些算法的并行性,。而FPGA具有良好的靈活性、并行性和集成性等特點(diǎn),,因此在FPGA上可以更好地發(fā)揮這些并行算法的優(yōu)勢(shì),,從而大大提高數(shù)據(jù)排序的實(shí)時(shí)性?;诖嗽O(shè)計(jì)了一個(gè)CPU-FPGA異構(gòu)系統(tǒng),,將一些排序算法移植到FPGA上,并進(jìn)行功能驗(yàn)證和理論性能評(píng)估,。結(jié)果顯示,,該系統(tǒng)對(duì)于并行性高的排序算法具有良好的加速效果,但邏輯資源消耗巨大,,適用于實(shí)時(shí)性要求高的算法加速場(chǎng)景,。
中圖分類號(hào): TP302.7
文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.212431
中文引用格式: 寇遠(yuǎn)博,邱澤宇,,王亮,,等. 基于CPU-FPGA異構(gòu)系統(tǒng)的排序算法加速[J].電子技術(shù)應(yīng)用,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 引言

    排序問題是計(jì)算機(jī)科學(xué)中的經(jīng)典問題,,人們已對(duì)此提出了許多解決辦法。而大規(guī)模數(shù)據(jù)的排序問題仍然是一個(gè)困難的問題,。這一問題廣泛發(fā)生在圖計(jì)算領(lǐng)域,,如社交網(wǎng)絡(luò)、推薦系統(tǒng)等[1],。

    傳統(tǒng)的計(jì)算平臺(tái)CPU和GPU存在計(jì)算效率低和高功耗的問題,,不能很好地滿足圖計(jì)算領(lǐng)域的計(jì)算需求。為了解決這一問題,,研究者們采用定制硬件平臺(tái)來進(jìn)行圖數(shù)據(jù)的處理和算法的加速[2],。其中,基于FPGA的圖計(jì)算加速器因滿足復(fù)雜性高,、數(shù)據(jù)規(guī)模大和基本操作多變的圖計(jì)算的性能要求[3]受到青睞,。

    目前,國(guó)內(nèi)外已經(jīng)存在大量的基于FPGA的硬件加速器,。GraphOps[4]提供了一個(gè)硬件庫(kù),,可以讓用戶快速且輕松地構(gòu)造用于圖分析算法的節(jié)能型加速器。FlashGraph[5]在具有極端并行性的SSD文件系統(tǒng)之上實(shí)現(xiàn)了圖處理引擎,,它可以在性能損失最小的情況下利用SSD處理超大規(guī)模的圖數(shù)據(jù),。FPGA開發(fā)門檻較高,但如果使用ThunderGP[6],,開發(fā)人員只需要使用C++編寫API函數(shù),,ThunderGP就會(huì)自動(dòng)生成一個(gè)高性能的加速器,極為方便,。大規(guī)模世界圖往往具有強(qiáng)大的社區(qū)結(jié)構(gòu),,其中一小部分頂點(diǎn)比其他頂點(diǎn)的訪問頻率更高,利用這一潛在局部性,,可以大幅提高圖計(jì)算的性能[7],。除了單機(jī)圖計(jì)算系統(tǒng),一些典型的分布式的圖計(jì)算系統(tǒng),,如ForeGraph[8]和FPGP[9],也可以處理超大規(guī)模的數(shù)據(jù),。




本文詳細(xì)內(nèi)容請(qǐng)下載:http://forexkbc.com/resource/share/2000003903,。




作者信息:

寇遠(yuǎn)博,邱澤宇,,王  亮,,黃建強(qiáng)

(青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系,,青海 西寧810016)




wd.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。