基于CUDA 并行化的K-Means 聚類算法優(yōu)化?

丁芙蓉 張功萱

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

聚類分析是一個(gè)將數(shù)據(jù)集中在某些方面相似的數(shù)據(jù)成員進(jìn)行分類組織的過(guò)程。一個(gè)聚類就是一些數(shù)據(jù)實(shí)例的集合，這個(gè)集合中的元素彼此相似，但它們都與其他聚類中的元素不同。K-Means是一種基于劃分的聚類算法，它通過(guò)隨機(jī)初始聚類中心，不斷地迭代調(diào)整聚類中心，得到最終的聚類結(jié)果［1］。K-Means 算法執(zhí)行簡(jiǎn)單，聚類效率高，目前已被廣泛地應(yīng)用于數(shù)據(jù)挖掘［2］、模式識(shí)別［3］、圖像處理［4］、氣象分析［5］等領(lǐng)域。

在大數(shù)據(jù)背景下，數(shù)據(jù)具有規(guī)模巨大，高速產(chǎn)生，形式多樣的特點(diǎn)，針對(duì)大規(guī)模，高維數(shù)據(jù)，聚類在每次迭代過(guò)程中的計(jì)算量非常大，耗時(shí)嚴(yán)重［6］。在高性能計(jì)算領(lǐng)域，多核和眾核芯片的普及，計(jì)算設(shè)備的計(jì)算能力不斷提高，如何充分利用計(jì)算設(shè)備的計(jì)算能力來(lái)進(jìn)行數(shù)據(jù)分析成為研究的熱點(diǎn)［7］。GPU 上有幾十個(gè)甚至上百個(gè)計(jì)算核心，采用GPU并行化K-Means 聚類算法相比于串行的K-Means算法，能達(dá)到 2～75x 的加速比［8］，大大地降低了算法的運(yùn)行時(shí)間。目前，在GPU 上進(jìn)行K-Means 聚類優(yōu)化多集中在初始聚類中心選擇方面，文獻(xiàn)［9］提出了初始多組聚類中心，迭代4 到5 次選擇最佳聚類中心的方法，文獻(xiàn)［10］提出了動(dòng)態(tài)調(diào)整聚類中心的策略。上述方法在優(yōu)化聚類中心的選擇后，算法的準(zhǔn)確率和性能得到了提升，但是在進(jìn)行聚類的迭代計(jì)算過(guò)程時(shí)，使用CUDA 的同步計(jì)算模式，即將CPU 作為程序的控制端，GPU 作為加速部件，在GPU 進(jìn)行加速計(jì)算時(shí)，作為主控端的CPU 陷入忙等狀態(tài)，直到GPU 上的計(jì)算任務(wù)完成并返回。在多核普及的時(shí)代，這種方式大大浪費(fèi)了主機(jī)端CPU的計(jì)算資源，因此本文提出了基于CPU/GPU 異步計(jì)算的優(yōu)化方法，利用GPU 核函數(shù)和CPU 異步執(zhí)行的特點(diǎn)，通過(guò)數(shù)據(jù)并行策略，將聚類過(guò)程進(jìn)一步并行化，減少了CPU 忙等，加速了K-Means 聚類算法的執(zhí)行。

2 相關(guān)算法與技術(shù)

2.1 K-Means聚類算法

設(shè) 樣 本 數(shù) 據(jù) 集 為 D={xi|i=1,2,…n} ，C={ci|i=1,2,…k}表示聚類的k 個(gè)類別，其中ci是第i 個(gè)聚類的中心。用‖‖xi-cj表示從xi到第j個(gè)聚類中心的距離，定義d(x,C)2=K-Means 算法的目的就是找到一個(gè)包含k 個(gè)聚類中心的集合C ，使得誤差最小。

K-Means聚類算法的步驟如下［11］:

1）隨機(jī)選擇k 個(gè)樣本(c1,c2,…ck)作為初始聚類中心；

2）將樣本數(shù)據(jù)集D 中各樣本按照最近距離原則指派給k 個(gè)聚類中心；

4）判斷是否滿足收斂準(zhǔn)則，不滿足跳轉(zhuǎn)至步驟2），否則算法收斂，中止算法。

2.2 CUDA程序設(shè)計(jì)模型

