近年來，隨著智慧型手機興起，隨時可以上網的用戶越來越多，雲端服務所需處理的請求數也越來越龐大，同時大家皆希望短時間內能獲得回應。傳統上伺服端皆使用中央處理單元(CPU)來做運算，而CPU的發展也日新月異，核心數與執行緒個數逐漸增加，使平行運算速度不斷提升。在使用CPU平行運算技術中，以OpenMP最為常見。最近從顯示卡發展起來的通用圖形處理單元(GPU)也日趨成熟，其中以統一硬體運算架構(CUDA)最為熱門，其運算能力高且單核成本低，已成功應用在許多平行運算領域。本研究主要是利用近年這些CPU及GPU平行化技術來加快分群地圖上一對一最短路徑的搜索。為充分運用CPU以及GPU的硬體資源，在計算最短路徑以及距離的部分，分成起終點跨群及群內兩類型。由於跨群路徑計算時間較長，因此在跨群配對組合部分，使用CUDA平行技術來求最短距離，以減少跨群計算時間。在群內路徑計算時，則直接採用一對一Dijkstra演算法，將最短路徑查詢部分做多任務平行化的處理，以增加單位時間任務處理數。
實驗以台灣路網地圖為主，節點數275,195，邊數381,172，於進行METIS方法之分群後進行評估。在給定Intel Xeon E5620雙CPU及NVidia Tesla C2050雙GPU硬體環境下，本文方法就單獨跨群配對求最短路徑部分，若只計算最短距離時，相較於CPU單緒版能提升7.7倍效能；若包含計算最短距離與最短路徑時，相較於CPU單緒版，能提升5倍效能。其中，平均一次計算最短距離回應時間為0.08 ms；若包含計算最短距離與最短路徑，回應時間為0.13 ms。就全體包含跨群及群內求最短路徑部份，若只有計算最短距離時，一秒內能服務25K次請求；若包含計算最短距離與最短路徑時，一秒內能服務24K次請求。最後為供比較，本文也測試地圖不分群情況下，眾多Dijkstra演算法平行化在計算最短距離與最短路徑時之表現。其中，使用台灣路網地圖時，本文平行化方法相較於CPU單緒版，提升5.2倍效能；若使用隨機地圖時，則提升8倍效能。

In recent years as more mobile devices allow user to get online more easily, there is increasing demand for more powerful cloud services to serve more requests with shorter response time. In the past, the server often uses CPU to handle the requests. As the CPU equips with more cores and threads, use of the parallel computation can provide more speedup. Currently, OpenMP is the most common parallelization technique for utilizing CPU threads. In the meantime, general purpose GPUs evolving from the graphics display card also see rapid development as a mature parallel compute technology. Currently, CUDA is the most popular compute architecture to exploit the powerful and cheap GPU cores. This work will utilize these parallelization techniques to accelerate the computation of one-to-one shortest path in a clustered map. To make full use of the CPU and GPU hardware resources, the request is divided into the inter-cluster task and the intra-cluster task based on the clusters of the start and end locations. As the inter-cluster task takes long compute time, GPU using CUDA is introduced to accelerate the computation. For intra-cluster tasks, each task is simply served by a CPU thread running the Dijkstra algorithm with a goal to maximize the number of tasks serviced per second.
Our experiment is performed on a real Taiwan roadmap with 275,195 nodes and 381,172 edges where clusters are formed by the METIS clustering method. Given a platform with double CPUs of Intel Xeon E5620 and double GPUs of NVidia Tesla C2050, we measure speedup relative to a single thread counterpart. For only inter-cluster tasks, we obtain a speedup of 7.7x or 0.08ms when computing only the shortest distance. When the shortest path is also computed, we obtain a speedup of 5.2x or 0.13ms. For the whole spectrum of tasks including inter-cluster and intra-cluster tasks, we can service 25,756 tasks in one second when computing only the shortest distance. When the shortest path is also computed, we can service 24,128 tasks in one second. For comparison with maps without clusters, several parallel Dijkstra algorithms are tested too. When the shortest path is also computed, our parallel algorithm can obtain a speedup of 5.2x on real Taiwan roadmap and a speedup of 8x on a map of random graph.

