基于新型異構(gòu)計(jì)算平臺(tái)的數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn).pdf

1、大數(shù)據(jù)時(shí)代的到來(lái)極大地推動(dòng)了數(shù)據(jù)挖掘算法的研究與應(yīng)用，其中KNN算法和 K-means算法作為“十大數(shù)據(jù)挖掘算法”中分類(lèi)算法與聚類(lèi)算法的代表，被廣泛應(yīng)用于文本信息分類(lèi)、金融預(yù)測(cè)、生物基因工程、圖像信息處理等各個(gè)領(lǐng)域。然而隨著信息和數(shù)據(jù)的爆炸式增長(zhǎng)，KNN算法與K-means算法的快速實(shí)現(xiàn)面臨著巨大的挑戰(zhàn)，基于 FPGA的新型異構(gòu)計(jì)算平臺(tái)為加速此類(lèi)算法的實(shí)現(xiàn)提供了新的解決方案。與大型工作站或計(jì)算機(jī)集群相比，基于 FPGA的新型異構(gòu)計(jì)算平臺(tái)

2、具有價(jià)格更低、體積更小等優(yōu)勢(shì)；與GPU平臺(tái)相比，F(xiàn)PGA平臺(tái)具有功耗更低、能量效率更高等優(yōu)勢(shì)。因此，本文基于FPGA新型異構(gòu)計(jì)算平臺(tái)，對(duì)KNN和K-means兩種數(shù)據(jù)挖掘算法進(jìn)行OpenCL異構(gòu)實(shí)現(xiàn)研究。
　　首先，本文基于FPGA異構(gòu)計(jì)算平臺(tái)的特點(diǎn)，設(shè)計(jì)了KNN算法的異構(gòu)實(shí)現(xiàn)方案 KB-KNN。為了充分發(fā)揮異構(gòu)平臺(tái)的優(yōu)勢(shì)，本文將待分類(lèi)數(shù)據(jù)進(jìn)行分組，并采用設(shè)備間流水的并行實(shí)現(xiàn)方案，使異構(gòu)系統(tǒng)中的主機(jī)與從機(jī)同時(shí)參與運(yùn)算，增加硬件資源

3、的利用率。在FPGA加速內(nèi)核的設(shè)計(jì)上，本文改進(jìn)了KNN算法中傳統(tǒng)的一維并行排序方案，采用了更易并行，結(jié)構(gòu)更加簡(jiǎn)單的K并行冒泡實(shí)現(xiàn)結(jié)構(gòu)。為了充分利用 FPGA的全局內(nèi)存帶寬，本文使用訪存聚合等優(yōu)化方法，提高了系統(tǒng)的吞吐量。
　　其次，本文設(shè)計(jì)了基于 FPGA異構(gòu)計(jì)算平臺(tái)的K-means算法實(shí)現(xiàn)方案 FP-Kmeans。根據(jù)算法的特點(diǎn)，采用FPGA與CPU協(xié)同計(jì)算的實(shí)現(xiàn)方案，增加了硬件資源的利用率。對(duì)系統(tǒng)的訪存行為進(jìn)行了優(yōu)化，減少全局

4、內(nèi)存的訪問(wèn)，并充分利用私有內(nèi)存與本地內(nèi)存提高了數(shù)據(jù)讀取與寫(xiě)入的速度。
　　最后，本文基于FPGA+CPU的異構(gòu)計(jì)算平臺(tái)，采用不同數(shù)據(jù)集對(duì)KB-KNN和PF-Kmeans異構(gòu)加速方案進(jìn)行了實(shí)現(xiàn)與測(cè)試，并分別與現(xiàn)有的基于GPU平臺(tái)的方案CU-KNN和CU-Kmeans進(jìn)行對(duì)比。測(cè)試結(jié)果表明，KB-KNN方案與移植到FPGA平臺(tái)上的CU-KNN方案相比獲得了1.7倍的加速比，與原始CU-KNN方案相比獲得了1.5倍的能效比。本文設(shè)計(jì)的P