English  |  正體中文  |  简体中文  |  Items with full text/Total items : 51771/86989 (60%)
Visitors : 8369961      Online Users : 72
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/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:[資訊管理學系暨研究所] 學位論文

    Files in This Item:

    File SizeFormat

    All items in 機構典藏 are protected by copyright, with all rights reserved.

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - Feedback