臺灣博碩士論文加值系統

隨著半導體技術的進步，積體電路設計變得更加複雜且耗時。在數位電路設計中，主要依靠電子設計自動化EDA工具實現顯著的自動化。然而，類比設計仍然重度依賴手動調整，相較於數位電路設計需要更多的努力和時間。由於技術進入深次微米時代，佈局依賴效應對類比積體電路佈局的品質有顯著影響。隨著最小特徵尺寸和互連間距的減少，串擾成為一個主要問題。傳統方法通常使用導線繞道或屏蔽導線來減輕平行導線之間的串擾，但這些方法通常佔用更多的佈線資源。
在本論文中，我們提出了一種繞線層設定方法來減少類比佈局中導線間的耦合電容，進而減少串擾。繞線層設定問題被視為圖著色問題，使用層衝突圖來表示。在第一階段，對層衝突圖應用飽和度優先著色演算法( DSATUR)來解決衝突，假設金屬層數沒有限制。這一階段產生初步的繞線層設定，解決了導線交叉和串擾問題，但可能會導致更多的導通孔和金屬層。在第二階段，通過模擬退火來改進繞線層設定，迭代擾動解決方案來改進結果。應用圖鬆弛來允許一些串擾，從而減少金屬層和導通孔數量，縮短上層的線長，並確保對稱性。實驗結果證實，所提出的繞線層設定方法在不佔用額外佈線區域的情況下，有效減少了導線之間的串擾，並提升了最終佈局的整體品質。

The advancements in semiconductor technology have introduced many challenges, making integrated circuit design more intricate and time-consuming. In the digital design, the process is significantly automated with EDA tools. Conversely, analog design remains heavily reliant on manual processes, demanding more effort and time compared to its digital counterpart. Layout-dependent effects have significant influence on the quality of analog integrated circuit layouts, particularly as technology scales into the deep submicron era. With decreasing minimum feature size and interconnect spacings, crosstalk has become a major concern. Traditional approaches often use net detour or shielding nets to alleviate crosstalk between parallel nets. However, these methods often occupy more routing resources.
In this thesis, we propose a layer assignment methodology for analog layout to mitigate coupling capacitance between wires and subsequently reduce crosstalk. The layer assignment problem is modeled in the form of a graph coloring problem, with a layer conflict graph. In the first phase, the Degree of Saturation (DSATUR) graph coloring algorithm is applied to the layer conflict graph to address conflicts, assuming there are no restrictions on the number of metal layers. This phase produces an initial layer assignment, resolving net crossing and crosstalk issues, but may result in a greater number of vias and metal layers. In the second phase, simulated annealing improves the layer assignment by iteratively perturbing the solution. Graph relaxation is applied to allow some crosstalk, thus reducing the number of metal layers and vias, shortening wire lengths in upper layers, and ensuring symmetry. Experimental results confirm that the proposed layer assignment methodology effectively reduces crosstalk among nets without consuming additional routing area, and enhances the overall quality of the final layout.

摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Analog Layout Automation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Crosstalk Noise in Analog Layout . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1 Crosstalk reduction in area routing . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Crosstalk noise reduction at detailed routing stage . . . . . . . . . . . . 6
1.3.3 Routing algorithm with signal shielding . . . . . . . . . . . . . . . . . 9
1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1 Crosstalk Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Proposed Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Net Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Crosstalk Nets Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Layer Assignment Through Graph Coloring . . . . . . . . . . . . . . . . . . . 23
3.4 DSATUR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.5 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.5.1 Neighborhood Structure . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.5.2 Cost Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6 Graph Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

[1] R. A. Rutenbar, “Design automation for analog: The next generation of tool challenges,”
in IBM Academy Conference on Analog Design, Technology, Modeling and Tools, IBM
T.J. Watson Research Labs, 2006.
[2] J. Scheible and J. Lienig, “Automation of analog IC layout: Challenges and solutions,” in
International Symposium on Physical Design, 2015, pp. 33–40.
[3] D. Sylvester and C. Wu, “Analytical modeling and characterization of deep-submicrometer
interconnect,” in Proceedings of the IEEE, vol. 89, no. 5, May 2001, pp. 634–664.
[4] T.-Y. Ho, Y.-W. Chang, S.-J. Chen, and D. T. Lee, “A Fast Crosstalk- and Performance-
Driven Multilevel Routing System,” in International Conference on Computer Aided Design,
2003, pp. 382–387.
[5] R. M. Smey, B. Swartz, and P. H. Madden, “Crosstalk reduction in area routing,” in Design,
Automation and Test in Europe Conference and Exhibition, Munich, Germany, 2003, pp.
862–867.
[6] R. Kastner, E. Bozorgzadeh, and M. Sarrafzadeh, “Predictable routing,” in IEEE/ACM
International Conference on Computer Aided Design. ICCAD, 2000, pp. 110–113.
[7] M. Borah, R. M. Owens, and M. J. Irwin, “An edge-based heuristic for Steiner routing,” in
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13,
no. 12, Dec. 1994, pp. 1563–1568.
[8] D. Wang and E. Kuh, “A performance-driven MCM router with special consideration
of crosstalk reduction,” in Proceedings Design, Automation and Test in Europe, Paris,
France, 1998, pp. 466–470.
[9] D. Wang and E. Kuh, “A New Timing-Driven Multilayer MCM/IC Routing Algorithm,”
in Proc. MCMC’97, 1997, pp. 89–94.
[10] Q. Gao, Y. Shen, Y. Cai, and H. Yao, “Analog circuit shielding routing algorithm based
on net classification,” in 2010 ACM/IEEE International Symposium on Low-Power Electronics
and Design (ISLPED), Austin, TX, USA, 2010, pp. 123–128.
[11] J. M. Rabaey, A. Chandrakasan, and B. Nikolié, “Digital Integrated Circuits: A Design
perspective,” Pearson Education, Inc. 2003, pp. 446–452.
[12] H. Y. Chi, H. C. Chang, C. H. Yang, C. N. Liu, and J. Y. Jou, “Performance-driven Routing
Methodology with Incremental Placement Refinement for Analog Layout Design,” in
Design, Automation Test in Europe Conference Exhibition (DATE), Grenoble, France,
2021, pp. 1218–1223.
[13] A. Patyal, H. M. Chen, M. P. H. Lin, G. Q. Fang, and S. Y. H. Chen, “Pole-Aware Analog
Layout Synthesis Considering Monotonic Current Flows and Wire Crossings,” in IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 42, no. 1,
Jan. 2023, pp. 266–279.
[14] R. M. R. Lewis, “The DSATUR Algorithm,” in A Guide to Graph Colouring. Cham,
Switzerland: Springer, 2016, p. 39–42.
[15] T.-C. Chen and Y.-W. Chang, “Floorplanning,” in Electronic Design Automation: Synthesis,
Verification, and Test. San Francisco, CA, USA: Morgan Kaufmann, 2009, p. 575–
634.
[16] LakerTM from Synopsys, https://www.synopsys.com.
[17] E. Malavasi and A. Sangiovanni-Vincentelli, “Area routing for analog layout,” in IEEE
Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 8,
1993, pp. 1186–1197.