并行無存儲沖突的鄰接矩陣算法

摘要:鄰接矩陣算法在科學(xué)計(jì)算與信息處理方面有著極為重要的應(yīng)用，是圖論的基礎(chǔ)研究之一。針對目前鄰接矩陣算法多是基于串行，或并行SIMD模型而無法解決存儲沖突的問題，提出一種基于SIMD-EREW共享存儲模型的并行鄰接矩陣算法。算法使用O(p)個并行處理單元，在O(n2/p)的時間內(nèi)完成對n個數(shù)據(jù)點(diǎn)鄰接矩陣的計(jì)算。將提出算法與現(xiàn)有算法進(jìn)行的性能對比分析表明:本算法明顯改進(jìn)了現(xiàn)有文獻(xiàn)的研究結(jié)果，是一種并行無存儲沖突的鄰接矩陣算法。

關(guān)鍵詞:鄰接矩陣;并行算法;存儲沖突

中圖分類號:TP301文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)25-7201-02

An Parallel Adjacent Matrix Algorithm without Memory Conflicts

LI Zhao-peng， CHENG Yun

(Hunan University of Humanities， Science and Technology， Loudi 417000， China)

Abstract: Adjacent matrix algorithm plays a very important role in scientific computing and information processing， which is one of the most extensively studied branch in data mining. Presently the adjacent matrix algorithms based on serial or SIMD which can not process memory conflicts among different processors. To overcome this shortcomings， a new parallel algorithm based on SIMD-EREW is proposed in this paper. The proposed algorithms can compute adjacent matrix of n objects with O(p) processors in O(n2/p) time. Performance comparisons show that it is an improved result over the past researches.

Key words: adjacent matrix; parallel algorithms; memory conflicts

鄰接矩陣技術(shù)在圖論、科學(xué)計(jì)算等領(lǐng)域有著極為廣泛的應(yīng)用[1，2，4]， 鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，設(shè)G=(V，E)是一個圖，其中V={v1，v2，…，vn}為頂點(diǎn)集，E為邊集。G的鄰接矩陣A是一個具有下列性質(zhì)的n階方陣，其中vi，vj∈V，a為邊vi，j的權(quán)值.在圖的運(yùn)算中許多算法通常采用鄰接矩陣作為存儲結(jié)構(gòu)來處理如:計(jì)算最短路徑的Dijkstra算法、Floyed算法，Prim算法等，這些算法中都涉及到邊的權(quán)值計(jì)算，對于一個n個頂點(diǎn)的完全圖其權(quán)值邊的計(jì)算復(fù)雜性將是O(n2)因此如何提高鄰接矩陣中邊的權(quán)值計(jì)算速度將是一個很有實(shí)際意義的工作。下面給出一種通過并行處理的方法達(dá)到既提高運(yùn)行速度又能在最弱的并行計(jì)算模型SIMD-EREW實(shí)現(xiàn)的鄰接矩陣算法。

1 并行無存儲沖突算法

使用并行計(jì)算機(jī)解決一個應(yīng)用問題時，就特別需要一個抽象的并行計(jì)算機(jī)結(jié)構(gòu)作為研究高效的結(jié)構(gòu)依賴性算法的基礎(chǔ)，以保證并行算法適應(yīng)于廣泛的并行計(jì)算機(jī)結(jié)構(gòu)，并能夠依照抽象的結(jié)構(gòu)分析并行算法的效率，以及指導(dǎo)與并行機(jī)結(jié)構(gòu)相匹配的并行算法的設(shè)計(jì)。并行計(jì)算模型就是為并行算法的設(shè)計(jì)、分析而研究出的并行計(jì)算機(jī)的抽象結(jié)構(gòu)。

1.1 計(jì)算模型

PRAM(Parallel Random Access Machine，隨機(jī)存取并行機(jī)器)模型，也稱為共享存儲的SIMD模型，是一種抽象的并行計(jì)算模型. PRAM模型可以分為: 不允許同時讀和同時寫的PRAM-EREW;允許同時讀但不允許同時寫PRAM-CREW;允許同時讀和同時寫的PRAM-CRCW。

PRAM-EREW是功能最弱的計(jì)算模型TM 表示某并行算法在并行計(jì)算模型 M 上的計(jì)算時間，則TEREW >= TCREW >= TCRCW且

