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

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

關鍵詞:鄰接矩陣;并行算法;存儲沖突

中圖分類號:TP301文獻標識碼: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

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

1 并行無存儲沖突算法

使用并行計算機解決一個應用問題時，就特別需要一個抽象的并行計算機結構作為研究高效的結構依賴性算法的基礎，以保證并行算法適應于廣泛的并行計算機結構，并能夠依照抽象的結構分析并行算法的效率，以及指導與并行機結構相匹配的并行算法的設計。……