基于Hadoop平臺的GPU集群加速Apriori算法

瞿詩齊,劉少江,倪偉傳,余慶茂

(中山大學 新華學院,廣州 510520)

0 概述

伴隨著存儲技術的迅猛發展,人類社會進入了一個大數據時代,各行各業都有著龐大的數據庫,然而在這些海量的數據中挖掘出有價值的信息成為一個難題[1]。分布式計算[2]因對大數據具有良好的處理能力而逐漸興起,它通過多個節點部署成一個集群,每個節點并行處理計算后通過匯總來處理任務。然而,針對Apriori算法,集群中單個節點的計算能力極大地限制了算法的效率[3]。因此,為通過GPU較強的運算能力解決該問題,本文提出一種CPU和GPU協同工作的方式,將GPU加入到現有的Hadoop平臺中,增強集群中節點的計算能力,并且進行對比實驗來檢測算法的運行效率。

1 Apriori算法的并行化

并行化計算[4]是現代計算要求越來越高的產物,更是目前高性能計算中非常實用的一種計算手段,它主要是把一個很復雜或者計算量很大的任務,分割成很多互相不具關聯性的小任務,然后把這些許許多多的小任務利用多個處理器并行來完成,最后把得到的結果匯總合并。通過這種方式有效地利用計算資源,減少運算所需的時間,提高算法效率。

1.1 Apriori算法

Apriori算法一種從海量的數據中找出數據間相關性的算法,它通過逐層迭代的手段來挖掘頻繁項,是關聯規則算法中最經典的一種[5],也是最先驗證其原理并且借鑒了源于support的剪枝技術的成果,有效地剔除了候選的真子集項的指數級增長姿態,使得它成為了關聯挖掘算法中應用最為廣泛的算法之一[6]。

Apriori算法的計算流程如圖1所示。首先遍歷事務數據集,統計出每條事務中每項出現的次數,即每項的支持度。刪減掉小于最小支持度的項,剩余的每個項即1階頻繁項集[7]。然后Apriori算法進入一個循環過程,根據k(k>0)階頻繁項來生成k+1階候選項集[8],如果候選項的個數小于0,則算法結束;否則,統計每個k+1階候選項集的支持度,刪除達不到最小支持度的候選項,就得到了k+1階頻繁項集合。最后繼續進入循環進行計算,直到算法結束。

圖1 Apriori算法流程

Apriori算法的計算流程實際上是一個尋找數據集中頻繁項的過程,但是因為在迭代過程中出現了大量的候選頻繁項集,在計算過程中為了得到候選項集的支持度而多次掃描數據集,在原始數據樣本較少時能有較好的計算效率。一旦數據增長到一定規模后,候選項集將呈指數增長,算法的執行速度和效率都會受到較大的影響。

1.2 Hadoop平臺下的Apriori算法

自從云計算出現以來,有關大數據的相關研究也相繼出現,其中使用最多的分布式結構即Hadoop[9],它是用來解決大規模的數據批處理的平臺,它的MapReduce計算框架[10]為Apriori算法的計算過程提供了一個很好的并行化思路。MapReduce計算框架也就是一個Map-Reduce的過程。首先進行一個Map的過程,即將大規模數據集分割成許多小的子數據集。然后將子數據集分配給Hadoop下的多個Mapper計算節點,使各個節點之間同時并行計算。最后進行Reduce的過程,即將每個Mapper節點計算出的結果通過Reduce節點進行匯總合并,來實現計算的并行。

在Hadoop平臺下,Apriori算法MapReduce的并行化流程如圖2所示。首先主節點把原始的數據集分成N個小的數據塊,均勻地散布到Hadoop集群中的各個工作節點上。工作節點應用MapReduce框架的原理,把收到的數據塊進行Map處理后計算k項候選集。接下來把每個節點上Map進程得到的局部k項候選集通過Reduce進程進行匯總得到全局的k項候選集的支持度。然后根據最小支持度的篩選得到全局k項頻繁項集合。最后根據全局k項頻繁項得到k+1項候選集,重新進入第2次數據處理直到k+1項候選集為空,結束算法。

圖2 Apriori算法MapReduce計算框架的并行化流程

2 GPU集群加速Apriori算法

2.1 GPU并行計算

CPU最初設計是為了次快速地一次完成多條串行指令,目前它的發展已經遇到了瓶頸,而GPU被設計用來執行并行指令[11],擁有大量的流處理器并行執行,運算能力不是CPU能夠比擬的。同時,GPU的計算成本也比CPU要小得多,因此,GPU非常適合用來進行密集型的計算。

從上文對Apriori算法的介紹可知,在運算過程中,主要是找出數據集中的頻繁項集合。實際上,頻繁項集主要是通過統計候選項的支持度來確定的,而候選項集就是一個排列組合的過程。其中,候選項集生成的規模大小主要是由項集的長度來決定的,大多數甚至呈指數增長,在數據集中對候選項進行計數的計算量十分巨大。因此,頻繁項項集的計算實際上也是一個計算密集型的計算。

