跳到主要內容

臺灣博碩士論文加值系統

(44.213.60.33) 您好!臺灣時間:2024/07/17 04:07
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張書鑫
研究生(外文):Shu-Hsin Chang
論文名稱:考慮電路延遲與障礙物迴避之直角史坦那樹建構法
論文名稱(外文):Performance-Driven Obstacle-Avoiding Rectilinear Steiner Tree Construction
指導教授:李毅郎
指導教授(外文):Yih-Lang Li
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學與工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:49
中文關鍵詞:史坦那樹電路延遲障礙物迴避
外文關鍵詞:Steiner TreePerformance-DrivenObstacle-Avoiding
相關次數:
  • 被引用被引用:0
  • 點閱點閱:315
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
隨著製程的演進,線路所造成的延遲已經變為最主要影響電路延遲的一個因素。而且,在先進的積體電路設計中,對一些比較先進的設計進行繞線時,那些設計常常會包含許多障礙物,例如: 區塊所產生障礙物,或者一些已經繞好的線路。然而,避開障礙物的史坦那繞線研究卻很少考慮如何去減少電路延遲,大部分之前的研究都只針對如何來減少整體繞線的長度,因此,這些研究被稱為避開障礙物且最短繞線長度之直角史坦那樹 (OARSMT)。

這篇論文中,我們提出一個新穎且快速的演算法稱為關鍵樹幹為基礎之電路延遲最小化演算法(critical-trunk based delay minimization algorithm),在考慮障礙物的情況下同時解決電路延遲問題。我們的演算法可以分為5個主要的部分; (1) 建立避開障礙物的擴張圖(spanning graph),(2) 對遠離驅動源(driver)的接腳(pin)先進行繞線,(3) 再連接其他的接腳(pin),(4) 將歪斜的線轉化為水平或垂的線段,(5) 優化違反時序限制最大的路徑延遲(Worst Negative Slack)。

實驗結果顯示,對於OARSMT,我們提出的演算法平均改進違反時序限制最大路徑延遲和最大路徑延遲,分別是81.52 %以及28.42 %,而且,僅僅增加了9.15%的線長,且外,我們更比[10]平均快了32.06%。對於C-Tree[21],我們的演算法相對改進的違反時序限制最大的路徑延遲和總線長,分別是53.92%以及15.61%,我們提出的演算法更比[21]快了27.69倍。
With technology scaling, interconnect delay has dominated circuit delay. Mean-while, modern System on Chip (SOC) design contains many obstacles such as IP cores, macro blocks, and pre-routed nets within the routing region. Most previous works on obstacle-avoiding rectilinear Steiner tree construction only focus on mini-mizing total tree wire-length, and thus their works are called obstacle-avoiding recti-linear Steiner minimal tree (OARSMT).

In this thesis, we propose a novel and fast algorithm called critical-trunk based delay minimization algorithm to tackle timing issue regarding existing blockages. The proposed algorithm can be classified into 5 main steps: (1) construct an obsta-cle-avoiding spanning graph; (2) pre-route the sinks that are far away from the driver; (3) connect other sinks; (4) transform every slant edge into horizontal or vertical edges; (5) refine worst negative slack (WNS).

