基于GPU的二部圖聯(lián)合聚類(lèi)并行算法研究

張宇，劉坡，楊敏華，龔建華，3，黃明詳

（1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙 410083；2.中國(guó)科學(xué)院遙感與數(shù)字地球研究所遙感科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101；3.浙江中科空間信息技術(shù)應(yīng)用研發(fā)中心，浙江 嘉興 314100；4.環(huán)境保護(hù)部信息中心，北京 100101）

0 引言

空間聚類(lèi)作為聚類(lèi)分析的一個(gè)研究方向，是指將空間數(shù)據(jù)集中的對(duì)象分成由相似對(duì)象組成的類(lèi)，同類(lèi)中的對(duì)象間具有較高的相似度，而不同類(lèi)中的對(duì)象間差異較大［1］。空間聚類(lèi)分析是空間數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)的主要手段之一，已廣泛應(yīng)用于地理學(xué)、地質(zhì)學(xué)、氣象學(xué)、地圖學(xué)、天文學(xué)及公共衛(wèi)生等諸多領(lǐng)域。但是由于空間數(shù)據(jù)的多尺度、高維度、模糊性等特點(diǎn)，造成空間聚類(lèi)算法的創(chuàng)新研究困難較大。

二部圖聚類(lèi)算法作為空間聚類(lèi)算法的一種，以圖的形式表明數(shù)據(jù)集中數(shù)據(jù)間的關(guān)系，用以尋找不同要素間的對(duì)應(yīng)關(guān)系。要素集合根據(jù)不同的原則分割成2個(gè)不同的候選集合，候選集中每個(gè)要素具有相近的空間關(guān)系或者非空間關(guān)系，二部圖聚類(lèi)算法旨在探究?jī)蓚€(gè)或多個(gè)要素集中要素間的相關(guān)性，廣泛應(yīng)用于文本查詢和檢索等領(lǐng)域［2，3］。二部圖也應(yīng)用于解決空間聚類(lèi)問(wèn)題，利用距離、邊距以及相應(yīng)的B矩陣來(lái)獲得空間聚類(lèi)知識(shí)，利用圖嵌入方法進(jìn)行影像分類(lèi)［4］。利用二部圖聯(lián)合聚類(lèi)分割可以解決異質(zhì)數(shù)據(jù)的聯(lián)合聚類(lèi)分割問(wèn)題［5，6］。海量空間數(shù)據(jù)的本身需要大量運(yùn)算，現(xiàn)有的基于CPU的串行計(jì)算很難達(dá)到實(shí)時(shí)計(jì)算的要求，傳統(tǒng)的采用建立空間索引的方法來(lái)加速搜索效率［7－9］，如文獻(xiàn)［10］中提出了基于空間聯(lián)合索引計(jì)算鄰接矩陣的方法來(lái)計(jì)算空間聚類(lèi)簇，該方法基于頁(yè)訪問(wèn)序列，利用了限制的緩沖空間，通過(guò)啟發(fā)式的對(duì)稱(chēng)聚類(lèi)等方法獲得類(lèi)別空間信息。GPU的出現(xiàn)，帶來(lái)了高性能計(jì)算的時(shí)代，統(tǒng)一計(jì)算設(shè)備架構(gòu)（CUDA）的推出，為高性能計(jì)算開(kāi)創(chuàng)了新時(shí)代［11，12］。文獻(xiàn)［13］將 GPU 引入 K均值聚類(lèi)算法中，利用GPU高度并行的特點(diǎn)可以明顯提高聚類(lèi)的速度。

多源空間數(shù)據(jù)的匹配，是空間數(shù)據(jù)合并、更新的基礎(chǔ)，具有巨大的研究?jī)r(jià)值，而且多源空間數(shù)據(jù)匹配問(wèn)題本身就是空間數(shù)據(jù)聚類(lèi)的問(wèn)題［14］。本文將GPU引入二部圖匹配的聯(lián)合聚類(lèi)算法的過(guò)程中，以多源空間數(shù)據(jù)的匹配為例，首先將空間數(shù)據(jù)的匹配分解成一個(gè)二部圖匹配的問(wèn)題，進(jìn)而驗(yàn)證GPU并行計(jì)算對(duì)空間聚類(lèi)算法效率的影響和不同儲(chǔ)存器對(duì)計(jì)算效率的影響。

