臺灣博碩士論文加值系統

圖形處理器由數百至數千個運算單元所組成，有著大量執行緒的高產出運算能力。隨著多核心時代的來臨，圖形處理器的運算能力逐漸在高效能運算中嶄露頭角。由於圖形處理器具有非常嚴格而規律的運算特性，如何針對其特性發展有效的演算法以達成效能提升，便是將圖形處理器運算能力有效應用於一般問題的關鍵。在這篇論文中，我們提出了利用NVIDIA圖形處理器對Mikami繞線演算法進行平行加速的想法。為能有效找到線段交點位置並判斷交點型態，我們提出32位元的繞線格點編碼，並針對圖形處理器的特性提出執行緒層級與warp層級的直線探索技巧以分別生成垂直和水平的直線。為使效能更進一步提升，我們針對測試資料進行分析並且透過商業軟體分析程式效能，最後針對演算法提出效能改善方法。從實驗數據中可以證實，和傳統中央處理器版本的Mikami繞線演算法比較起來，透過圖形處理器的運算能力確實可使得繞線演算法在執行時間上達到有效的加速。

Graphic processing unit (GPU), which contains hundreds of processing cores, is becoming a popular device for high performance computation in multi-core era. With strictly computation regularity characteristic, specific algorithms are key challenges for performance speed-up. In this thesis, we propose a parallel CUDA-Mikami routing algorithm on NVIDIA's GPU. A 32-bit routing grid encoding is proposed to simplify wire intersection identification and wire direction recognition. Furthermore, thread-level and warp-level line probing techniques are proposed for vertical and horizontal routings, respectively. To further improve the quality of CUDA-Mikami router, performance evaluation and improvements are also conducted. The experimental results indicate that the run-time efficiency is promising as compared to traditional CPU-version algorithms.

LIST OF FIGURES VI
LIST OF TABLES VII
Chapter 1 Introduction 1
Chapter 2 Background 3
2.1 Conventional Routing Algorithm 3
2.2 Graphic Processing Unit 4
2.2.1 CUDA on Fermi and Kepler Architecture 4
2.2.2 Memory Coalesced Issue 6
Chapter 3 CUDA-Mikami Router 7
3.1 Proposed Routing Flow 7
3.2 Routing Grid Encoding 8
3.3 Line Probing 9
3.3.1 Thread-level Line Probing 9
3.3.2 Warp-level Line Probing 10
3.4 Initial Experimental Result 12
3.5 Race Condition Issue 13
Chapter 4 Performance Improvement 15
4.1 Performance Evaluation 15
4.1.1 Performance Profiling 15
4.1.2 Benchmark Statistics 16
4.1.3 Drawback Evaluation of Current Algorithm 17
4.2 New Line Probing Schemes 18
4.2.1 Boundary Scheme 18
4.2.2 Improved thread-level Line Probing 19
4.2.3 Improved Warp-level Line Probing 20
4.3 Improved Experimental Result 21
Chapter 5 Conclusion 23
Reference 24

[1]. Prithviraj Banerjee, “Parallel Algorithms for VLSI Computer-Aided Design, 1st edition,” Prentice-Hall, 1994

[2]. Lee, C. Y. “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers, EC-10(2): 346365, 1961.

[3]. K. Mikami, K. Tabuchi, “A computer program for optimal routing of printed circuit connectors,” Proceedings of IFIP, H47:1475-1478, 1968.

[4]. “NVIDIA CUDA Programming Guide 4.0/5.0,” NVIDIA

[5]. “NVIDIA CUDA Best Practices Guide 4.0/5.0,” NVIDIA

[6]. Fermi architecture, http://www.nvidia.com/object/fermi architecture.html

[7]. Yen-Hung Lin, Yun-Jian Lo, Hian-Syun Tong, Wen-Hao Liu, Yih-Lang Li, “Topology-Aware Buffer Insertion and GPU-Based Massively Parallel Rerouting for ECO Timing Optimization,” ASP-DAC 2012: 437-442.

[8]. H. Wong, M.-M. Papadopoulou, M. Sadooghi-Alvandi, and A. Moshovos. Demystifying gpu microarchitecture through microbenchmarking. In ISPASS'10, pages 235--246, 2010.