跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.87) 您好!臺灣時間:2024/12/05 22:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:詹久儀
研究生(外文):Chiu-Yi Chan
論文名稱:以圖形處理器平行運算技術加速直線探索Mikami繞線演算法
論文名稱(外文):Accelerating Line Probing for Mikami Routing Algorithm Using Parallel Techniques on Graphic Processing Units
指導教授:劉一宇
指導教授(外文):Yi-Yu Liu
口試委員:陳勇志林政宏
口試委員(外文):Yung-Chih ChenCheng-Hung Lin
口試日期:2013-06-29
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:24
中文關鍵詞:圖形運算處理器繞線演算法
外文關鍵詞:CUDARouterGPUMikami
相關次數:
  • 被引用被引用:0
  • 點閱點閱:419
  • 評分評分:
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:0
圖形處理器由數百至數千個運算單元所組成,有著大量執行緒的高產出運算能力。隨著多核心時代的來臨,圖形處理器的運算能力逐漸在高效能運算中嶄露頭角。由於圖形處理器具有非常嚴格而規律的運算特性,如何針對其特性發展有效的演算法以達成效能提升,便是將圖形處理器運算能力有效應用於一般問題的關鍵。在這篇論文中,我們提出了利用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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