基于GPU的最短路徑算法的研究和實(shí)現(xiàn).pdf

1、GPGPU（General Purpose Graph Processing Unit）并行計(jì)算是近幾年高性能計(jì)算領(lǐng)域的一個(gè)研究熱點(diǎn)，主要是利用原有的圖形處理器的強(qiáng)大并行計(jì)算性能，實(shí)現(xiàn)高性能低成本的并行通用計(jì)算，高效地完成有海量數(shù)據(jù)的科學(xué)實(shí)驗(yàn)計(jì)算或企業(yè)數(shù)據(jù)分析。
　　 最短路徑問題是圖論中的一個(gè)經(jīng)典抽象問題，已經(jīng)廣泛應(yīng)用于城市規(guī)劃與設(shè)計(jì)、圖形學(xué)圖像分割、數(shù)字導(dǎo)航系統(tǒng)等領(lǐng)域，具有很高的理論研究和實(shí)際應(yīng)用價(jià)值。而Floyd-Wars

2、hall算法是最短路徑問題中求解APSP(All-PairShortestPaths)問題的經(jīng)典算法，能夠高效地計(jì)算出圖中所有節(jié)點(diǎn)間的最短路徑。Floyd算法可為實(shí)際的物流企業(yè)配送中心選址過程中提供重要的參考依據(jù)。然而Floyd算法的時(shí)間復(fù)雜度為O(n3)，在實(shí)際地圖中，隨著節(jié)點(diǎn)數(shù)的增加，計(jì)算時(shí)間呈指數(shù)級(jí)增長。因此，將此算法并行化則能明顯的加快計(jì)算速度，具有較高的科研和實(shí)際意義。
　　 在此情況下，本文采用GPGPU并行加速的方

3、式實(shí)現(xiàn)Floyd算法，可以快速地完成大規(guī)模地圖中最短路徑的尋找，為物流配送中心選址過程提供計(jì)算地理重心位置的依據(jù)。本文主要完成了如下工作:
　　 1、設(shè)計(jì)了基于GPU的Floyd并行策略，在TeslaM2050型號(hào)的GPU下完成CUDA程序的開發(fā)，并在同一平臺(tái)上和原有的Floyd串行程序比較，得到了平均百倍以上的加速比;
　　 2、研究了Venkataraman的矩陣分塊計(jì)算思想，提出并驗(yàn)證此算法在GPU上分塊并行的可行