并行廣度優(yōu)先搜索算法研究.pdf

1、隨著計算機(jī)科學(xué)的不斷發(fā)展，圖的搜索技術(shù)已經(jīng)滲透到語言學(xué)、邏輯學(xué)、物理、化學(xué)、電子、通信、數(shù)學(xué)等諸多學(xué)科領(lǐng)域，特別是網(wǎng)絡(luò)技術(shù)的快速發(fā)展和并行計算機(jī)的出現(xiàn)，并行處理進(jìn)入了前所未有的繁榮期，圖的遍歷也顯得越來越重要。廣度優(yōu)先搜索算法是圖論的一個基本問題，也是一個熱點(diǎn)問題。廣度優(yōu)先搜索算法的并行化已經(jīng)成為目前亟待解決的問題。
　　本文首先介紹了廣度優(yōu)先搜索并行算法的研究現(xiàn)狀。然后，在Cilk++運(yùn)行時系統(tǒng)上，實(shí)現(xiàn)了用“bag”的數(shù)據(jù)結(jié)構(gòu)代

2、替共享隊(duì)列的一種優(yōu)化方法，該算法是基于層同步思想的一個細(xì)粒度并行算法，能夠更容易的并行代碼。其次，在分布式系統(tǒng)上，實(shí)現(xiàn)了基于鄰接矩陣一維劃分的并行廣度優(yōu)先搜索算法。最后，在分析和研究現(xiàn)有的廣度優(yōu)先搜索并行算法的基礎(chǔ)上，結(jié)合現(xiàn)有的并行計算環(huán)境，提出了一種新的廣度優(yōu)先搜索并行算法。該算法是在分布式系統(tǒng)上提出來的，結(jié)合了層同步的思想和鄰接矩陣二維劃分的思想。通過大量實(shí)驗(yàn)證明，我們提出的新算法在時間復(fù)雜度上達(dá)到了更好的性能，在分布式系統(tǒng)上具有更