1 二部圖聯(lián)合聚類(lèi)

二部圖G（V，E）表示要素間的空間關(guān)系，其中V用于表示空間要素索引的節(jié)點(diǎn)，E用于表示有關(guān)系空間要素索引的連線。如果空間中的兩個(gè)要素集中要素存在關(guān)系，則有E≠0，E將這兩個(gè)空間要素連接起來(lái)。如圖1a、圖1b所示，用A、B兩個(gè)地理要素集合表示同一個(gè)地區(qū)不同時(shí)相的數(shù)據(jù)，數(shù)據(jù)集A中包含有要素（A1，A2，A3），數(shù)據(jù)集B 中包含有要素（B1，B2，B3），可以用圖1c表示要素之間的疊置關(guān)系。該問(wèn)題是一個(gè)典型的二部圖聯(lián)合聚類(lèi)問(wèn)題，可用二部圖聚類(lèi)算法判定空間要素間的對(duì)應(yīng)關(guān)系。

圖1 基于疊置關(guān)系的空間聚類(lèi)Fig.1 Co－clustering based on overlay relationship

二部圖聚類(lèi)算法主要的流程如圖2所示：1）計(jì)算要素間的空間關(guān)系，本文以疊置關(guān)系為判斷依據(jù)。2）根據(jù)要素的空間關(guān)系，構(gòu)建二部圖關(guān)系，即構(gòu)建關(guān)系矩陣及鄰接矩陣。3）根據(jù)鄰接矩陣，進(jìn)行二部圖聯(lián)合聚類(lèi)，每次聚類(lèi)后計(jì)算判斷矩陣中非0要素的數(shù)目的變化，直到要素的數(shù)目不變?yōu)橹埂?）根據(jù)最終的聯(lián)合聚類(lèi)結(jié)果，提取不同要素間的對(duì)應(yīng)關(guān)系。

圖2 二部圖聚類(lèi)Fig.2 Bipartite graph co－clustering

1.1 空間關(guān)系

確定兩個(gè)要素集間的拓?fù)潢P(guān)系和權(quán)重是構(gòu)建二部圖的基礎(chǔ)?？臻g拓?fù)潢P(guān)系一般采用9交模型描述空間數(shù)據(jù)的拓?fù)潢P(guān)系［15］。為了加快計(jì)算的速度，可利用plane－sweep［7］、TR＊樹(shù)［8］和R樹(shù)［9］等算法建立空間索引以加快要素空間關(guān)系的搜索，本文主要計(jì)算要素之間的疊置關(guān)系。

1.2 構(gòu)建二部圖

確定兩個(gè)地理要素集中每個(gè)要素的對(duì)應(yīng)關(guān)系之后，需要進(jìn)一步將有關(guān)系的要素都集中到同一個(gè)空間要素簇下。Huh等提出利用鄰接關(guān)系矩陣計(jì)算空間要素的聚類(lèi)集［14］?？臻g數(shù)據(jù)之間多對(duì)多關(guān)系由于涉及兩個(gè)要素集中的多個(gè)要素，較難確定聚類(lèi)集。這可以通過(guò)如下的過(guò)程來(lái)判斷：假設(shè)一個(gè)要素集中的要素與另一個(gè)要素集中的多個(gè)要素重疊，則將多個(gè)要素合并為一個(gè)連續(xù)要素，如果這個(gè)合并要素又與前一個(gè)要素集中的多個(gè)要素重疊，多個(gè)重疊要素同樣進(jìn)行合并，反復(fù)進(jìn)行這個(gè)過(guò)程直到得到合并要素的關(guān)系為1∶1為止［14］。假定兩個(gè)地理要素集分別為Ai（i＝0，1，2，3，…，m），Bj（j＝0，1，2，…，n），對(duì)于每個(gè)地理要素集中的要素，都有Ai∈A，Bj∈B。如果兩個(gè)要素存在疊置關(guān)系，則Ai與Bj在二部圖上存在邊，Ai與Bj的地理編碼可視為連接邊兩端的節(jié)點(diǎn)。假設(shè)二部圖中兩地理要素集中要素間的邊權(quán)重都為1，構(gòu)建關(guān)系矩陣C。其中，C中每一行表示要素集A中每個(gè)要素的地理編碼，C中每一列表示要素集B中每個(gè)要素的地理編碼，用于表示Ai與Bj的疊置關(guān)系，可表示為：