CUDA 是由NIVIDA 公司推出的一種利用GPU進(jìn)行通用并行計(jì)算的整套解決方案，包括硬件支持、程序語(yǔ)言擴(kuò)展、編譯器、調(diào)試器等整套開發(fā)工具鏈。在CUDA 中，物理上的SM（Streaming Multiprocessor，流多處理器）和SP（Streaming Processor，流處理器）被映射為邏輯上的網(wǎng)格（grid）、塊（block）和線程（thread），同一個(gè)線程塊中的線程可以通過(guò)共享存儲(chǔ)器實(shí)現(xiàn)數(shù)據(jù)共享，一個(gè)塊中可以通過(guò)唯一的索引來(lái)控制塊內(nèi)的每個(gè)線程來(lái)完成并行計(jì)算［12］。一個(gè)典型的CUDA 應(yīng)用由兩部分組成:在主機(jī)CPU上執(zhí)行的host 端程序，負(fù)責(zé)數(shù)據(jù)傳輸，初始化和啟動(dòng)GPU；完全在GPU 上執(zhí)行的device 端程序（被成為kernal 函數(shù)）。host 端與device 端之間的數(shù)據(jù)傳輸通過(guò) PCI Express 總線傳輸［13］。CUDA 程序員可以使用CUDA C，一種擴(kuò)展C 語(yǔ)言的編程語(yǔ)言來(lái)實(shí)現(xiàn)kernal 函數(shù)。在調(diào)用kernal 函數(shù)時(shí)，會(huì)以多線程的方式在GPU上并行執(zhí)行。

2.3 基于CUDA并行化的K-Means算法

由2.1 節(jié)可知，K-Means 聚類算法的迭代過(guò)程主要由樣本指派和更新聚類中心兩個(gè)階段組成。第一階段樣本指派，通過(guò)計(jì)算各個(gè)樣本到聚類中心的距離，將樣本指派給距離最近的聚類中心，該階段具備典型的數(shù)據(jù)并行的特點(diǎn)，各個(gè)樣本的最小距離可以相互獨(dú)立計(jì)算，適合于在GPU 上用多線程來(lái)加速計(jì)算，即將聚類空間中的每個(gè)樣本點(diǎn)對(duì)應(yīng)一個(gè)線程，負(fù)責(zé)該點(diǎn)的指派。聚類算法中計(jì)算量最大的一部分是樣本指派，通過(guò)并行設(shè)計(jì)，可以提高算法的運(yùn)行速度。對(duì)于更新聚類中心階段，需要計(jì)算樣本坐標(biāo)累加和，計(jì)算新的聚類中心。若在GPU上用多線程來(lái)更新聚類中心，需要所有線程訪問(wèn)一個(gè)求和值，而GPU的block間缺少全局的同步性，計(jì)算累加和容易引起B(yǎng)ank 沖突。因此將數(shù)據(jù)傳回主機(jī)端，將其在用于較大可讀寫cache 的CPU 上進(jìn)行［14］。

基于CUDA 并行化的K-Means 聚類算法的偽代碼如算法1［15］所示，首先初始化聚類中心，之后進(jìn)行迭代計(jì)算。算法的主體包含一個(gè)循環(huán)，先將聚類中心拷貝到GPU上，然后在GPU上通過(guò)調(diào)用CUDA 的函數(shù)進(jìn)行樣本指派gpu_labeling（），樣本指派完成后，將樣本指派的結(jié)果通過(guò)cudaMemcpy（）拷貝回CPU，此時(shí)的數(shù)據(jù)拷貝是同步的，只有第4 行GPU 上的kernal 函數(shù)執(zhí)行完畢才開始數(shù)據(jù)拷貝。樣本指派的結(jié)果拷貝完成后，在CPU上進(jìn)行聚類更新updateCentroids（）。通過(guò)定義偏差率φ 來(lái)表示先后迭代中聚類中心發(fā)生變化的比例占全部樣本的比例，并針對(duì)偏差率定義閾值φ0，表示算法終止的條件。

算法1：基于CUDA的并行K-Means聚類算法

1）init（D，C）//D 表示聚類的輸入數(shù)據(jù)集，C 表示聚類中心

2）while φ ＞ φ0do