2.2 改進的Apriori算法

CPU/GPU是一種CPU搭配GPU的新型計算模式[12],由于GPU在計算方面的超強性能遠遠超過了多核系統,將任務中的計算密集型工作交由GPU來完成,而CPU主要負責對任務進行分配、匯總等。這種方式不僅只是計算能力的提升,而且在達到同樣高性能計算能力的同時,還擁有更廉價的計算成本。

2.2.1 Hadoop平臺中GPU的引入

高性能計算主要分為分布式計算和GPU并行計算2種不同的計算方式[13]。當然,不管是利用集群來進行分布式計算還是GPU對數據的并行計算,對Apriori算法進行改進,分離出更多的并行化操作,使硬件資源并行來處理算法,減少運行時間。但是面對海量數據利用Apriori算法計算時,Hadoop平臺中集群的單個節點的計算量依舊是提高算法速度的一個瓶頸,而單個GPU的存儲能力不足,難以處理海量的數據輸入。因此,本文提出將GPU引入Hadoop平臺來充當主要的計算單元,不僅保留了Hadoop平臺高效的分布式管理,而且還能發揮GPU強大的并行計算能力。

雖然GPU擁有著更為強大的計算和并行能力,但是這并不意味著所有的計算任務都應該交由GPU來處理。GPU適合那些計算量大而控制流簡單的任務,即該任務大部分的處理時間都運用在計算上才能充分發揮GPU的高計算性能。通過前面的分析可知,Apriori算法的瓶頸主要是對候選項集支持度的計數。因此,把對候選項集的計數過程主要交給GPU來處理,Hadoop平臺下主節點Master主要負責子數據的分發、候選項集的下發與剪枝得到頻繁項集;從節點Slave主要存儲子數據,收到候選項集后創建kernel函數,調用GPU計算來對候選項集進行計數。本文在原來Hadoop的框架下,設計一種多節點并發、節點內多線程并行的多層次多粒度GPU-Hadoop框架,主體框架如圖3所示。首先搭建一個Hadoop集群,主要由一個主節點Master和N個從節點Slave構成,主節點Master控制多個從節點Slave并行進行任務,每個從節點Slave調用GPU進行計算密集型計算,最后將匯總給主節點Master。

圖3 GPU-Hadoop主體框架

GPU嵌入Hadoop的具體流程如圖4所示。將原始數據存儲在HDFS中,主節點Master將原始的數據分割成多塊子數據,然后將數據均勻地分散到各個Slave處。主節點Master生成對應的k項候選項集下發到Slave中。Slave收到后創建kernel函數來調用GPU對項集進行計數,每個Slave節點得到部分k項候選集的計算,然后匯總得到全局k項候選集合的計數,Master節點通過最小支持度剪枝來得到全局k項頻繁項集。之后,主節點Master判斷是否存在k+1項候選項集,如果生成k+1項候選項集,就將它發給Slave進行下一輪計算;反之如果不存在,計算結束。

圖4 GPU-Hadoop計算的具體流程

由于本文是利用Hadoop平臺中的分布式文件系統HDFS來存儲數據集,因此相對而言存儲的數據量更大,擴展性也更好。另外,因為框架的主體控制是以Hadoop平臺為主,所以還能很好地處理節點失效和負載不均衡等問題[14],較好地完成計算工作。

2.2.2 候選項集的生成

上節提到Master節點通過最小支持度剪枝來得到全局k項頻繁項集,當得到全局項頻繁項集后,主節點Master要判斷是否存在k+1項候選項集。由于頻繁項是從候選項集中通過計數挑選得到的,因此如果能很好地控制候選集的數目,防止不能成為頻繁項集的候選項集產生,就能極大地減少后面的計算,提高算法效率。

Apriori算法依賴于向下封閉原則[15],假設一個候選項集是頻繁項集,那么這個項集的子項也一定是頻繁項集。相應地,一個不是頻繁項集擴展出來的父項集一定也不是頻繁項集[16]。針對Apriori頻繁項集的這個特點,本文利用聯合和刪減的方法生成頻繁項集,可以生成包括全部頻繁項集較小的候選頻繁項,較前面的方式有了很大的提高。

聯合過程:在一個長度為k的頻繁項集集合Fk中,任意取2個不同的頻繁項集f1和f2。如果f1和f2中有k-1項是相同的,那么就可以得到其中一個由f1和f2組成的并集組成的k+1項項集f,可以把這個項集f放入臨時的k+1候選項集集合Ck+1′。然后重復這一合并的步驟,直到將Fk全部的項集元素都兩兩組合完畢為止。

