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

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

0 概述

伴隨著存儲(chǔ)技術(shù)的迅猛發(fā)展,人類社會(huì)進(jìn)入了一個(gè)大數(shù)據(jù)時(shí)代,各行各業(yè)都有著龐大的數(shù)據(jù)庫,然而在這些海量的數(shù)據(jù)中挖掘出有價(jià)值的信息成為一個(gè)難題[1]。分布式計(jì)算[2]因?qū)Υ髷?shù)據(jù)具有良好的處理能力而逐漸興起,它通過多個(gè)節(jié)點(diǎn)部署成一個(gè)集群,每個(gè)節(jié)點(diǎn)并行處理計(jì)算后通過匯總來處理任務(wù)。然而,針對(duì)Apriori算法,集群中單個(gè)節(jié)點(diǎn)的計(jì)算能力極大地限制了算法的效率[3]。因此,為通過GPU較強(qiáng)的運(yùn)算能力解決該問題,本文提出一種CPU和GPU協(xié)同工作的方式,將GPU加入到現(xiàn)有的Hadoop平臺(tái)中,增強(qiáng)集群中節(jié)點(diǎn)的計(jì)算能力,并且進(jìn)行對(duì)比實(shí)驗(yàn)來檢測(cè)算法的運(yùn)行效率。

1 Apriori算法的并行化

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

1.1 Apriori算法

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

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

圖1 Apriori算法流程

Apriori算法的計(jì)算流程實(shí)際上是一個(gè)尋找數(shù)據(jù)集中頻繁項(xiàng)的過程,但是因?yàn)樵诘^程中出現(xiàn)了大量的候選頻繁項(xiàng)集,在計(jì)算過程中為了得到候選項(xiàng)集的支持度而多次掃描數(shù)據(jù)集,在原始數(shù)據(jù)樣本較少時(shí)能有較好的計(jì)算效率。一旦數(shù)據(jù)增長到一定規(guī)模后,候選項(xiàng)集將呈指數(shù)增長,算法的執(zhí)行速度和效率都會(huì)受到較大的影響。

1.2 Hadoop平臺(tái)下的Apriori算法

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

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

圖2 Apriori算法MapReduce計(jì)算框架的并行化流程

2 GPU集群加速Apriori算法

2.1 GPU并行計(jì)算

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

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

2.2 改進(jìn)的Apriori算法

CPU/GPU是一種CPU搭配GPU的新型計(jì)算模式[12],由于GPU在計(jì)算方面的超強(qiáng)性能遠(yuǎn)遠(yuǎn)超過了多核系統(tǒng),將任務(wù)中的計(jì)算密集型工作交由GPU來完成,而CPU主要負(fù)責(zé)對(duì)任務(wù)進(jìn)行分配、匯總等。這種方式不僅只是計(jì)算能力的提升,而且在達(dá)到同樣高性能計(jì)算能力的同時(shí),還擁有更廉價(jià)的計(jì)算成本。

2.2.1 Hadoop平臺(tái)中GPU的引入

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

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

圖3 GPU-Hadoop主體框架

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

圖4 GPU-Hadoop計(jì)算的具體流程

由于本文是利用Hadoop平臺(tái)中的分布式文件系統(tǒng)HDFS來存儲(chǔ)數(shù)據(jù)集,因此相對(duì)而言存儲(chǔ)的數(shù)據(jù)量更大,擴(kuò)展性也更好。另外,因?yàn)榭蚣艿闹黧w控制是以Hadoop平臺(tái)為主,所以還能很好地處理節(jié)點(diǎn)失效和負(fù)載不均衡等問題[14],較好地完成計(jì)算工作。

2.2.2 候選項(xiàng)集的生成

上節(jié)提到Master節(jié)點(diǎn)通過最小支持度剪枝來得到全局k項(xiàng)頻繁項(xiàng)集,當(dāng)?shù)玫饺猪?xiàng)頻繁項(xiàng)集后,主節(jié)點(diǎn)Master要判斷是否存在k+1項(xiàng)候選項(xiàng)集。由于頻繁項(xiàng)是從候選項(xiàng)集中通過計(jì)數(shù)挑選得到的,因此如果能很好地控制候選集的數(shù)目,防止不能成為頻繁項(xiàng)集的候選項(xiàng)集產(chǎn)生,就能極大地減少后面的計(jì)算,提高算法效率。

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

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

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

2.2.3 候選項(xiàng)集的優(yōu)化

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

