模糊C均值聚類算法的并行化研究*

張建強，鄭曉薇，吳華平

(遼寧師范大學 計算機與信息技術學院，遼寧 大連 116081)

多核處理器的迅速發展，使得多核化不斷全面普及。為了應對計算機硬件的發展要求，盡可能利用多核資源，就要設計出相應的并行化應用程序。多核平臺下的并行化有多種方案，利用英特爾推出的高性能分析工具Intel ParallelAmplifier對串行應用程序進行性能分析，尋出熱點實現并行化是其中的一種方法。

模糊C均值聚類算法(FCM)是一種常用的聚類算法，在大規模數據分析、數據挖掘、模式識別、圖像處理等領域有著非常廣泛的應用。它是給定分類數，通過優化目標函數得到樣本點對聚類中心的隸屬度，尋找樣本點的最佳分類方案。本文將多核技術應用到模糊C均值聚類并行算法的設計中，把目標函數迭代的過程和處理數據的過程并行化，提高聚類過程的效率及多核處理器的利用率。實驗結果表明，本方法減少了程序的運行時間，顯示了多核編程的高效性。

1 模糊C均值聚類算法(FCM)

模糊C均值聚類算法[1]的基本思想是確定每個樣本數據隸屬于某個聚類的程度，把隸屬程度相似的樣本數據歸為一個聚類。FCM 把 n個樣本集合 X={x1，x2，...，xn}分為c個模糊組，并且求每組的聚類中心Ci(i=1，2，…c)，使得目標函數最小，該算法是優化目標函數的迭代過程。這個過程從一個隨機的隸屬度矩陣開始，確定聚類中心計算目標函數，通過迭代過程達到樣本分類。

初始化：給定樣本數 n，聚類數c∈[2，n]，模糊度m=2，迭代停止閾值 ω。

(2)計算聚類中心

(3)對模糊C均值進行迭代運算，返回目標函數的值。目標函數的形式為：

其中 dij=‖ci-data(i，j)‖為聚類中心與樣本點的歐幾里得距離。

(4)如果目標函數的改變量小于 ω，停止算法，否者重復(2)直到改變量小于ω。為了確保FMC得到一個最優解，要不斷調整隸屬度矩陣，需多次運行該算法。

2 多核技術與工具軟件

2.1 Intel Parallel Amplifier高性能工具

Intel Parallel Amplifier是英特爾在2009年發布的高性能工具[2]，界面設計友好，操作簡單方便。開發人員只需要運行工具就可對串行程序進行分析，研究分析結果進行并行化設計，確保多核的完全利用。IPA(Intel Parallel Amplifier)有以下三種類型的性能分析。

(1)熱點(Hotspot)分析：運行熱點分析可收集到不同類型的數據，確定應用程序運行消耗的時間，以及識別出最耗時的函數。在執行程序時，IPA通過數據收集器定期采樣，并在操作系統的協作下中斷程序收集數據。它通過獲取整個程序各個CPU核心的指令指針(IP)采樣，計算出每個函數的運行時間，再用調用棧采樣為程序創建調用關系樹。

(2)并發性(Concurrency)分析：運行并發性分析可確定應用程序是否有效地利用了所有可執行核，識別出最有可能并行化的串行代碼。它與熱點分析一樣收集數據信息，但是要比熱點分析多，除了一般的程序運行數據，還有所有可執行核的工作情況。最理想的情況是執行程序的線程數等于處理器的可執行核數，也就是完全利用(Fully Utilized)。

(3)鎖定和等待(Locks and Waits)分析：在前兩種分析的基礎上，運行鎖定和等待分析，可獲得更多的程序運行數據。

為了測試程序并行優化的效果，IPA提供了“比較結果(Compare Results)”的功能，用來比較串行程序和并行程序性能差別。

2.2 TBB線程構建模塊

TBB線程構建模塊 (Intel Thread Building Blocks)是基于GPLv2開源的、用來實現并行語義的C++模板庫[3]。TBB提供了高性能可擴展的算法，面向任務編程，支持任何ISO C++編譯器，具有很好的可移植性。本文將Intel并行庫 TBB的 tbb_block_rang2d和 tbb_parallel_for配合使用，前者的作用是對一個二維的半開區間進行可遞歸的粒度劃分；后者的作用可以實現負載均衡的并行執行固定數目獨立循環迭代體。

2.3 OpenMP并行編程模型

OpenMP是為共享內存以及分布式共享內存設計的多線程并行編程應用接口，包含了一套編譯語句以及一個函數庫，是一個編譯指令和庫函數的集合[4]。OpenMP也可以用于多核處理器并行程序設計中。在OpenMP中線程的創建是通過編譯指導語句實現的，本文采用sections和section命令。sections被稱作工作分區編碼，它定義了一個工作分區，然后由section將工作區劃分成幾個不同的工作段，每個工作段都由多核處理器的每個執行核并行執行。

3 C均值聚類算法的并行優化設計

3.1 基本流程

C均值聚類算法串行程序的并行化設計可分為以下幾個階段：首先用IPA高性能工具得到熱點函數的花費時間和并行情況，分析串行程序的可并行性[5]；然后運用TBB和OpenMP進行并行優化設計；最后使用IPA的Compare Results功能進行比較，測試并行程序的性能效果。基本流程如圖1所示。

