摘  要： 使用Intel Parallel Amplifier高性能工具，針對模糊C均值聚類算法在多核平臺的性能問題，找出串行程序的熱點和并發(fā)性，提出并行化設(shè)計方案?；贗ntel并行庫TBB（線程構(gòu)建模塊）和OpenMP運行時庫函數(shù)，對多核平臺下的串行程序進行循環(huán)并行化和任務(wù)分配的并行化設(shè)計。

　　并行性主要是指同時性或并發(fā)性，并行處理是指對一種相對于串行處理的處理方式，它著重開發(fā)計算過程中存在的并發(fā)事件。并行性通常劃分為作業(yè)級、任務(wù)級、例行程序或子程序級、循環(huán)和迭代級以及語句和指令級。作業(yè)級的層次高，并行處理粒度粗。粗粒度開并行性開發(fā)主要采用MIMD方式，而細粒度并行性開發(fā)則主要采用SIMD方式。開發(fā)計算機并行性的方法主要有：資源重復(fù)、時間重疊和資源共享三種方法。

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

　　多核架構(gòu)能夠使用的軟件更出色地運行，并創(chuàng)建一個促進未來的軟件編寫更趨完善的架構(gòu)。盡管認真的軟件廠商還在探索全新的軟件并發(fā)處理模式，但是，隨著向多核處理器的移植，已有軟件無需被修改就可支持多核平臺。操作系統(tǒng)專為充分利用多個處理器而設(shè)計，且無需修改就可運行。為了充分利用多核技術(shù)，應(yīng)用開發(fā)人員需要在程序設(shè)計中融入更多思路，但設(shè)計流程與對稱多處理 （SMP） 系統(tǒng)的設(shè)計流程相同，并且單線程應(yīng)用也繼續(xù)運行。

　　多內(nèi)核（multicore chips）是指在一枚處理器（chip）中集成兩個或多個完整的計算引擎（內(nèi)核）。多核技術(shù)的開發(fā)源于工程師們認識到，僅僅提高單核芯片（one chip）的速度會產(chǎn)生過多熱量且無法帶來相應(yīng)的性能改善，先前的處理器產(chǎn)品就是如此。他們認識到，在先前產(chǎn)品中以那種速率，處理器產(chǎn)生的熱量很快會超過太陽表面。即便是沒有熱量問題，其性價比也令人難以接受，速度稍快的處理器價格要高很多。

　　模糊C均值聚類算法（FCM）是一種常用的聚類算法，在大規(guī)模數(shù)據(jù)分析、數(shù)據(jù)挖掘、模式識別、圖像處理等領(lǐng)域有著非常廣泛的應(yīng)用。它是給定分類數(shù)，通過優(yōu)化目標(biāo)函數(shù)得到樣本點對聚類中心的隸屬度，把目標(biāo)函數(shù)迭代的過程和處理數(shù)據(jù)的過程并行化，提高聚類過程的效率及多核處理器的利用率。實驗結(jié)果表明，本方法減少了程序的運行時間，顯示了多核編程的高效性。

　　1 模糊C均值聚類算法（FCM）

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

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

　?。?）如果目標(biāo)函數(shù)的改變量小于？棕，停止算法，否者重復(fù)（2）直到改變量小于？棕。為了確保FMC得到一個解，要不斷調(diào)整隸屬度矩陣，需多次運行該算法。

　　2 多核技術(shù)與工具軟件

　　2.1 Intel Parallel Amplifier高性能工具

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

　　（1）熱點（Hotspot）分析：運行熱點分析可收集到不同類型的數(shù)據(jù)，確定應(yīng)用程序運行消耗的時間，以及識別出耗時的函數(shù)。在執(zhí)行程序時，IPA通過數(shù)據(jù)收集器定期采樣，并在操作系統(tǒng)的協(xié)作下中斷程序收集數(shù)據(jù)。它通過獲取整個程序各個CPU的指令指針（IP）采樣，計算出每個函數(shù)的運行時間，再用調(diào)用棧采樣為程序創(chuàng)建調(diào)用關(guān)系樹。

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

　?。?）鎖定和等待（Locks and Waits）分析：在前兩種分析的基礎(chǔ)上，運行鎖定和等待分析，可獲得更多的程序運行數(shù)據(jù)。

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

　　2.2 TBB線程構(gòu)建模塊

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

　　2.3 OpenMP并行編程模型

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

　　3 C均值聚類算法的并行優(yōu)化設(shè)計

　　3.1 基本流程