在圖1中，假設(shè)數(shù)據(jù)集A和B中要素間對(duì)應(yīng)關(guān)系為（A1，B2，B3），（A2，A3，B3），由于要素集A 中要素記錄為矩陣C中的行，要素集B中要素記錄為矩陣C中的列，矩陣C表示為：

構(gòu)建鄰接矩陣C′，其中I為單位矩陣，C′表示節(jié)點(diǎn)間所有的鄰接關(guān)系（包括自相鄰關(guān)系）：

1.3 矩陣運(yùn)算和確定關(guān)系

對(duì)鄰接矩陣C′連續(xù)自乘，直到所有為0的元素值不再發(fā)生變化，便可得到結(jié)果矩陣，其中每一行非0實(shí)體表現(xiàn)出要素間的鄰接關(guān)系。圖1中的鄰接矩陣C′自乘3次后，矩陣元素為0的位置不再發(fā)生變化。為了簡(jiǎn)化計(jì)算結(jié)果，將矩陣中所有的非0元素表示為1，結(jié)果矩陣C″表示C′自乘3次之后的結(jié)果，如式（4）所示：

其中：C″的第一行表示得到空間聚類(lèi)簇（A1，A2，A3）與（B2，B3）間3∶2的對(duì)應(yīng)關(guān)系。第四行中，只有一個(gè)要素，其余位置處均為0，對(duì)應(yīng)的要素為B1，表示要素集A中沒(méi)有任何要素與B1對(duì)應(yīng)。

2 GPU并行算法設(shè)計(jì)

CUDA的基本思想是將應(yīng)用程序映射到GPU以獲得較大的性能提升，盡量的開(kāi)發(fā)線程級(jí)并行算法，將GPU作為超大規(guī)模數(shù)據(jù)并行協(xié)處理器，讓GPU運(yùn)行一些能夠被高度線程化的程序，充分發(fā)揮GPU并行處理能力并極大提高單個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算性能。CUDA采用單指令多線程（SIMT）執(zhí)行模型，執(zhí)行數(shù)據(jù)寬度將作為硬件細(xì)節(jié)被隱藏起來(lái)，硬件可以自動(dòng)地適應(yīng)不同執(zhí)行寬度，而且每個(gè)線程的寄存器是私有的，線程間只能通過(guò)共享存儲(chǔ)器和同步機(jī)制通信。GPU采用的是由硬件管理的輕量級(jí)線程，實(shí)現(xiàn)零開(kāi)銷(xiāo)線程切換，用計(jì)算隱藏延遲。

2.1 并行算法設(shè)計(jì)分析

由于空間數(shù)據(jù)計(jì)算數(shù)量的擴(kuò)大，導(dǎo)致構(gòu)建鄰接矩陣的維度增大，計(jì)算速度降低。采用GPU并行加速算法，計(jì)算時(shí)間和電腦資源的開(kāi)銷(xiāo)將會(huì)減少?？梢岳肎PU高度并行的特點(diǎn)快速提高二部圖聚類(lèi)算法過(guò)程中的鄰接矩陣運(yùn)算效率，主要包括矩陣自乘和計(jì)算矩陣中非0的個(gè)數(shù)。