目錄
第一章 緒論	1
1.1 研究背景	1
1.2 研究動機與目的	3
1.3 研究架構	4
第二章 文獻探討	5
2.1 Dijkstra演算法	5
2.2 CUDA	5
2.3 Dijkstra平行演算法-使用GPU	7
2.4 OpenMP	8
2.5 MPI	9
2.6 Dijkstra平行演算法-使用CPU	9
2.7 METIS	10
2.8 地圖分群求最短距離與路徑	10
第三章 方法介紹	13
3.1 分群地圖一對一求解之摘要	13
3.2 伺服器模型	16
3.3 群間窮舉配對求最短平行化	19
3.4 Dijkstra演算法平行化	26
第四章 實驗結果	32
4.1 實驗環境	32
4.2 評估方式	34
4.3 群間窮舉配對求最短平行化	35
4.3.1 CPU單緒 vs 單GPU	36
4.3.1.1 參數調整：使用不同GPU+CPU組合求最短距離之比較	36
4.3.1.2 只有最短距離	37
4.3.1.3 最短距離+重建路徑	38
4.3.2 單GPU vs 雙GPU	39
4.3.2.1 只有最短距離	39
4.3.2.2 最短距離+重建路徑	40
4.4 群內Dijkstra演算法平行化比較	41
4.4.1 參數調整：區塊內執行緒個數	41
4.4.2 參數調整：使用任務串流與否	41
4.4.3 CPU單緒版與結合GPU版比較	43
4.5 群間+群內最佳平行化作法	44
4.5.1 只有最短距離	45
4.5.2 最短距離+重建路徑	46
4.6 地圖不分群一對多Dijkstra平行演算法之比較	46
4.7 CUDA使用率	49
4.8 討論	49
4.8.1 只有最短距離	50
4.8.2 最短距離+重建路徑	51
第五章 結論與未來發展	52
參考文獻	55

圖目錄
圖2 1 Dijkstra演算法[13]	5
圖2 2 CPU和GPU架構[17]	6
圖2 3 CUDA架構[17]	7
圖3 1採用Metis分群，群間無節點交集之分群結果[1]	13
圖3 2 4種任務分類作法[1]	15
圖3 3情況二─起終點不同群且至少一方非邊界點	16
圖3 4伺服器運作流程圖	17
圖3 5地圖搜索平行演算法	19
圖3 6群間窮舉配對求最短平行化流程圖	20
圖3 7 GPU區塊內計算各配對組合最短距離流程圖(kernel_AllPairShortest)	21
圖3 8 CPU彙總各區塊結果求最小值	22
圖3 9群間窮舉配對求最短距離及路徑演算法(適用圖3-2情況二)	24
圖3 10 GPU區塊內計算各配對組合最短距離值演算法(kernel_ AllPairShortest)	25
圖3 11 Dijkstra演算法平行化流程圖	26
圖3 12群內Dijkstra演算法平行化使用任務串流兩種方式	28
圖3 13 Dijkstra平行化演算法	30
圖4 1 METS 分群及地標示意圖[1]	33
圖4 2 CPU單緒版與單GPU版計算最短距離與最短路徑之回應時間	38
圖4 3群內Dijkstra演算法平行化使用單任務串流與雙任務串流運算時間	42

表目錄
表4 1測試平台規格	31
表4 2原始及分群地圖資料集	32
表4 3隨機地圖資料集	32
表4 4 10000次亂數起終點之任務類型比例	34
表4 5 GPU+CPU組合求最短距離之回應時間	35
表4 6群間窮舉配對求最短距離(單GPU)之回應時間	36
表4 7群間窮舉配對求最短距離(單GPU)之單位時間任務數	36
表4 8群間窮舉配對求最短距離(單GPU)+重建最短路徑(CPU)之回應時間	37
表4 9群間窮舉配對求最短距離(單GPU)+重建最短路徑(CPU)之單位時間任務數	37
表4 10群間窮舉配對求最短距離(雙GPU)之單位時間任務數	39
表4 11群間窮舉配對求最短距離(雙GPU)+重建最短路徑(CPU)之單位時間任務數	40
表4 12群內Dijkstra演算法批次執行800個任務所花時間	41
表4 13群內Dijkstra演算法使用單任務串流與雙任務串流所花時間	41
表4 14群內Dijkstra演算法平行化求最短距離(GPU)之回應時間	43
表4 15群內Dijkstra演算法平行化求最短距離(GPU)之單位時間任務數	43
表4 16群內Dijkstra演算法平行化求最短距離(GPU)+重建最短路徑(CPU)之回應時間	43
表4 17群內Dijkstra演算法平行化求最短距離(GPU)+重建最短路徑(CPU)之單位時間任務數	44
表4 18只有最短距離在一秒內GPU與CPU執行緒組合之最大任務量	45
表4 19最短距離+重建路徑在一秒內GPU與CPU執行緒組合之最大任務量	46
表4 20 Dijkstra演算法平均一次一對多之單位時間任務數(一秒內)	47
表4 21實驗摘要	49