3） cudaMemcpy（…）

4） gpu_labeling＜＜ ＜…＞ ＞＞（D ，C）

5） cudaMemcpy（…）

6） updateCentroids（D ，C）

7） compute φ

8）end while

3 基于CPU/GPU異步計(jì)算的并行化

3.1 算法存在問(wèn)題

經(jīng)典的基于CUDA 并行化的K-Means 算法的執(zhí)行過(guò)程如圖1。S1 表示迭代的第一階段，樣本指派gpu_labeling（）；S2 表示迭代的第二階段，更新聚類中心點(diǎn)updateCentriods（）。 D 表示輸入的數(shù)據(jù)集，圖中的箭頭表示各個(gè)執(zhí)行階段間的數(shù)據(jù)依賴關(guān)系。執(zhí)行時(shí)，必須滿足箭頭標(biāo)示的順序一致性。

圖1 基于CUDA的并行K-Means執(zhí)行過(guò)程

在理論上，對(duì)于數(shù)據(jù)規(guī)模為n，樣本維度為d ，聚類劃分個(gè)數(shù)為k 的K-Means聚類過(guò)程，樣本指派的運(yùn)行時(shí)間是O(n×k×d)，而更新聚類中心的運(yùn)行時(shí)間是O((n+k)×d)。采用CUDA 并行化后，樣本指派的運(yùn)行時(shí)間是，其中 p 為計(jì)算單元的數(shù)量，與GPU 的性能有關(guān)。此時(shí)，樣本指派/更新聚類中心的比率等于n ?k 。隨著聚類劃分個(gè)數(shù)k 的增加，樣本指派/更新聚類中心的比率會(huì)變大，即S1/S2 的比值增大。大部分時(shí)間在GPU 上進(jìn)行計(jì)算，CPU 處于忙等狀態(tài)，浪費(fèi)了CPU 的計(jì)算資源。隨著多核CPU 的普及，原有的并行模式不能充分利用CPU端的計(jì)算能力，浪費(fèi)了CPU 的計(jì)算資源。本文利用GPU/CPU異步執(zhí)行的特點(diǎn)，提出數(shù)據(jù)并行策略，將聚類數(shù)據(jù)集分配到 CPU 和 GPU 上，增加了 CPU 和 GPU 的數(shù)據(jù)通量，對(duì)傳統(tǒng)的并行算法做優(yōu)化，提高了聚類的效率。

3.2 數(shù)據(jù)并行優(yōu)化策略

由3.1節(jié)分析可知，當(dāng)k 增大時(shí)，算法的主要時(shí)間開銷在樣本指派階段，即GPU 上執(zhí)行的計(jì)算任務(wù)，此時(shí)CPU 處于忙等狀態(tài)，浪費(fèi)了多核CPU 的計(jì)算資源。樣本指派的時(shí)間復(fù)雜度為通過(guò)減小在GPU 上的聚類數(shù)據(jù)量，可以減小樣本指派階段的執(zhí)行時(shí)間。因此，將聚類數(shù)據(jù)集進(jìn)行劃分，一部分?jǐn)?shù)據(jù)在GPU 上進(jìn)行樣本指派，另一部分?jǐn)?shù)據(jù)在CPU 上進(jìn)行樣本指派，通過(guò)數(shù)據(jù)并行的方式，GPU 上的運(yùn)算和CPU 上的運(yùn)算同時(shí)進(jìn)行。通過(guò)GPU 和CPU 的計(jì)算重疊，減小算法的執(zhí)行時(shí)間。利用數(shù)據(jù)并行策略對(duì)CUDA 并行化的K-Means聚類算法進(jìn)行優(yōu)化，在提高CPU的利用率的同時(shí)提高了算法的執(zhí)行效率。如圖3 所示，數(shù)據(jù)集分成了g 和c 兩個(gè)部分，在保證原來(lái)的數(shù)據(jù)依賴關(guān)系下，完成聚類。

圖2 數(shù)據(jù)并行優(yōu)化的K-Means執(zhí)行過(guò)程

