[發(fā)明專利]一種基于CUDA實(shí)現(xiàn)聚類的方法及裝置

在審

• 申請?zhí)枺?/td>: 201410360455.4
• 申請日: 2014-07-25
• 公開（公告）號: CN104123372A
• 公開（公告）日: 2014-10-29
• 發(fā)明（設(shè)計）人: 沈鉑;張剛;邱學(xué)侃;胡金輝;王婭娟;張清
• 申請（專利權(quán)）人: 浪潮（北京）電子信息產(chǎn)業(yè)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安信方達(dá)知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 王丹;李丹

技術(shù)領(lǐng)域

本申請涉及數(shù)據(jù)處理技術(shù)，尤指一種基于計算統(tǒng)一設(shè)備架構(gòu)(CUDA)實(shí)現(xiàn)聚類的方法及裝置。

背景技術(shù)

聚類分析又稱群分析，它是研究(樣品或指標(biāo))分類問題的一種統(tǒng)計分析方法，同時也是數(shù)據(jù)挖掘的一個重要算法。聚類分析以相似性為基礎(chǔ)，在一個聚類中的模式之間比不在同一聚類中的模式之間具有更多的相似性。

K-means算法是聚類分析中的一種硬聚類算法，是典型的基于原型的目標(biāo)函數(shù)聚類方法，K-means算法以數(shù)據(jù)點(diǎn)到原型的某種距離作為優(yōu)化的目標(biāo)函數(shù)，利用函數(shù)求極值的方法得到迭代運(yùn)算的調(diào)整規(guī)則。K-means算法以歐式距離作為相似度測度，是求對應(yīng)某一初始聚類中心向量最優(yōu)分類，使得評價指標(biāo)最小；采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)。

計算統(tǒng)一設(shè)備架構(gòu)(Compute?Unified?Device?Architecture，簡稱CUDA)是英偉達(dá)(NVIDIA)公司推出的并行計算架構(gòu)，該架構(gòu)通過利用圖形處理器(GPU)的處理能力，能夠大幅提升計算性能。其中程序代碼通常采用C語言的超集CUDA?C編寫。該技術(shù)封裝了使用GPU的細(xì)節(jié)，使用類似C語言的方式為使用者提供較簡單利用GPU的編程體驗(yàn)。該技術(shù)可以利用GPU的眾核特性，大幅加速并行化的應(yīng)用。

目前，已經(jīng)出現(xiàn)一些使用K-means聚類方法對CUDA進(jìn)行優(yōu)化的方法，并取得了不錯的效果。這些方法大致是將中央處理器(CPU)的點(diǎn)數(shù)組經(jīng)過轉(zhuǎn)置處理后賦值給CUDA點(diǎn)數(shù)組，CPU類數(shù)組直接賦值給CUDA類數(shù)組，通過對K-means方法進(jìn)行修改，對矩陣維度為2的冪的矩陣，尤其常見的維度為32、64、128等矩陣，使用類似于矩陣乘法的形式(按照矩陣相乘的方式進(jìn)行矩陣運(yùn)算，只是將矩陣元素的乘操作改為求差的平方)進(jìn)行矩陣運(yùn)算，通過統(tǒng)計GPU矩陣運(yùn)算結(jié)果，當(dāng)GPU矩陣運(yùn)算結(jié)果中改變的點(diǎn)數(shù)大于或等于預(yù)先設(shè)置的閾值時，根據(jù)GPU矩陣運(yùn)算結(jié)果更新CUDA類數(shù)組，否則，完成聚類。但是，現(xiàn)有使用K-means聚類方法對CUDA進(jìn)行優(yōu)化的方法中，僅針對規(guī)則矩陣(指矩陣維度為2的冪的矩陣，尤其常見的維度為32、64、128等矩陣)進(jìn)行優(yōu)化處理，對于維度不規(guī)則的矩陣，無法利用CUDA進(jìn)行優(yōu)化處理，使K-means聚類方法在CUDA下實(shí)現(xiàn)高效運(yùn)行。

發(fā)明內(nèi)容

為了解決上述問題，本發(fā)明提供一種基于CUDA實(shí)現(xiàn)聚類的方法及裝置，能夠支持不規(guī)則矩陣的聚類，實(shí)現(xiàn)K-means聚類方法在CUDA下的高效運(yùn)行。

為了達(dá)到本發(fā)明的目的，本申請?zhí)峁┮环N基于CUDA實(shí)現(xiàn)聚類的方法包括：

將確定的計算統(tǒng)一設(shè)備架構(gòu)CUDA類數(shù)組和CUDA點(diǎn)數(shù)組劃分為一個或一個以上16乘16的大小的矩陣；對不足16乘16的矩陣，標(biāo)志位賦值為0，除標(biāo)志位以外的其他位賦值為1；

對各劃分的矩陣，按照類似于矩陣乘法的形式進(jìn)行矩陣運(yùn)算，對不足16乘16的矩陣，在結(jié)果累加時，乘上標(biāo)志位，以獲得圖形處理器GPU矩陣運(yùn)算結(jié)果；

統(tǒng)計GPU矩陣運(yùn)算結(jié)果，當(dāng)GPU矩陣運(yùn)算結(jié)果中改變的點(diǎn)數(shù)大于或等于預(yù)先設(shè)置的閾值時，根據(jù)GPU矩陣運(yùn)算結(jié)果更新CUDA類數(shù)組，直至聚類完成。

進(jìn)一步地，該方法之前還包括：

從輸入文件中獲取每行一組浮點(diǎn)數(shù)的二進(jìn)制或文本形式的信息，根據(jù)獲取的二進(jìn)制或文本形式的信息，建立中央處理器CPU內(nèi)存相應(yīng)的CPU點(diǎn)數(shù)組和CPU類數(shù)組；

根據(jù)CPU點(diǎn)數(shù)組和CPU類數(shù)組，確定CUDA點(diǎn)數(shù)組、CUDA類數(shù)組。

進(jìn)一步地，根據(jù)CPU內(nèi)存相應(yīng)的數(shù)組，確定的GPU端CUDA點(diǎn)數(shù)組、CUDA類數(shù)組具體包括：將CPU點(diǎn)數(shù)組轉(zhuǎn)置變化后賦值給CUDA點(diǎn)數(shù)組，將CPU類數(shù)組直接賦值給CUDA類數(shù)組。

進(jìn)一步地，統(tǒng)計GPU矩陣運(yùn)算結(jié)果通過聚類結(jié)果數(shù)組實(shí)現(xiàn)統(tǒng)計。

進(jìn)一步地，該方法之前還包括：預(yù)先設(shè)置元素個數(shù)與CUDA點(diǎn)數(shù)組相同的聚類結(jié)果數(shù)組，并初始化聚類結(jié)果數(shù)組各元素為-1。

另一方面，本申請還提供一種基于CUDA實(shí)現(xiàn)聚類的裝置，包括：劃分單元、計算單元和統(tǒng)計處理單元；其中，

劃分單元，用于將確定的計算統(tǒng)一設(shè)備架構(gòu)CUDA類數(shù)組和CUDA點(diǎn)數(shù)組劃分為一個或一個以上16乘16的大小的矩陣；對不足16乘16的矩陣，標(biāo)志位賦值為0，除標(biāo)志位以外的其他位賦值為1；

計算單元，用于對各劃分的矩陣，按照類似于矩陣乘法的形式進(jìn)行矩陣運(yùn)算，對不足16乘16的矩陣，在結(jié)果累加時，乘上標(biāo)志位，以獲得圖形處理器GPU矩陣運(yùn)算結(jié)果；