刪減過程:在之前聯合過程中,有些不滿足向下封閉原則,為了將不滿足向下封閉原則的項集刪減,在這里加入一個Merge函數對項集進行壓縮。Merge函數是遍歷集合Ck+1′中的項集元素f′,f′所有k長度的子集都能在Fk中找到,f′有必要帶入后面計算的候選頻繁項集,放入到真正的候選項集集合Ck+1中。

2.2.3 候選項集的優化

在串行計算中,候選集的計數方式一般都是定義一個計數變量count,遍歷數據集中的每條事務,不斷地對變量count進行加一操作,最后count的值就是該候選項在數據集中出現的次數。由于現在將計數的工作交給了GPU來進行處理,GPU啟動多個數據塊計算,數據塊內多線程并行,count變量在同一時間容易被多個線程同時訪問和修改,可能會使得計數出錯。但是如果采用線程鎖的方式,頻繁地加鎖減鎖又會嚴重影響算法的運行速度。

為解決這個問題,在每個單獨的線程內申請了一個寄存器變量count,用來統計該線程對候選頻繁項的支持數。然后,在全局寄存器中申請一個二維數組count_thread[block_num][thread_num],其中,block_num代表線程塊的個數,thread_num代表線程塊內線程數。每個線程塊內線程對候選頻繁項的計數完成后,線程之間采用并行的規約思想,統計出整個線程塊的候選頻繁項的計數。最后,把節點所有線程塊block的結果求和,節點內的統計計數即完成。線程內的統計計數過程如圖5所示。

圖5 線程塊內并行規約計數過程

3 實驗結果與分析

為了驗證本文Hadoop平臺利用GPU進行加速Apriori算法在面對大規模數據集時的性能,將實驗分為了2個部分:1)實驗對比未采用CUDA加速的Hadoop算法和采用CUDA加速后的Hadoop算法之間的效率;2)實驗對比Hadoop平臺下節點個數對算法的影響。

實驗的數據選自UCI機器學期數據庫中某大型超市交易記錄信息,數據分為2份:10萬條數據集和50萬條數據集。為方便實驗,對這些文件又進行了多次備份,最多將數據自拷貝10次達到500萬條數據集來達到大數據的情況,并對選取的數據集進行預處理,將處理過的數據上傳到HDFS。

實驗環境為:5臺配置GPU的PC構成Hadoop集群的Slave節點,1臺沒有配置GPU的PC作為Hadoop集群的Master節點;NVIDIA CUDE6.0以及Hadoop-1.2.1,集群配置信息如表1所示。

表1 Hadoop集群的節點配置

3.1 CUDA加速對比實驗結果

實驗采用上述的硬件環境,將未采用CUDA加速的Hadoop算法和采用CUDA加速后的Hadoop算法分別進行對10、50、100、200、500萬條事務數據進行處理,查看算法所用的時間,實驗結果如圖6所示。

圖6 運行時間與數據量的對比實驗結果

當需要計算的數據量比較小時,單純的Hadoop平臺運行效率更好,這是因為在數據量較小時,相對而言計算量并沒有特別大,所以將計算傳遞給GPU反而耗費了計算時間。當數據量逐漸增大時,算法的計算規模也越來越大,當計算時間占主要部分時,GPU-Hadoop優異的計算能力因而得以凸顯出來,并且可以看出,隨著數據量的增大,相對于單純地利用Hadoop平臺來計算,改進算法提升效果越來越明顯。

3.2 不同節點對比實驗結果

對于并行算法而言,最關注的是它的運算時間。但與此同時,還要考慮并行算法下資源本身的運行效率,即并行效率。純粹用硬件資源來提高算法的效率,對算法的效率評價并不全面。因此,對改進算法用不同從節點個數對500萬條事務數據進行了對比實驗,結果如表2所示。

表2 不同節點的實驗結果對比

從表2不難發現,隨著從節點數目的增加,雖然加速比在不斷變大,但是并行的效率卻在下降。這是因為在處理的數據量不變時,Hadoop集群中的節點數越多,集群的計算能力越強,因此加速比明顯提高。但是,節點之間的通信開銷卻在隨之增大,導致并行效率也隨之下降。因此,在進行計算時,不能僅僅單純地追求整體效率的提升,而完全忽視硬件之間的并行效率,應該在節點數和處理的數據量之間找到一個平衡點,從而最有效地利用平臺設備。

4 結束語

本文通過研究Apriori數據關聯算法,提出一種基于Hadoop平臺的GPU加速計算算法。由于GPU在計算方面的超強性能,超過了多核系統,因此將任務中的計算密集型工作交由GPU來完成,而CPU主要負責對任務進行分配、匯總等,不僅節約硬件成本,而且具有良好的擴展性。實驗結果表明,改進后的算法能夠有效地利用計算資源,減少運算所需的時間,提高算法效率。