基于數(shù)據(jù)并行策略的CUDA 并行化聚類方法，將輸入數(shù)據(jù)集劃分成兩個(gè)部分，利用CPU 和GPU異步執(zhí)行的特點(diǎn)，分別在CPU 和GPU 上完成迭代過(guò)程中的樣本指派。然后再實(shí)現(xiàn)CPU 和GPU 的同步，在CPU 上合并兩個(gè)部分樣本指派的結(jié)果，重新計(jì)算聚類中心。

算法2 給出了基于數(shù)據(jù)并行策略的CUDA 并行化K-means 聚類的迭代過(guò)程。首先將數(shù)據(jù)集分成兩個(gè)部分D1、D2，每次迭代調(diào)用GPU 核函數(shù)gpu_labeling（）來(lái)對(duì)數(shù)據(jù)集 D1 完成樣本指派，調(diào)用CPU 函數(shù) cpu_labeling（）來(lái)對(duì)數(shù)據(jù)集 D2 完成樣本指派。由于GPU 和CPU 是異步執(zhí)行的，這兩部分的計(jì)算重疊。通過(guò)gpu_finish 和cpu_finish 變量來(lái)表示GPU 和CPU 上的樣本指派是否完成，從而實(shí)現(xiàn)GPU和CPU的同步。然后再對(duì)數(shù)據(jù)集D 進(jìn)行更新聚類中心updateCentroids（）。

其中，GPU 和CPU 的異步執(zhí)行以及同步操作，我們總結(jié)如下:

1）GPU 和 CPU 之間的數(shù)據(jù)傳輸使用 cudaMemcpyAsync 異步傳輸?shù)姆绞?，因?-8 行代碼的操作提交到GPU 后，控制權(quán)立即返回給host 端，此時(shí)第9 行代碼開始執(zhí)行。通過(guò)這種方式，實(shí)現(xiàn)了GPU 和CPU的異步執(zhí)行。

2）GPU上的樣本指派完成后，插入一個(gè)流事件gpu_finish。調(diào)用cudaEventQuery 函數(shù)，通過(guò)監(jiān)聽gpu_finish 來(lái)判斷GPU 上的樣本指派是否完成。CPU上樣本指派完成后，將cpu_finish置為1。通過(guò)gpu_finish 和 cpu_finish 來(lái) 實(shí) 現(xiàn) GPU 和 CPU 樣本指派完成后的同步。

3）當(dāng)更新聚類中心updateCentroids（）完成后，要置cpu_finish為0，進(jìn)行復(fù)位。

算法2：數(shù)據(jù)并行策略優(yōu)化的算法

1.Init（D，C）//D 表示聚類的輸入數(shù)據(jù)集，C 表示聚類中心

2.cpu_finish=0

3.cudaEvent_t gpu_finish

4.while φ ＞ φ0do

5. cudaMemcpyAsync（…）

6. gpu_labeling＜＜ ＜……＞＞ ＞（D1，C）

7. cudaMemcpyAsync（…）

8. cudaEventRecord（gpu_finish）

9. while（cudaEventQuery（gpu_finish）== cudaError-NotReady）do

10. if（cpu_finish）

11. continue

12. cpu_labeling（ D2，C）

13. cpu_finish=1

14. end while

15. updateCentroids（D ，C）

16. cpu_finish=0

17. compute φ

18.end while

4 實(shí)驗(yàn)與分析

有很多文獻(xiàn)在GPU 上加速K-Means 算法，算法的執(zhí)行流程如算法1。因此本文的對(duì)比算法為算法1，實(shí)驗(yàn)的主要目的是分析算法的執(zhí)行時(shí)間和加速比。由于相同初始條件下，K-Means算法最終的聚類迭代次數(shù)相同，在進(jìn)行實(shí)驗(yàn)時(shí)，確保算法1和算法2的初始聚類中心相同。

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證算法的有效性，依據(jù)本文提出的數(shù)據(jù)并行優(yōu)化策略，利用CUDA C 語(yǔ)言，在GPU 上實(shí)現(xiàn)了算法1 和算法2。實(shí)驗(yàn)平臺(tái)為配有兩個(gè)Intel Xeon E5-2620 2.10GHz CPU，NIVIDIA Tesla C2050 GPU的服務(wù)器，采用64位Windows server 2012操作系統(tǒng)。主機(jī)端的英特爾至強(qiáng)處理器每個(gè)處理器有8 個(gè)物理核心，支持超線程技術(shù)，在主機(jī)端每次可以最多可以支持32 個(gè)線程。NVIDIA Tesla C2050計(jì)算卡擁有448 個(gè)頻率為1.15GHz 的CUDA 核心，3 GB GDDR5 專用存儲(chǔ)器，存儲(chǔ)器接口384 位，存儲(chǔ)器帶寬144GB/s，通過(guò)PCIe×16 Gen2 接口與主機(jī)相連。

