跳到主要內容

臺灣博碩士論文加值系統

(54.225.48.56) 您好!臺灣時間:2022/01/19 22:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林世平
研究生(外文):Shih-Ping Lin
論文名稱:考慮可繞度和效能之多階層繞線器
論文名稱(外文):A Novel Framework for Multilevel Routing Considering Routability and Performance
指導教授:莊仁輝張耀文張耀文引用關係
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:50
中文關鍵詞:多階層繞線器效能
外文關鍵詞:MultilevelRoutingPerformance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:168
  • 評分評分:
  • 下載下載:15
  • 收藏至我的研究室書目清單書目收藏:0
在這碩士論文中,我們提出一個可以同時考慮可繞度以及效能的多階層(multilevel)繞線器的架構。此架構包含兩個主要步驟:粗糙化(coarsening)及反粗糙化(uncoarsening)。與之前多階層繞線器架構不同的地方是,我們將全域繞線(global routing)、細部繞線(detailed routing)以及資源評估(resource estimation)整合在多階層繞線器的架構的每一個階段(level),使得在粗糙化階段的資源評估更為正確,同時在反粗糙化階段也可以加速結果的改善。並且由於每一階段皆得到正確繞線資訊,讓我們的架構更具彈性,並且能去處理不同繞線的要求(例如減少雜訊,能量的消耗等)。實驗結果證明,我們的架構比其他方法具有較好的繞線完成度。例如在11個常用的標準電路中,我們的方法對所有電路皆達到了100%的繞線完成度,反之以前的方法,包括多階層繞線架構、三階段式繞線(three-level routing)以及階層式繞線(hierarchical routing)分別只完成了3, 0, 3個電路。另外我們的繞線器也可使用比較少的繞線層數來達成100%完成度。我們同時提出了依效能為導向的繞線器,也得到了不錯的成果。
We propose in this thesis a novel framework for multilevel routing
considering both routability and performance. The two-stage
multilevel framework consists of coarsening followed by
uncoarsening. Unlike the previous multilevel routing, we integrate
global routing, detailed routing, and resource estimation together
into each level of the framework, leading to more accurate routing
resource estimation during coarsening and thus facilitating the
solution refinement during uncoarsening. Further, the exact
routing information obtained at each level makes our framework
more flexible in dealing with various routing objectives (such as
crosstalk, power, etc). Experimental results show that our
approach obtains significantly better routing solutions than all
previous works. For example, for a set of 11 commonly used
benchmark circuits, our approach achieves 100\% routing completion
for all circuits while the previous multilevel routing, the
three-level routing, and the hierarchical routing can complete
routing for only 3, 0, 3 circuits, respectively. In particular,
the number of routing layers used by our router is even smaller.
We also have performed experiments on timing-driven routing. The
results are also very promising.
Chinese Abstract i
Abstract ii
Acknowledgements iii
List of Tables vi
List of Figures vii
Chapter 1. Introduction 1
1.1 Physical Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 Sequential Approaches . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Concurrent Approaches . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Hierarchical Approaches . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Multilevel Approaches . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Chapter 2. Preliminary 13
2.1 Routing Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Multilevel Routing Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Elmore Delay Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapter 3. Multilevel Routing Framework 19
3.1 Multilevel Routing for Routability . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Coarsening Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.2 Uncoarsening Stage . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Multilevel Routing for Performance . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Performance Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.2 Our Routing Approach for Performance . . . . . . . . . . . . . . . 24
Chapter 4. Experimental Results 29
Chapter 5. Conclusion 38
Bibliography 39
[1] C. Albrecht, \Global Routing by New Approximation Algorithms for Multi-
commodity Flow," Trans. on CAD, vol. 20, no. 5, pp. 622-632 (2001).
[2] C. J. Alpert, J.-H. Huang, and A. B. Kahng, \Multilevel circuit partitioning,"
IEEE Trans. Computer-Aided Design, vol. 17, no. 8, pp. 655{667, August
1998.
[3] K. D. Boese, A. B. Kahng, B. A. McCoy and G. Robins, \Near-optimal Critical
Sink Routing Tree Constructions," Trans. on CAD, vol. 14, no. 12 pp. 1417-
1436 (1995).
[4] K. D. Boese, A. B. Kahng and G. Robins, \High-performance routing trees
with identied critical sinks," Proc. DAC, pp.182-187 (1993).
[5] M. Burstein and R. Pelavin, \Hierarchical Wire Routing," TCAD, vol. CAD-2,
pages 223-234 1983.
[6] T. F. Chan, J. Cong, T. Kong, J. R. Shinnerl, \Multilevel optimization for
large-scale circuit placement," Proc. of IEEE/ACM Int. Conf. Computer-
Aided Design, pp. 171{176, 2000.
[7] Y.-W. Chang, K. Zhu and D. F. Wong, \Timing-driven routing for
symmetrical-array-based FPGAs," Trans. on Design Automation of Electronic
Systems, vol. 5, no. 3, pp. 433-450 (2000).
[8] Z. Chen and I. Koren, \Crosstalk Minimization in Three-Layer HVH Channel
Routing," Proc. IEEE International Symposium on Defect and Fault Tolerance
in VLSI Systems, pp. 38-42 (1997).
[9] T. Chan, J. Cong, T. Kong, and J. Shinnerl, \Multilevel optimization for
large-scale circuit placement," Proc. ICCAD, pp.171{176 (2000).
[10] J. Cong, J. Fang and Y. Zhang, \Multilevel Approach to Full-Chip Gridless
Routing," Proc. ICCAD, pp. 396-403 (2001).
[11] J. Cong, J. Fang and K. Khoo, \DUNE: A Multi-Layer Gridless Routing
System with Wire Planning," Proc. ISPD, pp.12-18 (2000).
[12] J. Cong, S. Lim, and C. Wu, \Performance driven multilevel and multiway
partitioning with retiming" Proc. DAC, pp.274{279 (2000)
[13] J. Cong, A. Kahng, and K. Leung, \EÆcient algorithms for the Minimum
Shortest Path Steiner Arborescence Problem with Applications to VLSI Phys-
ical Design," Trans. CAD, vol 17, pp. 24-39 (1998).
[14] J. Cong and P. H. Madden, \Performance driven global routing for standard
cell design" Proc. ISPD, pp.73-80 (1997)
[15] J. Cong, and K. S. Leung, and D. Zhou, \Performance-driven interconnect
design based on distributed RC delay model," Proc. DAC, pp. 606-611 (1993).
[16] J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong, \Provably
good performancedriven global routing," Trans. CAD, vol 11, no 6, pp. 739-
752 (1992).
[17] T. Deguchi, T. Koide and S. Wakabayashi \Timing-driven hierarchical global
routing with wire-sizing and buer-insertion for VLSI with multi-routing-
layer," Proc. ASP-DAC, pp.99-104 (2000).
[18] W. C. Elmore, \The transient response of damped linear networks with par-
ticular regard to wide band ampliers," J. Appl. Phys., vol. 19, pp. 55-63
(1948).
[19] J. Heisterman and T. lengauer, \The eÆcient solutions of integer programs
for hierarchical global routing," Trans. on CAD, vol. 10, no. 6, pp. 748-753
(1991).
[20] D. Hightower, \A solution to line routing problems on the continuous plane,"
Proc. Design Automation Workshop, pp. 1-24, (1969).
[21] G. Karypis, R. Aggarwal, V. Kumar, and S. shekhar, \Multilevel hypergraph
partitioning: Application in VLSI domain," IEEE Trans. VLSI Systems , vol.
7, pp. 69{79, Mar. 1999.
[22] R. Kastner, E. Bozorgzadeh and M. Sarrafzadeh, \Predictable Routing," Proc.
ICCAD, pp.110-114 (2000).
[23] Lee, \An algorithm for path connection and its application," IRE Trans. Elec-
tronic Computer, EC-10(1961).
[24] S.-C. Lee, J.-M. Hsu, and Y.-W. Chang, \Multilevel large-scale module place-
ment/ oorplanning using B*-trees," in Proceedings of The 12th VLSI De-
sign/CAD Symposium, Hsinchu, Taiwan, Aug. 2001.
[25] J. Lillis, C.-K Cheng, T.-T. Y. Lin and C.-Y. Ho, \ New Performance Driven
routing techniques with explicit area/delay tradeo and simultaneous wiresiz-
ing," Proc. DAC, pp. 395-400 (1996).
[26] M. Marek-Sadowska, \Route planner for custom chip design," Proc. ICCAD,
pp. 246- 249 (1986).
[27] G. Meixner and U. Lauther, \A New Global Router Based on a Flow Model
and Linear Assignment," Proc. ICCAD, pp.44-47 (1990).
[28] S. M. Sait and H. Youssef, VLSI Physical Design Automation.
[29] J. Soukup, \Fast maze router," Proc. DAC, pp.100-102, (1978).
[30] D. Wang and E. Kuh, \A new timing-driven multilayer MCM/IC routing
algorithm," Proc. Multi-chip Module Conf., pp.89{94, Feb. (1997).
[31] H. Zhou and D. F. Wong, \Global routing with crosstalk constraints," Proc.
DAC, pp. 374-377 (1998).
[32] The International Technology Roadmap for Semiconductors (2001).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top