為解決這個(gè)問題,在每個(gè)單獨(dú)的線程內(nèi)申請(qǐng)了一個(gè)寄存器變量count,用來統(tǒng)計(jì)該線程對(duì)候選頻繁項(xiàng)的支持?jǐn)?shù)。然后,在全局寄存器中申請(qǐng)一個(gè)二維數(shù)組count_thread[block_num][thread_num],其中,block_num代表線程塊的個(gè)數(shù),thread_num代表線程塊內(nèi)線程數(shù)。每個(gè)線程塊內(nèi)線程對(duì)候選頻繁項(xiàng)的計(jì)數(shù)完成后,線程之間采用并行的規(guī)約思想,統(tǒng)計(jì)出整個(gè)線程塊的候選頻繁項(xiàng)的計(jì)數(shù)。最后,把節(jié)點(diǎn)所有線程塊block的結(jié)果求和,節(jié)點(diǎn)內(nèi)的統(tǒng)計(jì)計(jì)數(shù)即完成。線程內(nèi)的統(tǒng)計(jì)計(jì)數(shù)過程如圖5所示。

圖5 線程塊內(nèi)并行規(guī)約計(jì)數(shù)過程

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文Hadoop平臺(tái)利用GPU進(jìn)行加速Apriori算法在面對(duì)大規(guī)模數(shù)據(jù)集時(shí)的性能,將實(shí)驗(yàn)分為了2個(gè)部分:1)實(shí)驗(yàn)對(duì)比未采用CUDA加速的Hadoop算法和采用CUDA加速后的Hadoop算法之間的效率;2)實(shí)驗(yàn)對(duì)比Hadoop平臺(tái)下節(jié)點(diǎn)個(gè)數(shù)對(duì)算法的影響。

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

實(shí)驗(yàn)環(huán)境為:5臺(tái)配置GPU的PC構(gòu)成Hadoop集群的Slave節(jié)點(diǎn),1臺(tái)沒有配置GPU的PC作為Hadoop集群的Master節(jié)點(diǎn);NVIDIA CUDE6.0以及Hadoop-1.2.1,集群配置信息如表1所示。

表1 Hadoop集群的節(jié)點(diǎn)配置

3.1 CUDA加速對(duì)比實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用上述的硬件環(huán)境,將未采用CUDA加速的Hadoop算法和采用CUDA加速后的Hadoop算法分別進(jìn)行對(duì)10、50、100、200、500萬條事務(wù)數(shù)據(jù)進(jìn)行處理,查看算法所用的時(shí)間,實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 運(yùn)行時(shí)間與數(shù)據(jù)量的對(duì)比實(shí)驗(yàn)結(jié)果

當(dāng)需要計(jì)算的數(shù)據(jù)量比較小時(shí),單純的Hadoop平臺(tái)運(yùn)行效率更好,這是因?yàn)樵跀?shù)據(jù)量較小時(shí),相對(duì)而言計(jì)算量并沒有特別大,所以將計(jì)算傳遞給GPU反而耗費(fèi)了計(jì)算時(shí)間。當(dāng)數(shù)據(jù)量逐漸增大時(shí),算法的計(jì)算規(guī)模也越來越大,當(dāng)計(jì)算時(shí)間占主要部分時(shí),GPU-Hadoop優(yōu)異的計(jì)算能力因而得以凸顯出來,并且可以看出,隨著數(shù)據(jù)量的增大,相對(duì)于單純地利用Hadoop平臺(tái)來計(jì)算,改進(jìn)算法提升效果越來越明顯。

3.2 不同節(jié)點(diǎn)對(duì)比實(shí)驗(yàn)結(jié)果

對(duì)于并行算法而言,最關(guān)注的是它的運(yùn)算時(shí)間。但與此同時(shí),還要考慮并行算法下資源本身的運(yùn)行效率,即并行效率。純粹用硬件資源來提高算法的效率,對(duì)算法的效率評(píng)價(jià)并不全面。因此,對(duì)改進(jìn)算法用不同從節(jié)點(diǎn)個(gè)數(shù)對(duì)500萬條事務(wù)數(shù)據(jù)進(jìn)行了對(duì)比實(shí)驗(yàn),結(jié)果如表2所示。

表2 不同節(jié)點(diǎn)的實(shí)驗(yàn)結(jié)果對(duì)比

從表2不難發(fā)現(xiàn),隨著從節(jié)點(diǎn)數(shù)目的增加,雖然加速比在不斷變大,但是并行的效率卻在下降。這是因?yàn)樵谔幚淼臄?shù)據(jù)量不變時(shí),Hadoop集群中的節(jié)點(diǎn)數(shù)越多,集群的計(jì)算能力越強(qiáng),因此加速比明顯提高。但是,節(jié)點(diǎn)之間的通信開銷卻在隨之增大,導(dǎo)致并行效率也隨之下降。因此,在進(jìn)行計(jì)算時(shí),不能僅僅單純地追求整體效率的提升,而完全忽視硬件之間的并行效率,應(yīng)該在節(jié)點(diǎn)數(shù)和處理的數(shù)據(jù)量之間找到一個(gè)平衡點(diǎn),從而最有效地利用平臺(tái)設(shè)備。

4 結(jié)束語

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