[發(fā)明專利]基于FPGA的FP?Growth算法的改進(jìn)方法及裝置

在審

• 申請?zhí)枺?/td>: 201710088020.2
• 申請日: 2017-02-19
• 公開（公告）號: CN106874479A
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計）人: 曹芳;陳繼承;王洪偉
• 申請（專利權(quán)）人: 鄭州云海信息技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司41111
• 代理人: 陳勇

技術(shù)領(lǐng)域

本發(fā)明涉及機器學(xué)習(xí)算法處理領(lǐng)域，尤其涉及基于FPGA的FP-Growth算法的改進(jìn)方法及裝置。

背景技術(shù)

基于Spark平臺的FP-Growth算法采用MapReduce分布式計算模型、立足于內(nèi)存計算，實現(xiàn)了該算法的并行化，在一定程度上提升了該算法的挖掘效率；然而隨著大數(shù)據(jù)時代的到來，科學(xué)和工程計算領(lǐng)域的數(shù)據(jù)量急劇增長，計算復(fù)雜度不斷增加，給基于Spark平臺的FP-Growth算法的計算性能帶來了極大挑戰(zhàn)。由于單節(jié)點處理能力有限，Spark通過擴展集群節(jié)點規(guī)模來實現(xiàn)算法性能的提升；而這種集群擴展不僅使得系統(tǒng)成本和能耗快速增加，而且使得集群網(wǎng)絡(luò)復(fù)雜度和節(jié)點間的數(shù)據(jù)傳輸開銷急劇上升，降低了集群擴展帶來的計算性能增益。如何才能解決上述問題，增強單節(jié)點處理能力、進(jìn)而減少計算集群快速擴張帶來的網(wǎng)絡(luò)傳輸開銷，最終實現(xiàn)FP-Growth算法的性能提升成為亟待解決的熱點問題。

發(fā)明內(nèi)容

本發(fā)明提供的基于FPGA的FP-Growth算法的改進(jìn)方法及裝置，克服了現(xiàn)有技術(shù)中存在的不足，顯著的提升了FP-Growth算法的計算性能。

為了達(dá)到上述目的，本發(fā)明是通過以下技術(shù)方案實現(xiàn)的：

本發(fā)明提供一種基于FPGA的FP-Growth算法的改進(jìn)方法，包括以下步驟：

掃描Spark集群中的數(shù)據(jù)庫，獲取頻繁項集；

將頻繁項集進(jìn)行分組；

為Spark集群中的每個節(jié)點加配一塊FPGA板卡；

在FPGA板卡上對每一組的頻繁項集建FP樹；

在FPGA板卡上對每一組建的FP樹進(jìn)行遞歸挖掘；

將每一組遞歸挖掘的結(jié)果進(jìn)行合并。

進(jìn)一步地，將頻繁項集進(jìn)行分組，包括：

將其按頻繁1-項集順序遞減排列；

根據(jù)數(shù)據(jù)庫的大小確定分組個數(shù)，按照預(yù)先設(shè)定的分組規(guī)則將其分為若干組。

進(jìn)一步地，在FPGA板卡對每一組建FP樹，包括：

建立一個根節(jié)點為NULL的FP樹和一個存儲節(jié)點信息的Tab表；

將頻繁項表中的每條處理好的事務(wù)中的數(shù)據(jù)項按降序依次插入到FP樹中，構(gòu)建出FP樹的一條路徑；

在上述的插入過程中，同時用Tab的指針指向?qū)?yīng)項的節(jié)點，并將每個節(jié)點的計數(shù)增加1。

進(jìn)一步地，在FPGA板卡對每一組建的FP樹進(jìn)行遞歸挖掘，包括：

A：從Tab表的尾部的項開始向上遍歷FP樹，每次遍歷得到該項的條件模式基；

B：將其條件模式基轉(zhuǎn)化為條件FP樹；

C：迭代重復(fù)步驟A步驟B，直到FP樹包含一個元素項為止。

進(jìn)一步地，將每一組遞歸挖掘的結(jié)果進(jìn)行合并，包括：

將每一棵條件FP樹生成所有的從根節(jié)點到葉子節(jié)點的路徑，由路徑中的集合生成其所有的非空子集。

基于上述的任一項一種基于FPGA的FP-Growth算法的改進(jìn)方法的一種基于FPGA的FP-Growth算法的改進(jìn)裝置，包括：

獲取模塊，用于掃描Spark集群中的數(shù)據(jù)庫，獲取頻繁項集；

分組模塊，用于將頻繁項集進(jìn)行分組；

板卡模塊，用于為Spark集群中的每個節(jié)點加配一塊FPGA板卡；

建樹模塊，用于在FPGA板卡上對每一組的頻繁項集建FP樹；

挖掘樹模塊，用于在FPGA板卡上對每一組建的FP樹進(jìn)行遞歸挖掘；

結(jié)果模塊，用于將每一組遞歸挖掘的結(jié)果進(jìn)行合并。

本發(fā)明所提供的一種基于FPGA的FP-Growth算法的改進(jìn)方法，具有如下優(yōu)點：

1.本發(fā)明通過在原有Spark集群的基礎(chǔ)上加配FPGA，為每個集群節(jié)點增加一塊FPGA板卡，由于FPGA板卡具有高性能、低功耗、易編程、動態(tài)可重構(gòu)等突出優(yōu)勢，是一種新型的異構(gòu)計算加速器件，將FPGA板卡與原有節(jié)點組成新的Spark集群節(jié)點服務(wù)于整個Spark集群，來提高集群單節(jié)點的計算能力，同時保留了Spark集群自身的并行計算框架，有效提高了大數(shù)據(jù)環(huán)境下FP-Growth算法的整體性能，且FPGA作為加速設(shè)備與CPU相配合形成異構(gòu)計算平臺，能夠有效的提升Spark集群的綜合性能；

2.本發(fā)明將FPGA與Spark相結(jié)合，將算法中最耗時、計算量最大的建樹與挖掘樹部分從Spark源碼中抽離并在FPGA上開發(fā)實現(xiàn)并優(yōu)化，而算法的其他部分如數(shù)據(jù)分組、挖掘結(jié)果綜合等計算量較小的部分仍按照Spark原有機制運行，充分發(fā)揮二者優(yōu)勢，并在此基礎(chǔ)上對FP-Growth算法進(jìn)行優(yōu)化改進(jìn)，有效的提升FP-Growth算法的計算性能。