2.1.1 矩陣自乘并行性分析 假設(shè)一個(gè)M×N大小的關(guān)系矩陣C，其鄰接矩陣C′大小為（M＋N）×（M＋N）。對(duì)于矩陣自乘，由于每個(gè)要素都是獨(dú)立計(jì)算的，理論上可同時(shí)運(yùn)行（M＋N）×（M＋N）線程來(lái)同步計(jì)算，但是由于硬件的限制，每次啟動(dòng)的線程塊和每個(gè)塊中線程的數(shù)量都有限制。每一個(gè)內(nèi)核的配置項(xiàng)包括問(wèn)題的分塊數(shù)griddim及每個(gè)塊內(nèi)的線程數(shù)目blockdim，增加線程塊中線程數(shù)目可能會(huì)降低在多處理器中投入運(yùn)行的實(shí)際線程塊數(shù)，降低并行度。假設(shè)矩陣計(jì)算中每個(gè)塊的大小為Width×Length，鄰接矩陣可以劃分為（M＋Width－1）／16×（N＋Length－1）／16個(gè)塊，每個(gè)塊中有Width×Length線程執(zhí)行計(jì)算。

GPU以warp為單位調(diào)度和執(zhí)行，每個(gè)warp擁有32個(gè)線程，若線程調(diào)度數(shù)目不足32個(gè)，則會(huì)因warp塊填充不足而造成計(jì)算資源的浪費(fèi)，損失部分效率。而對(duì)于存儲(chǔ)器的訪問(wèn)，是以half－warp為單位進(jìn)行的，因此提高運(yùn)算效率就要使劃分的線程矩陣維度為16的倍數(shù)。對(duì)于GeForce 9800GT，由于每個(gè)SM（流多處理器）中最多有768個(gè)線程，8個(gè)SP（流處理器），處理效率最佳時(shí)，線程塊的數(shù)目應(yīng)滿足768／（Width×Length）＜8。

2.1.2 計(jì)算矩陣非0元素并行性分析 當(dāng)鄰接矩陣相乘次數(shù)大于等于2時(shí)，需要判斷矩陣中非0元素的個(gè)數(shù)。對(duì)于（M＋N）×（M＋N）要素的鄰接矩陣非0元素個(gè)數(shù)的計(jì)算，可視為并行歸約的過(guò)程?？梢詫⒃撗h(huán)計(jì)算分解為（M＋N）×（M＋N）線程以完成計(jì)算，考慮不同的分塊和分線程完成計(jì)算，假設(shè)每個(gè)塊中有512個(gè)線程，過(guò)程如下：第一次循環(huán)，只有i＝0，2，4，…，510線程執(zhí)行計(jì)算，即每個(gè)線程與其后跨度為1的元素加操作；第二次循環(huán)，只有i＝0，4，8，12，…，508線程執(zhí)行計(jì)算，即每個(gè)要素與其后跨度為2的元素加操作；依次類(lèi)推……直到最后一次循環(huán)，即i＝0線程執(zhí)行計(jì)算。此時(shí)線程i＝0中記錄的結(jié)果即為要素中非0元素的個(gè)數(shù)。

2.2 并行算法設(shè)計(jì)優(yōu)化

CUDA內(nèi)部存在6種存儲(chǔ)器，分別是寄存器、局部存儲(chǔ)器、共享存儲(chǔ)器、全局存儲(chǔ)器、常數(shù)存儲(chǔ)器和紋理存儲(chǔ)器，應(yīng)依據(jù)具體研究?jī)?nèi)容選擇合適的存儲(chǔ)設(shè)備從而最大限度地提高算法的效率，本文探討采用全局存儲(chǔ)器和共享存儲(chǔ)器完成計(jì)算。