　　C均值聚類算法串行程序的并行化設(shè)計可分為以下幾個階段：首先用IPA高性能工具得到熱點函數(shù)的花費時間和并行情況，分析串行程序的可并行性[5]；然后運用TBB和OpenMP進行并行優(yōu)化設(shè)計；使用IPA的Compare Results功能進行比較，測試并行程序的性能效果?；玖鞒倘鐖D1所示。

　　3.2 熱點定位

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

　　3.3 并發(fā)性分析

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

　　實行并行性的緣故，由于計算機和外部的設(shè)備不匹配，輸入和輸出極大地影響了效率。類如一臺計算機的內(nèi)存里只有一個程序在運行，該程序還不能處理的他為擁有的數(shù)據(jù)，并且只有在他獲得數(shù)據(jù)后他可以繼續(xù)執(zhí)行下一步操作，影戲這個程序必須等待輸入或輸出。既然這個程序控制著個計算機，那么計算機也必須等待。使得一個計算機等待時間要遠超過他處理數(shù)據(jù)實花的時間。為啥倆個程序不可以同時放進內(nèi)存呢？一旦如此，程序A等待數(shù)據(jù)時，處理器就可以轉(zhuǎn)向程序B。還可以繼續(xù)推廣，有倆個或更多的程序裝入內(nèi)存以便更好的利用內(nèi)存。一般來說，裝入內(nèi)存的程序越多，處理器的利用率也就越高。

　　3.4 串行程序優(yōu)化

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

　?。?）因為隸屬度矩陣的歸一化和樣本矩陣的標(biāo)準(zhǔn)化沒有數(shù)據(jù)相關(guān)性，所以可以利用OpenMP的工作分區(qū)功能在兩個線程中同時執(zhí)行運算，提高多核的利用率，節(jié)省程序運行時間。使用OpenMP的優(yōu)化設(shè)計：

　　#include <omp.h>

　　初始化數(shù)據(jù)

　　#pragma omp parallel sections//工作分區(qū)

　　{#pragma omp setion

　　樣本數(shù)據(jù)標(biāo)準(zhǔn)化

　　#pragma omp section

　　隸屬度矩陣歸一化}

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

　　#include “tbb/taske_scheduler_init.h”

　　# include ”tbb/parallel_for.h”

　　#include ”tbb/blocked_range2d.h”

　　task_scheduler_init init；//初始化對象

　　{//矩陣相乘的tbb并行化

　　parallelMul（）double c， double a，double b}{parallel _for（blocked_range2d<size_t> （0，k，0，n），MatrixlMul（c，a，b））；}

　　}

　　4 實驗結(jié)果測試

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

　　（1）實驗平臺

　　硬件：Intel Pentium Dual T3400 @2.16 GHz 2.16 GHz，2 GB內(nèi)存。

　　軟件：Microsoft Windows XP professional service pack3操作系統(tǒng)；Visual.Studio.2008英文版；parallel_studio_ sp1_setup（評估版）；tbb22_009oss_win（TBB2.2版本）[8]。

　　為了檢測并行優(yōu)化的效果，要對測試結(jié)果、熱點、并發(fā)性和串行程序進行對比。

　　（2）實驗結(jié)果

　　經(jīng)過實驗測試獲得Wine數(shù)據(jù)集3個分類的樣本數(shù)，分別為59、64、48，與標(biāo)準(zhǔn)分類相比誤差很小。本文通過5次運行FMC得到的實驗結(jié)果相同，說明模糊C均值算法的并行優(yōu)化設(shè)計是可行的。

　　（3）熱點對比

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

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

　?。?）并發(fā)性對比

　　幷發(fā)的實質(zhì)是一個物理CPU（也可以多個物理CPU）在若干道程序之間多路復(fù)用，并發(fā)性是對有限物理資源強制行駛多用戶共享以提高效率。實現(xiàn)幷發(fā)技術(shù)的關(guān)鍵之一是如何對系統(tǒng)內(nèi)的多個活動（進程）進行切換。并行性指的是兩個或兩個以上的事件或活動在同一時刻發(fā)生。在多道程序環(huán)境下，并行性使多個程序同一時刻可在不同CPU上同時執(zhí)行。并行性和并發(fā)性的區(qū)別：并行的時間或者活動一定是幷發(fā)的，但是反之并發(fā)的時間或者活動未必是并行的。并行性是并發(fā)性的特例，而并發(fā)性是并行性的拓展。

　　從圖4可以看到并行程序的并發(fā)效果。熱點函數(shù)Update并行后不僅時間減少了，狀態(tài)也由Poor變?yōu)镮deal。說明當(dāng)熱點函數(shù)運行時，其他線程同時運行在多核處理器上，多核利用率得到提高。

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