圖1 運行Intel Parallel Amplifier流程框架

3.2 熱點定位

通過“Hotspot”可以獲得熱點函數所花費的時間，調用棧信息可以得到它被不同函數調用花費的時間。IPA采集的數據為程序段花費的總時間、CPU運行的時間、CPU空閑時間、處理器的核數、執行程序的線程數等。找到熱點函數后，打開源代碼，分析哪些代碼花費處理器時間最多。

3.3 并發性分析

Concurrency分析可以得到熱點函數在執行過程中各個其他任務并行執行的情況，以及各個線程的任務分配情況。IPA并發性分析不僅包含熱點采集的時間數據，更重要的是程序的并發狀態。它用5種不同狀態(Idle、Poor、Ok、Ideal、Over)表示并發性的情況。在多核平臺下，理想的狀態應該達到Ok以上，也就是說當熱點函數運行時，其他線程同時工作在處理器上，這樣可以提高多核資源的利用率。

3.4 串行程序優化

通過分析源代碼，可以對串行程序進行如圖2所示的并行優化。

圖2 并行優化流程圖

(1)因為隸屬度矩陣的歸一化和樣本矩陣的標準化沒有數據相關性，所以可以利用OpenMP的工作分區功能在兩個線程中同時執行運算，提高多核的利用率，節省程序運行時間。使用OpenMP的優化設計：

(2)歸一化后的隸屬度矩陣和標準化的樣本數據做矩陣乘法的運算，可以使用TBB并行庫進行優化設計[6-7]。TBB：：block_range2d表示的是二維迭代空間的模板類，它包含在頭文件TBB/blocked_range.h中，作用是根據需求對并行任務正確的劃分。因為矩陣相乘是二維空間的運算，因此采用block_range2d模板類。迭代空間劃分好后，就可以使用 TBB：：parallel_for執行并行操作。parallel_for包含在頭文件TBB/parallel_for.h中，作用是對循環體進行并行化處理。使用TBB的優化設計：

4 實驗結果測試

本文采用UCI標準數據集中的Wine數據集作為測試實例，該數據集包含有178個樣本，每個樣本有13個屬性特征，分為 3類，每類分別為 59，71，48，數據為178×13的矩陣。設定加權指數 m=2，停止閾值ω=le-4。

(1)實驗平臺

硬件：Intel Pentium Dual T3400@2.16 GHz 2.16 GHz，2 GB內存。

軟件：Microsoft Windows XP professional service pack3操作系統；Visual.Studio.2008英文專業版；parallel_studio_sp1_setup(評估版)；tbb22_009oss_win(TBB2.2 版 本)[8]。

為了檢測并行優化的效果，要對測試結果、熱點、并發性和串行程序進行對比。

(2)實驗結果

經過實驗測試獲得Wine數據集3個分類的樣本數，分別為59、64、48，與標準分類相比誤差很小。本文通過5次運行FMC得到的實驗結果相同，說明模糊C均值算法的并行優化設計是可行的。

(3)熱點對比

從圖3可以看到并行后熱點函數Update執行時間減少為15.321 ms，這是由于Update函數中有二維矩陣的并行化設計。在雙核平臺下，串行程序的線程數為1，而并行程序的線程數為3。

表1是IPA中 Compare Results功能的比較結果，各項時間的差值都為正數，表明性能提高。

表1 時間性能比較

(4)并發性對比

從圖4可以看到并行程序的并發效果。熱點函數Update并行后不僅時間減少了，狀態也由Poor變為Ideal。說明當熱點函數運行時，其他線程同時運行在多核處理器上，多核利用率得到提高。

本文將Intel多核高性能工具應用到FMC串行程序的并行優化設計中，提出并行優化設計方案，把TBB和OpenMP引入到聚類算法的并行化設計中。并行聚類算法在處理海量數據時將大大節省時間，并且提高多核資源的利用率。下一步的工作是從并行算法的可擴展性進行探究，并在眾核處理器上做進一步測試，以便更好地提高聚類算法效率。

[1]齊淼，張化祥.改進的模糊 c均值聚類算法研究[J].計算機工程與應用，2009，45(20)：133-135.

[2]英特爾@軟件網絡[EB/OL].http：//software.intel.com/enus/intel-parallel-studio-home.

[3]REINDERS J. Intel threading building blocks[M].O’REILLY出版社，2007.

[4]周偉明.多核計算與程序設計[M].武漢：華中科技大學出版社，2009.

[5]Peter Wang.使用Intel parallel Amplifier：一站式解決最佳方案[EB/OL].http：//software.intel.com/zh-cn/blogs2010-2-22.

[6]曹婷婷.基于多核處理器串行程序并行化改造和性能分析[D].成都：西南交通大學，2009.

[7]胡斌，袁道華.TBB多核編程及其混合編程模型的研究[J].計算機技術與發展，2009，19(2)：89-101.

[8]Intel公司.Intel threading building blocks reference manual[EB/OL].2007.http：//threadingbuildingblocks.org/.