2.2.1 全局存儲(chǔ)器 全局存儲(chǔ)器使用的是普通的顯存，存儲(chǔ)內(nèi)核中輸入輸出數(shù)據(jù)，容量較大，整個(gè)網(wǎng)格中的任意線程都能讀寫(xiě)全局存儲(chǔ)器的任意位置。在計(jì)算能力較低的GPU設(shè)備中，缺少對(duì)數(shù)據(jù)的緩存，采用全局存儲(chǔ)器操作數(shù)據(jù)時(shí)將導(dǎo)致400～600個(gè)時(shí)鐘周期的延遲，而且在計(jì)算過(guò)程中有許多重復(fù)的數(shù)據(jù)存儲(chǔ)訪問(wèn)。因此，必須最小化對(duì)全局存儲(chǔ)器的訪問(wèn)并應(yīng)設(shè)計(jì)考慮SM中數(shù)據(jù)重用。

使用全局存儲(chǔ)器進(jìn)行鄰接矩陣運(yùn)算時(shí)，GPU可實(shí)現(xiàn)在GPU－DRAM的任何位置讀取到GPU中的聚集操作。如果計(jì)算的矩陣大小不超過(guò)GPU的計(jì)算能力，可利用CUDA的API中的cudaMemcpy（）一次性將鄰接矩陣數(shù)據(jù)由內(nèi)存全部加載到GPU全局存儲(chǔ)器中。

2.2.2 共享存儲(chǔ)器 共享存儲(chǔ)器位于每個(gè)SM內(nèi)，同一個(gè)SM上的線程可訪問(wèn)一個(gè)共享存儲(chǔ)器，實(shí)現(xiàn)高速數(shù)據(jù)交換。通過(guò)線程間的合作，可以將全局存儲(chǔ)器的流量減少到原來(lái)的1／16，避免了數(shù)據(jù)的重復(fù)讀取和存儲(chǔ)，提高了運(yùn)算效率。共享存儲(chǔ)器位于GPU片內(nèi)，速度比局部存儲(chǔ)器、全局存儲(chǔ)器快很多。在不發(fā)生bank沖突的情況下，共享存儲(chǔ)器的延遲幾乎只有局部存儲(chǔ)器或全局存儲(chǔ)器的1／100，訪問(wèn)速度和寄存器相當(dāng)。對(duì)共享存儲(chǔ)器的訪問(wèn)是以半個(gè)warp為單位，訪問(wèn)將會(huì)以前16個(gè)線程或后16個(gè)線程的方式進(jìn)行。半warp中的線程訪問(wèn)的數(shù)組元素分別屬于不同bank時(shí)，不會(huì)發(fā)生訪問(wèn)沖突；當(dāng)半warp中的線程訪問(wèn)的數(shù)據(jù)元素處于同一個(gè)bank時(shí)，其讀寫(xiě)操作不能同時(shí)進(jìn)行，發(fā)生訪問(wèn)沖突，造成運(yùn)算錯(cuò)誤?？紤]到每個(gè)程序中字節(jié)的大小，算法以4的倍數(shù)設(shè)置進(jìn)行等間隔的訪問(wèn)以避免沖突。

共享存儲(chǔ)器在每個(gè)流處理器中只有16KB的存儲(chǔ)空間，算法要考慮到共享存儲(chǔ)器的大小。設(shè)計(jì)每個(gè)線程塊的共享空間大小為16×16，對(duì)于實(shí)驗(yàn)中處理的int類(lèi)型的變量，每個(gè)共享存儲(chǔ)空間中的數(shù)據(jù)小于16KB。若鄰接矩陣不超過(guò)GPU的運(yùn)算能力，則將鄰接矩陣全部調(diào)入全局存儲(chǔ)器中，每個(gè)SM中的共享存儲(chǔ)器分別對(duì)應(yīng)處理一個(gè)矩陣塊。根據(jù)矩陣元素的標(biāo)識(shí)將相應(yīng)的數(shù)據(jù)調(diào)入對(duì)應(yīng)的共享存儲(chǔ)器中進(jìn)行運(yùn)算，用矩陣塊Ai中的每一行乘以矩陣塊Bj中的每一列，并將計(jì)算結(jié)果按照數(shù)據(jù)對(duì)應(yīng)行列進(jìn)行相加計(jì)算，接著依次對(duì)該行列中相應(yīng)的矩陣塊相加，將結(jié)果保存在矩陣C中的相應(yīng)位置處。由于同一個(gè)線程塊共用一個(gè)共享存儲(chǔ)器，因此，每個(gè)線程塊中各線程可以重復(fù)利用加載到共享存儲(chǔ)器中的數(shù)據(jù)，減少了數(shù)據(jù)的重復(fù)存取。最后將運(yùn)算結(jié)果由全局存儲(chǔ)器載入到內(nèi)存中。