Experiments show that the proposed algorithm achieves the average reduction rates of WNS and maximum delay over OARSMT approach are 81.52 % and 28.42%. Besides, the proposed algorithm runs faster by 32.06% as compared to that in [10]. As compared to the C-Tree approach in [21], the reduction rates of WNS and wire length are 53.92% and 15.61%, respectively. The proposed algorithm achieves a 27.69X runtime speedup as compared to that in [21].
Abstract (Chinese) i
Abstract ii
Acknowledgement iii
Table of Contents iv
List of Figures vi
List of Tables ix
Chapter 1 Introduction 1
1.1 Preface 1
1.2 Obstacle-Avoiding Rectilinear Steiner Minimal Tree 1
1.2.1 Maze Routing 2
1.2.2 Spanning Graph Based Approaches 2
1.2.2.1 OASG Construction 4
1.2.2.2 Tree Construction 7
1.3 Performance-Driven Steiner Tree 7
1.3.1 A-Tree Algorithm 7
1.3.2 Prim and Dijkstra Algorithms 9
1.3.3 Radius Ratio Based Approach 10
1.4 Motivation 11
1.5 Contributions 12
1.6 Thesis Organization 13
Chapter 2 Problem Formulation and Preliminaries 14
2.1 Problem Formulation 14
2.2 Preliminaries 16
2.2.1 Elmore Delay Model 16
2.2.2 A* Search Algorithm 17
2.2.3 Region Tree (R-Tree) Algorithm 17
Chapter 3 PDOARST Algorithm 19
3.1 Steiner–Tree Delay Analysis 19
3.2 PDOARST Overflow 23
3.3 OASG Construction 26
3.4 SPT Construction 29
3.4.1 Multi-Source Single-Target Maze Routing 30
3.4.2 A* Search Schemes 31
3.5 Critical Trunk Growth 31
3.5.1 Critical Trunk Selection 32
3.5.2 Rip-Up of Non-Critical Trunk 32
3.6 Sub-Tree Re-Routing 33
3.6.1 Delay Penalty Factor 33
3.6.2 Re-Routing Order and A* Search 34
3.7 Transformation of Slant Edges into Rectilinear Edges 36
3.8 WNS Reduction 37
Chapter 4 Extension to OARSMT Problem 40
Chapter 5 Experimental Results 41
5.1 OARSMT Problem 41
5.2 PD-OARST Problem 42
Chapter 6 Conclusions 45
Chapter 7 Reference 46
[1] J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, and C.K. Wong, “Perform-ance-driven global routing for cell based ICs”, International Conference on Com-puter Design (ICCD-1991), pp. 14-16.
[2] J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, “Provably
good performance-driven global routing”, in IEEE Trans. on Computer-Aided De-sign of Integrated Circuits and Systems (TCAD-1992), vol. 11, no. 6, pp. 739-752.
[3] S. Rao, P. Sadayappan, F. Hwang, and P. Shor, “The rectilinear Steiner arbores-cence problem”, Algorithmica, vol. 7, no. 2-3, pp. 277--288, 1992.
[4] J. Cong, K. S. Leung, and D. Zhou, “Performance-driven interconnect design based on distributed RC delay model”, in Proceedings of ACM/IEEE Design Automation Conference (DAC-1993), pp.606-611.
[5] C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger, “Prim-Dijkstra tradeoffs for improved performance-driven routing tree design”, in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD-1995), vol.14, no. 7, pp. 890-89.
[6] K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins, “Near-optimal critical sink routing tree constructions”, in IEEE Trans. on Computer-Aided Design of In-tegrated Circuits and Systems (TCAD-1995), vol.14, no. pp. 1417-1436.
[7] H. Hou, J. Hu, and S. S. Sapatnekar, “Non-Hanan routing”, in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD-1999), vol. 18. no. 4, pp. 436-444.
[8] J. Hu and S. S. Sapatnekar, “Simultaneous buffer insertion and non-hanan optimi-zation for VLSI interconnect under a higher order AWE model”, in Proc. of In-ternational Symposium on Physical Design (ISPD-1999), pp. 133-138.
[9] Z. C. Shen, C. C. N. Chu, and Y.-M. Li, “Efficient Rectilinear Steiner Tree Con-struction with Rectilinear Blockings”, International Conference on Computer De-sign (ICCD-2005).
[10] C.-W. Lin, S.-Y. Chen, C.-F. Li, Y.-W. Chang, and C.-L. Yang, “Efficient
Obstacle-Avoiding Rectilinear Steiner Tree Construction”, in Proc. of Interna-tional Symposium on Physical Design (ISPD-2007).
[11] P.-C. Wu, J.-R. Gao, and T.-C. Wang, “A Fast and Stable Algorithm for
Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction”, in Proc. of Asia South Pacific Design Automation Conference (ASP-DAC-2007).
[12] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An O(nlogn) Algorithm for Obstacle-Avoiding Routing Tree Construction in Geometry Plane”, in Proc. of International Symposium on Physical Design (ISPD-2006).
[13] Y. Hu, T. Jing, X. Hong, Z. Feng, X. Hu, and G. Yan, “An-OARSMan: Obsta-cle-Avoiding Routing Tree Construction with Good Length Performance”, in Proc. of Asia South Pacific Design Automation Conference (ASP-DAC-2005).
[14] Y. Hu, Z. Feng, T. Jing, X. Hong, Y. Yang, G. Yu, X. Hu, and G. Yan,
“FORst: a 3-step heuristic for obstacle-avoiding rectilinear Steiner minimal tree
construction,” Journal of Information and Computational Science, pp. 107{116,
2004.
[15] H. Zhou, N. Shenoy, and W. Nicholls. “Efficient spanning tree construction without delaunay triangulation”, Information Processing Letter, 81(5), 2002.
[16] J. Long, H. Zhou, and S. O. Memik. “An O(nlogn) Edge-Based Algorithm for Obstacle-Avoiding Rectilinear Steiner Tree Construction”, in Proc. of Interna-tional Symposium on Physical Design (ISPD-2008).
[17] M. Berg, M. Kreveld, M. Overmars, and O. Schwarzkopf, “Computational
Geometry: Algorithms and Applications”, 2nd Edition, Springer-Verlag, 2000.
[18] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, “Introduction to Algorithms”, 2nd Edition, 2001.
[19] M. R. Garey and D. S. Johnson, “The rectilinear Steiner tree problem in NP-
complete", SIAM Journal on Applied Mathematics, vol. 32, pp. 826{834, 1977.
[20] C. Alpert, A. Kahng, C. Sze, and Q. Wang. “Timing-Driven Steiner Trees are (Practically) Free”, in Proc. of Design Automation Conference (DAC-2006).
[21] C. J. Alpert, et. al. “Buffered Steiner Trees for Difficult Instances”, in Proc. of International Symposium on Physical Design (ISPD-2001).
[22] R. F. Hentschke, J. Narasimharm, M. O. Johann and R. L. Resis. “Maze Routing Steiner Trees with Effective Critical Sink Optimization”, in Proc. of International Symposium on Physical Design (ISPD-2007).
[23] M. Pan, C. Chu and P. Patra “A Novel Performance-Driven Topology Design Algorithm”, in Proc. of Asia South Pacific Design Automation Conference (ASP-DAC-2007).
[24] M. Borah, R. M. Owens, and M. J. Irwin. “An edge-based heuristic for Steiner
Routing”. in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems (TCAD-1994), 13(12):1563–1568, Dec, 1994.
[25] J. Rubinstein, P. Pentield, and N. A. Horowitz, “Signal delay in RC tree net-works”, in Proc. of ACM/IEEE Design Automation Conference (DAC-1983), 2(3) pp. 202-211.
[26] A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching”, in Proc. of ACM's Special Interest Group on Management of Data (SIGMOD-1984)
[27] M. de Berg, J. Gudmundsson, M. Hammar and M. H. Overmars, “On R-trees
with Low Stabbing Number”, Proc. European Symposium on Algorithms, 2000.
[28] N. Beckmann, H.-P. Kriegel, R. Schneider and B. Seeger, “The R*-Tree: An
Efficient and Robust Access Method for Points and Rectangles”, in Proc. of ACM's Special Interest Group on Management of Data (SIGMOD-1990).
[29] S.-P. Lin and Y.-W. Chang. “A novel framework for multilevel routing consider-ing routability and performance”, in Proc. of International Conference on Com-puter Aided Design (ICCAD-2002), pp. 44–50, Nov. 2002.
[30] D. W. Hightower, “A solution to the line routing problem on the continous
plane", Proceedings of ACM Design Automation Workshop, pp. 1{24, 1969.
[31] C. Y. Lee, “An algorithm for connections and its application", IRE Transac-
tions on Electronic Computer, pp. 346{365, 1961.
[32] K. Mikami and K. Tabuchi, “A computer program for optimal routing of printed
circuit conductors", Proceedings of IFIP Congress, vol. 2, pp. 1475{1478, 1968.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top