4.2 真實(shí)數(shù)據(jù)集測(cè)試

使用UCI 上的真實(shí)數(shù)據(jù)集Spambase 進(jìn)行聚類測(cè)試［16］。該數(shù)據(jù)集具有4601 個(gè)數(shù)據(jù)樣本，每個(gè)樣本具有57 個(gè)維度。實(shí)驗(yàn)中聚類的劃分個(gè)數(shù)k 分別為10、20 和50，進(jìn)行三組實(shí)驗(yàn)，每組實(shí)驗(yàn)算法各運(yùn)行10 次，統(tǒng)計(jì)聚類過(guò)程中樣本指派/更新聚類中心的耗時(shí)比值S1/S2 平均值、聚類迭代過(guò)程的平均耗時(shí)和優(yōu)化后的算法的加速比。

表1 Spambase數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

由實(shí)驗(yàn)可以看出，隨著k 的增加，S1/S2 的比值增大，即在GPU 上的計(jì)算耗時(shí)占比增大。利用數(shù)據(jù)并行策略，將聚類數(shù)據(jù)劃分一部分到主控端CPU上，充分利用多核CPU 的計(jì)算能力，能夠?yàn)樗惴铀佟?/p>

4.3 人工生成數(shù)據(jù)集測(cè)試

為了評(píng)估文本提出的數(shù)據(jù)并行策略在樣本維度增加和聚類劃分個(gè)數(shù)增加時(shí)算法的性能，采用人工生成的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)集包括10、50 和100 維的100 000 個(gè)樣本，所有的樣本被指派到 10，50，100 個(gè)聚類中，一共進(jìn)行 9 組對(duì)比試驗(yàn)。每組實(shí)驗(yàn)算法各運(yùn)行10 次，統(tǒng)計(jì)聚類迭代過(guò)程的平均耗時(shí)作為評(píng)價(jià)指標(biāo)。實(shí)驗(yàn)結(jié)果如圖3。

圖3 運(yùn)行時(shí)間對(duì)比

圖4 顯示了9 組對(duì)比試驗(yàn)，每組對(duì)比試驗(yàn)的加速比，即本文提出的數(shù)據(jù)并行的優(yōu)化策略相對(duì)于傳統(tǒng)的基于CUDA 并行化的K-Means 算法的加速比。本文的優(yōu)化方法能獲得31% ～38%的性能提升。從圖4 中可以看出，隨著數(shù)據(jù)維度和聚類劃分個(gè)數(shù)的增加，加速比基本保持不變。

圖4 加速比比較

5 結(jié)語(yǔ)

本文研究基于CUDA 并行化的K-Means 聚類算法在CPU 和GPU 上的執(zhí)行特征，指出了聚類劃分個(gè)數(shù)對(duì)聚類在GPU 和CPU 上執(zhí)行時(shí)間比值的影響，從而提出了數(shù)據(jù)并行策略，對(duì)原有的基于GPU并行化的K-Means 聚類算法進(jìn)行優(yōu)化，利用GPU核函數(shù)與CPU 異步執(zhí)行的特征，通過(guò)將CPU 與GPU的計(jì)算重疊，減小了算法的執(zhí)行時(shí)間。實(shí)驗(yàn)證明，優(yōu)化的算法有很好的加速比。隨著CPU性能的提升，多核CPU 的普及，CPU 和GPU 異構(gòu)計(jì)算中，作為主機(jī)端的CPU計(jì)算性能不斷提升，本文在研究加速計(jì)算時(shí)，在使用GPU 作為加速部件的同時(shí)，進(jìn)一步挖掘了主機(jī)端CPU的計(jì)算能力，提高了算法的并行性。本文的下一步研究工作是深入研究CPU和CPU異步計(jì)算的模式，以提高其他聚類算法的并行化。