3 實(shí)驗(yàn)及分析

實(shí)驗(yàn)采用GeForce 9800GT顯卡，顯存容量為1 G，計(jì)算能力為1.1，時(shí)鐘頻率為1.50GHz，有12個(gè)流多處理器，每個(gè)流多處理器中有8個(gè)流處理器，每個(gè)流處理器中有16KB的共享存儲(chǔ)器。采用浙江海鹽地區(qū)不同時(shí)相的多尺度數(shù)據(jù)，驗(yàn)證本文的算法和不同配置情況下的GPU運(yùn)行效率。對(duì)于不同來(lái)源的空間數(shù)據(jù)，首先將其投影到統(tǒng)一的空間坐標(biāo)體系下，然后確定不同空間數(shù)據(jù)集間的拓?fù)浏B置關(guān)系，根據(jù)式（3）構(gòu)建鄰接矩陣，通過(guò)GPU并行計(jì)算確定要素之間的關(guān)系，得到空間聚類(lèi)結(jié)果。實(shí)驗(yàn)在vs2008.net環(huán)境下，利用 ArcEngine 9.3，CUDA Toolkit 5.0工具包開(kāi)發(fā)，并將并行算法封裝為動(dòng)態(tài)鏈接庫(kù)（DLL），完成整個(gè)實(shí)驗(yàn)過(guò)程。

3.1 CPU串行和GPU并行比較

針對(duì)同一個(gè)地區(qū)的多尺度和多時(shí)相的兩個(gè)地理要素集做空間聯(lián)合聚類(lèi)運(yùn)算，先執(zhí)行CPU串行計(jì)算，再分別執(zhí)行基于GPU全局存儲(chǔ)器和基于GPU共享存儲(chǔ)器的并行計(jì)算，計(jì)算時(shí)間統(tǒng)計(jì)如表1所示。

由表1可以看出，基于GPU共享存儲(chǔ)器的計(jì)算效率最高，其次是基于GPU全局存儲(chǔ)器的計(jì)算效率，而基于CPU串行計(jì)算的效率最低。利用GPU并行計(jì)算比利用CPU串行計(jì)算的執(zhí)行效率高。此實(shí)驗(yàn)中的鄰接矩陣大小為1 103×1 103，矩陣自乘次數(shù)為12次，矩陣元素類(lèi)型為整型，處理數(shù)據(jù)量大小為55.69MB，分別計(jì)算這三者的計(jì)算速率：1）GPU全局存儲(chǔ)器并行計(jì)算：55.69MB÷13.726s≈4.1 MB／s；2）GPU 共享存儲(chǔ)器并行計(jì)算：55.69MB÷0.9935s≈56.1MB／s；3）CPU串行計(jì)算：55.69MB÷853s≈0.065MB／s?？梢钥闯?，GPU共享存儲(chǔ)器運(yùn)算效率是GPU全局存儲(chǔ)器運(yùn)算效率的14倍，是CPU串行計(jì)算效率的858倍。在此類(lèi)情況下，GPU并行計(jì)算應(yīng)使用共享存儲(chǔ)器提高算法的效率。

