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

丁芙蓉 張功萱

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

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

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

2 相關算法與技術

2.1 K-Means聚類算法

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

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

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

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

4）判斷是否滿足收斂準則，不滿足跳轉至步驟2），否則算法收斂，中止算法。

2.2 CUDA程序設計模型

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

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

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

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

3.1 算法存在問題

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

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

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

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

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

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

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

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

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

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

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

3）當更新聚類中心updateCentroids（）完成后，要置cpu_finish為0，進行復位。

算法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 實驗與分析

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

4.1 實驗環(huán)境

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

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

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

表1 Spambase數(shù)據(jù)集實驗結果

由實驗可以看出，隨著k 的增加，S1/S2 的比值增大，即在GPU 上的計算耗時占比增大。利用數(shù)據(jù)并行策略，將聚類數(shù)據(jù)劃分一部分到主控端CPU上，充分利用多核CPU 的計算能力，能夠為算法加速。

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

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

圖3 運行時間對比

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

圖4 加速比比較

5 結語

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