[1]	鄭宇辰，民98，給定分群下加快最短路徑計算之時空成本考量，淡江大學資訊管理學系碩士班碩士論文。
[2]	Andreas Crauser, K. M., Ulrich Meyer, and Peter Sanders "A parallelization of dijkstra’s shortest path algorithm.," in: Computer Science, M.F.o.C.S. (MFCS) (ed.), In Lubos Brim, Jozef Gruska, and Jir’ı Zlatuska, 1998, pp. 722–731.
[3]	Bleiweiss, A. “GPU accelerated pathfinding,” in: Proceedings of the 23rd ACM SigGraph/EuroGraphics Symposium on Graphics Hardware, EuroGraphics Association, Sarajevo, Bosnia and Herzegovina, 2008, pp. 65-74.
[4]	Buluc, A., Gilbert, J. R., and Budak, C. “Solving path problems on the GPU,” Parallel Computing (36:5–6) 2010, pp. 241-253.
[5]	Douglas Gregor , A. L. "The Parallel BGL: A Generic Library for Distributed Graph Computations," in: Open Systems Laboratory, Indiana University, In Parallel Object-Oriented Scientific Computing, 2005.
[6]	E. W. Dijkstra, “A note on two problems in connecion with graphs,” Numerische Mathematik, 1, 1959, pp. 269-271.
[7]	Fort, M., and Sellar, J. A. “GPU-based computation of distance functions on road networks with applications,” in: Proceedings of the 2009 ACM Symposium on Applied Computing, ACM, Honolulu, Hawaii, 2009, pp. 1320-1324.
[8]	Gabow, H. N. “Scaling algorithms for network problems, ” J. Comput. Syst. Sci. (31:2) 1985, pp 148-168.
[9]	G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” Tech. Rep. No.95-035, University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, 1998.
[10]	Harish, P., and Narayanan, P. J. “Accelerating large graph algorithms on the GPU using CUDA,” in: Proceedings of the 14th International Conference on High Performance Computing, Springer-Verlag, Goa, India, 2007, pp. 197-208.
[11]	Jasika, N. "Dijkstra's shortest path algorithm serial and parallel execution performance analysis," in: MIPRO, 2012 Proceedings of the 35th International Convention, 2012, pp. 1811 - 1815
[12]	Katz, G. J., and Joseph T. Kider, J. “All-pairs shortest-paths for large graphs on the GPU,” in: Proceedings of the 23rd ACM SigGraph/EuroGraphics Symposium on Graphics Hardware, EuroGraphics Association, Sarajevo, Bosnia and Herzegovina, 2008, pp. 47-55.
[13]	Kelley, K. "Parallel Single-Source Shortest Paths," MIT Computer Science and Artificial Intelligence Laboratory, 2010. 
[14]	Martin, P., Torres, R., and Gavilanes, A. “CUDA solutions for the SSSP problem,” in: Computational Science – ICCS 2009, G. Allen, J. Nabrzyski, E. Seidel, G. Albada, J. Dongarra and P.A. Sloot (eds.), Springer Berlin Heidelberg, 2009, pp. 904-913.
[15]	Meyer, U., and Sanders, P. “Δ-stepping: a parallelizable shortest path algorithm,” Journal of Algorithms (49:1) 2003, pp. 114-152.
[16]	MPI, 1994 , http://www.mcs.anl.gov/research/projects/mpi/
[17]	NVIDIA, NVIDIA Programming Guide, 2012, http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html
[18]	NVIDIA Visual Profiler v4.2, 2012, https://developer.nvidia.com/nvidia-visual-profiler
[19]	OpenMP, 1997, http://openmp.org/wp/.
[20]	Parallel BGL, 2005 , http://osl.iu.edu/research/pbgl/.
[21]	R. W. Floyd: Algorithm 97: Shortest Path. Communications of the ACM 5 (6) (1962), pp.345.