表2是不同空間二部圖聯(lián)合聚類(lèi)中，執(zhí)行GPU共享存儲(chǔ)器計(jì)算與執(zhí)行CPU串行計(jì)算的時(shí)間和加速比。從表中可以看出，隨著矩陣維度的擴(kuò)大，對(duì)應(yīng)的循環(huán)次數(shù)不確定，并且加速比有增大的趨勢(shì)，但是達(dá)到一定的維度后，趨于穩(wěn)定。其中在矩陣維度為1 103時(shí)，加速比最大，表明此時(shí)GPU共享存儲(chǔ)器運(yùn)算效率是CPU串行計(jì)算效率的858倍。

表2 不同維度下的串并行性能比較Table 2 Comparison of serial and parallel performance under different dimensional

3.2 GPU在處理不同數(shù)據(jù)量時(shí)的效率

使用GPU共享存儲(chǔ)器在處理不同數(shù)據(jù)量時(shí)，進(jìn)行空間聚類(lèi)并行計(jì)算的效率有明顯的不同，實(shí)驗(yàn)選取同一地區(qū)的多時(shí)相、多尺度數(shù)據(jù)進(jìn)行空間二部圖聯(lián)合聚類(lèi)，統(tǒng)計(jì)結(jié)果如表3所示。由表3可知，由于空間要素聚類(lèi)關(guān)系的多樣性，構(gòu)建的鄰接矩陣的維度明顯不同，鄰接矩陣的循環(huán)次數(shù)也表現(xiàn)出無(wú)規(guī)律性。但隨著矩陣維度的增大，并行計(jì)算中單次循環(huán)平均耗時(shí)也越來(lái)越多。運(yùn)算效率不僅與維度相關(guān)，還與循環(huán)次數(shù)相關(guān)。如果兩個(gè)要素集中要素間存在疊置關(guān)系，則對(duì)應(yīng)鄰接矩陣中的權(quán)重為1，矩陣中權(quán)重為1的矩陣元素的數(shù)目決定著矩陣的復(fù)雜度以及最終的運(yùn)算效率。直到所有的關(guān)系要素都合并為1∶1，得到最終的空間聚類(lèi)簇。

表3 不同維度下GPU共享存儲(chǔ)器運(yùn)算結(jié)果Table 3 Calculation result of GPU shared memory under the different dimensional

3.3 Warp占有率對(duì)GPU運(yùn)算效率的影響

通過(guò)實(shí)驗(yàn)對(duì)經(jīng)過(guò)優(yōu)化的并行二分圖聚類(lèi)算法在設(shè)計(jì)中的各種參數(shù)對(duì)于系統(tǒng)性能的影響進(jìn)行分析。圖3表示的是每個(gè)線程塊中不同線程數(shù)量對(duì)warp占有率的影響，其中三角形標(biāo)記處是設(shè)計(jì)的線程模塊的分配大小，每個(gè)線程塊中有256個(gè)線程，此時(shí)warp占有率最高。圖4表示的是不同寄存器數(shù)量對(duì)warp占有率的影響，其中三角形標(biāo)記處是每個(gè)線程分配的寄存器個(gè)數(shù)，每個(gè)線程中擁有的寄存器數(shù)量為8，此時(shí)warp占有率最高。在每個(gè)線程的寄存器數(shù)量多于32個(gè)時(shí)，每個(gè)SM中最多有8 129個(gè)寄存器文件，此時(shí)warp占有率為0。圖5表示的是不同的共享內(nèi)存對(duì)warp占有率的影響，其中三角形標(biāo)記處是每個(gè)塊分配的共享存儲(chǔ)器大小，每個(gè)線程塊中擁有的共享內(nèi)存大小為1 024bytes，此時(shí)warp占有率最高。當(dāng)共享內(nèi)存大小大于16KB時(shí)，由于每個(gè)SM中最多有16KB共享內(nèi)存，此時(shí)warp占有率將降為0。本文中線程的劃分正好滿足此類(lèi)條件，warp占有率最佳。

圖3 線程數(shù)對(duì)warp占有率的影響Fig.3 The affection of threads to warp occupancy

圖4 寄存器對(duì)warp占有率的影響Fig.4 The affection of registers to warp occupancy

