運用平行化技術於一對一最短路徑問題之研究

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Thesis > Item 987654321/87744

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/87744

Title:	運用平行化技術於一對一最短路徑問題之研究
Other Titles:	Using parallelization techniques to solve the one-to-one shortest path problem
Authors:	何永欣;Ho, Yung-Hsin
Contributors:	淡江大學資訊管理學系碩士班魏世杰;Wei, Shih-Chieh
Keywords:	CUDA;Dijkstra演算法;GPU;OpenMP;平行化;Dijkstra Algorithm;parallelization
Date:	2013
Issue Date:	2013-04-13 11:39:04 (UTC+8)
Abstract:	近年來，隨著智慧型手機興起，隨時可以上網的用戶越來越多，雲端服務所需處理的請求數也越來越龐大，同時大家皆希望短時間內能獲得回應。傳統上伺服端皆使用中央處理單元(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.
Appears in Collections:	[Graduate Institute & Department of Information Management] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	330	View/Open

Loading...