TEREW = O(TCREW*logP) = O(TCRCW*logP) (1)

其中p 為處理器數(shù)目，上式的含義是，一個具有時間復(fù)雜度 TCREW 和 TCRCW 的算法，可以在 PRAM-EREW 模型上，花費(fèi) logP 倍的時間模擬實(shí)現(xiàn)。CRCW與EREW相比，PRAM-EREW的底層硬件相對來說比較簡單，并且因?yàn)樗鼰o需對相互沖突的存儲器讀寫操作進(jìn)行處理，因此運(yùn)行速度也比較快。

1.2 并行算法

令G=(V，E)是一個圖，V ={v1，v2，…，vn}是頂點(diǎn)集，E是邊集，各邊權(quán)值這里暫定義為相連兩點(diǎn)間歐幾里德距離即

(2)

其中i，j∈V，m為頂點(diǎn)的空間坐標(biāo)。這里假定每個頂點(diǎn)有m維坐標(biāo)即V1(x11， x12，…，x1m)， V2(x21， x22，…，x2m)，…， Vn(xn1， xn2，…，xnm)，則并行算法如下:

begin

forl = p to 1 step by – 1do

forall processors Pi where 1≤i≤l do

fork =[n/p](i-1+p-l) to[n/p](i+p-l)do

forj =[n/p](i-1)+1 to [n/p]×i do

begin

compute the Euclidean distance dkj where

write dkj to the shared memory

end

end

2 算法性能分析

假定每個PRAM處理器計(jì)算歐氏距離的時間為O(1)(實(shí)際為O(m)，文中假定m為常量)，如圖1所示.1) 若p|n，上述算法的三次循環(huán)總時間為p×n/p×n/p=n2/p，計(jì)算成本為p×n2/p=n2.由于不同處理器計(jì)算的dij互不相同，因此它們將不同的dij寫入共享存儲器的不同地址單元，即各處理器的寫入不會存在沖突.而在算法循環(huán)運(yùn)行的任何時刻，對不同的處理器Pi和Pj，如果i≠j，則處理器i所計(jì)算的距離d的下標(biāo)將不同于處理器j所計(jì)算距離的下標(biāo).這說明處理器i和處理器j在任何時刻所讀取的存儲單元互不相同，從而不同處理器間也不存在對同一地址單元的讀取沖突.因此算法可運(yùn)行于EREW模型. 2) 否則，即p不整除n，則除了處理器p和最后對l的循環(huán)和情形(i)稍有不同外，其它均維持不變，顯然此情形下算法的運(yùn)行時間和計(jì)算成本均不會變化.

a. when l=p b.when l=p-1 c.when l=1

圖1算法執(zhí)行的不同時刻各處理器處理的數(shù)據(jù)塊

綜上所述算法能在EREW-SIMD模型上以O(shè)(n2/p)的時間和O(n2)的成本完成.且與文獻(xiàn)[1，2]相比速度得到提高。

3 結(jié)論

受無存儲沖突并行歸并算法的啟示[3]，基于EREW-SIMD模型，提出了一種新的并行鄰接矩陣算法.算法使用p個處理機(jī)，1≤p≤n/logn，在O(n2/p)的時間完成n頂點(diǎn)的圖賦權(quán)鄰接矩陣計(jì)算，此算法可較大地減少鄰接矩陣的計(jì)算工作量為后述相關(guān)處理節(jié)約時間.當(dāng)然本算法只是處理了鄰接矩陣的一個部份即賦權(quán)值的計(jì)算，有關(guān)鄰接矩陣的內(nèi)容還很多如存儲方式等，這有待于進(jìn)一步的研究。

參考文獻(xiàn):

[1] Han J W， Kamber M. Data mining: concepts and techniques[M].Morgan Kaufmann Publishers，2000.

[2] 周水庚，胡運(yùn)發(fā).基于鄰接矩陣的全文索引模型[J].軟件學(xué)報(bào)，2002，13(10):1933-1942.

[3] Rasmussen E M， Willett P. Efficiency of hierarchic agglomerative clustering using the ICL[J].distributed array processor.Journal of Documentation，1989， 45:1-24.

[4] Lang X Y， Lu Z H， Chi X B. A parallel clustering algorithm of gene expression patterns[J]. Chinese Journal of Computers，2007，30(2):311-316.