圖5 共享內(nèi)存對(duì)warp占有率的影響Fig.5 The affection of shared memory to warp occupancy

4 結(jié)論

空間聚類(lèi)算法是一個(gè)計(jì)算密集型算法，對(duì)計(jì)算資源有著巨大的需求，對(duì)于有潛在并行的算法，GPU的并行計(jì)算可以顯著提高聚類(lèi)的計(jì)算效率。根據(jù)GPU硬件特征和研究對(duì)象的不同劃定GPU線程的大小，使運(yùn)算效率最優(yōu)化。特別是海量空間數(shù)據(jù)聚類(lèi)，GPU并行計(jì)算將會(huì)有明顯的優(yōu)勢(shì)。本文將GPU并行計(jì)算運(yùn)用到二部圖聯(lián)合聚類(lèi)算法中，實(shí)驗(yàn)結(jié)果表明，基于GPU的并行計(jì)算將會(huì)給空間聯(lián)合聚類(lèi)算法的效率帶來(lái)顯著的提升。此外，空間索引也是提高數(shù)據(jù)處理速度的一種有效的手段，如何將空間數(shù)據(jù)索引與GPU并行計(jì)算結(jié)合，將是下一步研究的方向。

［1］ 席景科，譚海樵.空間聚類(lèi)分析及評(píng)價(jià)方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009（7）：1712－1715.

［2］ 張軍偉，王念濱，黃少濱，等.二分K均值聚類(lèi)算法優(yōu)化及并行化研究［J］.計(jì)算機(jī)工程，2011（17）：23－25.

［3］ ZHA H，HE X，DING C，et al.，Bipartite graph partitioning and data clustering［A］.Proceedings of the Tenth International Conference on Information and Knowledge Management［C］.2001.25－32.

［4］ CZECH W.Invariants of distance K－graphs for graph embedding［J］.Pattern Recognition Letters，2012，33（15）：1968－1979.

［5］ FERN X Z，BRODLEY C E.Solving cluster ensemble problems by bipartite graph partitioning［A］.Proceedings of the Twenty－First International Conference on Machine Learning［C］.2004.36.

［6］ REGE M，DONG M，F(xiàn)OTOUHI F.Bipartite isoperimetric graph partitioning for data co－clustering［J］.Data Mine Knowledge Discovery，2008，16（3）：276－312.

［7］ BRINKHOFF T，KRIEGEL H P，SCHNEIDER R，et al.Multistep processing of spatial joins［J］.ACM，1994，23（2）：197－208.

［8］ ZHANG J，YOU S，GRUENWALD L.High－Performance Spatial Join Processing on GPUs with Applications to Large－Scale Taxi Trip Data［R］.2012.

［9］ BRINKHOFF T，KRIEGEL H P，SEEGER B.Parallel processing of spatial joins using R－trees，data engineering［A］.Proceedings of the Twelfth International Conference，IEEE［C］.1996.258－265.

［10］ SHEKHAR S，LU C T，CHAWLA S，et al.Efficient join－index－based spatial－join processing：A clustering approach［J］.IEEE Transactions on Knowledge and Data Engineering，2002，14（6）：1400－1421.

［11］ OWENS J D，HOUSTON M，LUEBKE D，et al.GPU computing［A］.Proceedings of the IEEE［C］.2008，96（5）：879－899.

［12］ 肖漢，周清雷，張祖勛.基于多GPU的Harris角點(diǎn)檢測(cè)并行算法［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2012（7）：876－881.

［13］ FARIVAR R，REBOLLEDO D，CHAN E，et al.A parallel implementation of K－Means clustering on GPUs［A］.Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications（PDPTA）［C］.Las Vegas，Nevada，USA，F(xiàn)，2008.340－345.

［14］ HUH Y，YU K，HEO J.Detecting conjugate－point pairs for map alignment between two polygon datasets［J］.Computers，Environment and Urban Systems，2011，35（3）：250－262.

［15］ 李成名，陳軍.空間關(guān)系描述的9－交模型［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，1997，22（3）：207－211.