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

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

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

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