臺灣博碩士論文加值系統

近幾年來，圖形處理器（Graph Processing Unit），簡稱GPU，已經發展成一個超多核心而且可程式化的架構。而CUDA平行處理平台的到來，可以簡化開發人員於GPU上的程式開發流程，使得平行處理的工作進行，變得相當地方便簡單。本篇論文的研究目的，是在CUDA平行處理架構上，使用GPU來實作、提升螞蟻族群演算法的執行效能，基於此目的，本論文提出了一個新的平行方法，稱為轉換條件法。實驗結果的部分，是使用旅行銷售人員（Traveling Salesman Problem，TSP）問題來當成實際的測試實例。最後的實驗數據，在效能方面，本論文所提出的轉換條件法，與先前文獻所提出的平行方法做比較的結果，最高可達到3.14倍的速度提升；而轉換條件法，再經由本論文所提出的程式架構調整方式與最佳化之後，甚至可以達到5.18倍的速度提升。接著，實驗結果也針對解的品質（Quality）做比較探討，證明論文中所提出的平行方法，並不會因為取得效能方面的提升，而犧牲掉解的品質。

Graph Processing Units (GPUs) have recently evolved into a super multi-core and a fully programmable architecture. In the CUDA programming model, the programmers can simply implement parallelism ideas of a task on GPUs. The purpose of this paper is to accelerate Ant Colony Optimization (ACO) for Traveling Salesman Problems (TSP) with GPUs. In this paper, we propose a new parallel method, which is called the Transition Condition Method. Experimental results are extensively compared and evaluated on the performance side and the solution quality side. The TSP problems are used as a standard benchmark for our experiments. In terms of experimental results, our new parallel method achieves the maximal speed-up factor of 3.14 than the previous parallel method. Next, some tuning techniques of the program architecture and optimization mechanisms we proposed are applied to this new method. It can achieve the speed-up factor of 5.18 furthermore. On the other hand, the quality of solutions is similar to the original sequential ACO algorithm. It proves that the quality of solutions does not be sacrificed in the cause of speed-up.

目錄
中文摘要 I
英文摘要 II
致謝 III
目錄 IV
圖目錄 V
表目錄 VI
第一章　緒論 1
第一節　研究背景、動機與目的 1
第二節　論文章節安排 2
第二章　相關資訊 3
第一節　螞蟻族群演算法與TSP問題 3
第二節　CUDA簡介 6
第三節　文獻探討 10
2.3.1節　〖Thread〗_Ant平行策略 11
2.3.2節　Block_Ant平行策略 11
2.3.3節　轉換機率法與平行輪盤法選擇機制 11
第三章　研究方法 17
第一節　新的平行方法－轉換條件法 17
第二節　相關資料結構與記憶體管理 20
第三節　可規劃式Thread個數之實作方式 21
第四節　一個調整的技巧針對記憶體管理 29
第五節　CUDA最佳化技術－Data Prefetching 30
3.5.1節　Data Prefetching之基本概念 30
3.5.2節　Data Prefetching之應用 31
第四章　實驗結果 35
第一節　解的品質之探討 36
第二節　效能比較 37
第五章　總結與未來展望 43
參考文獻 44

圖目錄
圖1. 螞蟻族群演算法 4
圖2. ConstructAntSolutions步驟的演算法 4
圖3. CUDA程式的執行流程 7
圖4. CUDA的多階層式記憶體模型 9
圖5. 轉換機率法的流程圖 13
圖6. 原始的輪盤法選擇機制，其演算法 14
圖7. 轉換機率法的流程圖，使用平行輪盤法選擇機制 16
圖8. 轉換條件法的流程圖 19
圖9. 第一種可規劃式Thread個數之實作方式 23
圖10. 第二種可規劃式Thread個數之實作方式：步驟.1 26
圖11. 第二種可規劃式Thread個數之實作方式：步驟.2 27
圖12. 判斷的運作：Reg.Product.of.Previous > Product.of.Previous [ThreadID] 28
圖13. 一個調整的技巧針對記憶體管理 29
圖14. Data Prefetching最佳化技術的說明實例 31
圖15. Data Prefetching最佳化技術應用於轉換條件法，變數宣告 32
圖16. Data Prefetching最佳化技術應用於轉換條件法，其流程圖 33
圖17. 解的品質比較圖 36
圖18. 執行時間比較圖，Thread個數為64個 37
圖19. 執行時間比較圖，Thread個數為128個 38
圖20. 執行時間比較圖，Thread個數為256個 38

表目錄
表1. CPU跟GPU的詳細硬體規格 35
表2. TSP問題的測試實例，包含城市數目和旅行路徑的最佳長度 35
表3. 四個版本的詳細執行時間，單位為ms，把TPM當成比較的基準 39
表4. Data Prefetching技術之應用 42

[1] Dorigo,M.,et al., “Ant Colony Optimization ”, IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE, PP. 28-39, NOVEMBER 2006.
[2] Dorigo,M., “A. Colorni, V.Maniezzo, Positive feedback as a search strategy ”, Tech. Rep. 91-016, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy, 1991.
[3] Nvidia,C., “ABOUT GPU COMPUTING [Online]”, http://www.nvidia.com/object/what-is-gpu-computing.html.
[4] Nvidia,C., “DEVELOPING WITH CUDA [Online] ”, http://www.nvidia.com/object/cuda-parallel-computing-platform.html.
[5] Lawler,E., et al., “The Traveling Salesman Problem ”, Wiley, New York, 1987.
[6] Dorigo,M., et al., “Ant Colony Optimization ”, A Bradford Book, The MIT Press, Cambridge, Massachusetts, London, England, 2004.
[7] Nvidia,C., “CUDA C Programming Guide ”, http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf.
[8] Cecilia,J.M., et al., “Enhancing Data Parallelism for Ant Colony Optimization on GPUs ”, Journal of Parallel and Distrib. Computing, 2012.
[9] Delevacq,A., et al., “Paralle Ant Colony Optimization on Graphics Processing Units ”, Journal of Parallel and Distrib. Computing, 2012.
[10] Patterson,D., et al., “Programming Massively Parallel Processors ”, A Hands-on Approach, Morgan Kaufmann Publishers is an imprint of Elsevier, USA, 2012.
[11] Weiss,R.M., “GPU-Accelerated Ant Colony Optimization ”, GPU Computing Gems, Chapter 22, PP. 325-340, 2011.
[12] Bai,H., et al., “MAX-MIN Ant System on GPU with CUDA ”, IEEE Fourth International Conference on Innovative Computing, Information and Control, PP. 801-804, 2009.
[13] Nvidia,C., “CUDA C BEST PRACTICES GUIDE ”, http://docs.nvidia.com/cuda/pdf/CUDA_C_Best_Practices_Guide.pdf.
[14] TSPLIB WebPage August 2008,
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
[15] Harris,M., “Optimization parallel reduction in CUDA”, Nvidia Developer Technology, 2007.