臺灣博碩士論文加值系統

類比電路的佈局自動化在多年來已經進步了許多。然而，使用先進製程的集成電路(IC)中對於類比這部分依然採用手動的方式來進行設計。類比電路的系統性較低，大多都是基於啟發式的(heuristic-based)、需要多年的時間設計專業知識以生成高質量的類比電路佈局。而且，他們對於佈局引起的干擾非常敏感，會大幅地影響佈局品質。當我們採用深奈米技術節點時，佈局效應(layout dependent effects, LDE)，例如井鄰近效應(well proximity effects, WPE)，擴散區的長度(length of diffusion)以及氧化物之間的距離(oxide-to-oxide spacing)是決定佈局質量方面的重要指標。因此，類比IC佈局設計需要經過反覆調整以生成可接受的佈局是件容易出錯並且費時的過程。約束導向的類比設計流程是解決此問題的一種方法。類比佈局中的專業知識可以用約束的形式來達成，並將其應用到設計流程中以滿足設計規範並實現快速簽核(sign-off)。

本文提出了使用基於生成/優化的方法和算法來改進類比電路佈局和改善電路效能。 在我們的方法中會新進行擺置後再繞線。從電路圖(schematic)生成新的佈局，並滿足約束和設計規範。我們考慮了不同的約束、高效搜索空間修剪技術、並探索多組不同的佈局以生成高性能的類比佈局。

第一種方法著重於類比擺置的問題。平行電流路徑(parallel current paths, PCP)可以有效地編碼兩個常用的類比性能約束，即類比電路中的共同對稱軸(symmetry-island)和電流路徑(current path)的約束。 之後，一個使用序列對(sequence-pair, SP)表示法、並具有較少的搜索空間和更好的成本函數的PCP-SP類比擺置器會被用來進行類比電路的擺放。 PCP-SP擺置器使用快速枚舉拓撲排序算法探索多種佈局的拓撲。實驗結果顯示我們的方法可以改善佈局性能，並協助設計人員從多種佈局拓撲中進行挑選。

在第二種方法中我們進一步改善了PCP-SP放置器。我們的增強版PCP-SP放置器提出三種技術，代表序列對(representative sequence-pair, RSP)、局部單調性(partial-monotonicity)和改進尋找解範圍。RSP表示法提供了一種新穎的生成方式並具有較小搜索空間和快速RSP的對稱可行序列對(symmetry-feasible sequence pairs, SFSP)計算算法。局部單調有助於生成更緊湊的佈局而不犧牲單調繞線的特性。我們使用PCP約束來改善我們的搜索空間探索。實驗結果顯示我們提出的類比擺置方法更快而且可以生成多個緊湊的擺置並具有更好的性能和佈線特性，例如線長和導孔的數量。

我們的最後一種方法主要是著重在類比佈局合成中的擺置和繞線階段。我們提出了一種擺置的新概念，它除了考慮共同對稱軸和電流流向外，進一步考量最小化導線的交錯。我們的方法採用決定間隔搜索樹來決定單調佈局中的交叉點。我們提出了斯坦納集合(group-steiner based)的方法來決定端點(terminal)到端點的連接、端口(port)和斯坦納點(steiner point)的位置。我們在全局和細部繞線階段提出的技術有助於最大程度地減少主極點(dominant poles)處的寄生效應、以及通過總體的交叉數量減少導線負載。實驗結果證明我們的擺置和繞線方法可以顯著地改善與佈局相關的物理效應和性能。

總體而言，這些方法有助於發展類比佈局設計自動化的研究。借由增強序列對這類不可切割的平面規劃(non-slicing floorplan)表示法，我們能夠在現今且敏感的類比佈局合成中進一步考慮電流流向、對稱的擺置和考量負載影響的繞線規劃。實驗結果驗證了我們對於電路性能的主張。

Analog layout automation sees improvements over the years; however, the process in advanced technology nodes is still mostly a manual step in the integrated circuit industry. The analog designs are less systematic and more of heuristic-based, requiring years of design expertise to generate a good quality analog layout. Moreover, they are sensitive to layout induced disturbances, which can greatly impact the layout quality. As we advance into deep nanometer technology nodes, the layout-dependent effects (LDE), i.e., well proximity effect, length of diffusion, and oxide-to-oxide spacing, are also playing a significant role in deciding the layout quality. Thus, the analog IC layout design is error-prone and time-consuming, which requires repeated refinements to generate an acceptable layout. The constraint-driven analog design flow is a way to mitigate this issue. The design expertise is captured in the form of analog constraints and applied at the early stages of the design flow to meet the design specifications and achieve fast sign-off.

This dissertation proposes methodologies and algorithms to improve the analog layout's performance using the generation/optimization-based approach. In our approach, placement is followed by routing, and a new layout is generated from the schematic, satisfying the constraints and design rules. We have considered different constraints, efficient search space pruning techniques, and multiple solutions exploration to generate high-performance analog layouts.

The first approach focuses on the analog placement problem. Parallel current paths (PCP) are introduced to efficiently encode two commonly used analog performance constraints, i.e., symmetry-island and current path constraint in analog circuits. After that, a PCP-SP analog placer is presented with a reduced search space and a better cost function for the analog placement using sequence-pair (SP) representation. PCP-SP placer can explore multiple placement topologies using a fast enumerative topological ordering algorithm. Experimental results demonstrate that the proposed approach improves layout performance parameters and helps designers select from multiple placement topologies.

Our second approach further enhances PCP-SP placer. We propose three techniques, i.e., representative sequence-pair (RSP), partial-monotonicity, and improved search space exploration for our PCP-SP placer. RSP representation presents a novel way of generating symmetry-feasible sequence pairs (SFSP) with a smaller search space and a fast RSP computation algorithm. Partial-monotonicity helps generate a more compact placement without sacrificing monotonic placement routing characteristics. We use the PCP constraint graph to improve our search space exploration. Experimental results show that our proposed analog placement approach is faster and can generate multiple compact placements with better performance parameters and routing characteristics, like wirelength and via number.

Our last approach focuses on both the placement and routing stages in the analog layout synthesis. We present a new concept for analog placement, which further incorporates poles in addition to consideration of symmetry-island and current flow constraints while minimizing the wire-crossings. Our proposed approach uses an interval search tree to determine crossings from the monotonic placements. We proposed a group-steiner based approach to determine the terminal-to-terminal connections, port and steiner point locations for the routing part. Our proposed techniques at global and detailed routing stages help minimize the parasitics at dominant poles and reduce the wire load via total crossings. Experimental results demonstrate that our placement and routing methodologies can significantly improve layout related physical and performance parameters.

Overall, these approaches help shape the research in analog layout design automation. With the assistance in augmentation of non-slicing floorplan representation sequence-pair, we are able to further consider current flow, symmetrical-island placement, and loading-impacted wire planning in modern and sensitive analog layout synthesis. The empirical results validate our claims in the performance of designs.

List of Tables. . . . . . . . . . . xii
List of Figures . . . . . . . . . . xiii
Symbol List . . . . . . . . . . . . xv
Chapter 1 Introduction . . . . . . 1
1.1 Analog IC Layout Automation . . 1
1.2 Performance-Driven Analog Layout Automation. . 2
1.3 Challenges in Analog Layout Automation . . . . 4
1.4 Organization of this Dissertation . . . . . . 5
Chapter 2 Analog Placement with Current Flow and Symmetry Constraints using PCP-SP . . . . . . . . . . . . . 7
2.1 Introduction and Motivation . . . . . . . . . 7
2.2 Problem Formulation . . . . . . . . . . . .. . 10
2.3 Parallel Current Path Constraints . . . . .. . 12
2.3.1 PCP terms . . . . . . . . . . . . . . . . . 12
2.3.2 PCP Constraints for Different Analog Structures . 14
2.3.3 Advantages of using PCP Constraints . . . . . . . 16
2.4 Methodology . . . . . . . . . . . . . . . . . . . . 16
2.4.1 Conforming PCP Constraints . . . . . . . . . . . .17
2.4.2 Pruning Search Space . . . . . . . . . . . . . . .18
2.4.3 Relative Dimension Checking . . . . . . . . . . . 18
2.4.4 Overall Flow . . . . . . . . . . . . . . . . . . .20
2.5 Experimental Results . . . . . . . . . . . . . . . .21
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . 22
Chapter 3 Exploring Multiple Analog Placements with Partial-Monotonic Current Paths and Symmetry Constraints using PCP-SP 3.1 Motivation . . . . 26
3.2 Problem Formulation . 29
3.3 RSP, PM Current Paths, and PCP Constraints . 31
3.3.1 Representative Sequence-Pair (RSP) . . . . 31
3.3.2 Partial-Monotonic (PM) Current Paths . . . 35
3.3.3 PCP Constraints . . . . . . . . . . . . . .37
3.4 Methodology . . . . . . . . . . . . . . . . .39
3.4.1 Conforming PCP Constraints . . . . . . . . 40
3.4.2 Pruning Search Space . . . . . . . . . . . 40
3.4.3 Design Flow . . . . . . . . . . . . . . . .41
3.5 Experimental Results . . . . . . . . . . . . 47
3.5.1 Folded-Cascode Op-Amp (umc65nm) . . . . . .47
3.5.2 Folded-Cascode Op-Amp (tsmc90nm) . . . . . 48
3.5.3 Variable-Gain Amplifier (umc65nm) . . . . .48
3.6 Summary . . . . . . . . . . . . . . . . . . .50
Chapter 4 Pole-aware Analog Layout Synthesis Considering Monotonic Current Flow and Crossing-Wire Minimization . 56
4.1 Introduction . . . . . . . . . . . . . . . . .56
4.2 Problem Description . . . . . . . . . . . . . 59
4.3 Placement Methodology . . . . . . . . . . . . 59
4.4 Routing Methodology . . . . . . . . . . . . . 61
4.4.1 Group Steiner Problem (GSP) . . . . . . . . 62
4.4.2 Proposed Approach to GSP . . . . . . . . . .63
4.4.3 Overall Flow . . . . . . . . . . . . . . . .67
4.5 Experimental Results . . . . . . . . . . . . .73
4.5.1 Placement . . . . . . . . . . . . . . . . . 73
4.5.2 Routing . . . . . . . . . . . . . . . . . . 75
4.6 Summary . . . . . . . . . . . . . . . . . . . 75
Chapter 5 Conclusion and Future Work . . . . . . .80
5.1 Conclusion . . . . . . . . . . . . . . . . . .80
5.2 Future Work . . . . . . . . . . . . . . . . . 81
References . . . . . . . . . . . . . . . . . . . .83
Vita . . . . . . . . . . . . . . . . . . . . . . .87

[1] P. H. Wu, M. P. H. Lin, T. C. Chen, C. F. Yeh, T. Y. Ho, and B. D. Liu, “Exploring feasibilities of symmetry islands and monotonic current paths in slicing trees for analog placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 6, pp. 879–892, June 2014.
[2] B. Razavi, Design of Analog CMOS Integrated Circuits, 1st ed. McGraw-Hill, 2001.
[3] P. Pan, C. Chin, H. Chen, T. Chen, C. Lee, and J. Lin, “A fast prototyping framework for analog layout migration with planar preservation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 9, pp. 1373-1386, Sep. 2015.
[4] A. Patyal, P. Pan, A. K.A., H. Chen, H. Chi, and C. Liu, “Analog placement with current flow and symmetry constraints using PCP-SP,” in Proc. IEEE/ACM Design Automation Conference, June 2018, pp. 1–6.
[5] H. Chi, H. Tseng, C. J. Liu, and H. Chen, “Performance-preserved analog routing methodology via wire load reduction,” in Proc. IEEE/ACM Asia and South Pacific
Design Automation Conference, Jan 2018, pp. 482–487.
[6] A. Hastings and R. Hastings, The Art of Analog Layout. Pearson Prentice Hall, 2006.
[7] P.-H. Lin, Y.-W. Chang, and S.-C. Lin, “Analog placement based on symmetry-island formulation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 6, pp. 791–804, jun 2009.
[8] M. M. Ozdal and R. F. Hentschke, “Algorithms for maze routing with exact matching constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 33, no. 1, pp. 101–112, 2014.
[9] L. Xiao, E. F. Y. Young, X. He, and K. P. Pun, Practical placement and routing techniques for analog circuit designs,” in Proc. IEEE/ACM International Conference
on Computer-Aided Design, Nov 2010, pp. 675–679.
[10] N. Lourenco, M. Vianello, J. Guilherme, and N. Horta, “Laygen - automatic layout generation of analog ics from hierarchical template descriptions,” in 2006 Ph.D.
Research in Microelectronics and Electronics, 2006, pp. 213–216.
[11] R. Martins, N. Lourenço, and N. Horta, “LAYGEN II-automatic layout generation of analog integrated circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, no. 11, pp. 1641–1654, Nov 2013.
[12] Y.-P. Weng, H.-M. Chen, T.-C. Chen, P.-C. Pan, C.-H. Chen, and W.-Z. Chen, Fast analog layout prototyping for nanometer design migration,” in Proc. IEEE/ACM International Conference on Computer-Aided Design, Nov. 2011, pp. 517—522.
[13] Y. Tam, E. F. y. Young, and C. Chu, “Analog placement with symmetry and other placement constraints,” in Proc. IEEE/ACM International Conference on Computer Aided Design, Nov 2006, pp. 349–354.
[14] Y. Tam, E. Young, and C. Chu, “Analog placement with symmetry and other placement constraints,” in Proc. IEEE/ACM International Conference on Computer-Aided Design, 2006, pp. 349–354.
[15] M. Strasser, M. Eick, H. Grab, U. Schlichtmann, and F. M. Johannes, “Deterministic analog circuit placement using hierarchically bounded enumeration and enhanced shape functions,” in Proc. IEEE/ACM International Conference on Computer-Aided Design, Nov 2008, pp. 306–313.
[16] P.-H. Lin and S.-C. Lin, “Analog placement based on hierarchical module clustering,”in Proc. IEEE/ACM Design Automation Conference, Jun. 2008.
[17] P.-H. Lin and S.-C. Lin, “Analog placement based on novel symmetry-island formulation,” in Proc. IEEE/ACM Design Automation Conference, June 2007, pp. 465–470.
[18] H.-C. Ou, H.-C. C. Chien, and Y.-W. Chang, Simultaneous analog placement and routing with current flow and current density considerations,” in Proc. IEEE/ACM Design Automation Conference, May 2013, pp. 5:1–5:6.
[19] M. P. H. Lin, Y. W. Chang, and C. M. Hung, “Recent research development and new challenges in analog layout synthesis,” in Proc. IEEE/ACM Asia and South Pacific
Design Automation Conference, Jan 2016, pp. 617–622.
[20] F. Balasa and K. Lampaert, “Symmetry within the sequence-pair representation in the context of placement for analog design,” IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, vol. 19, no. 7, pp. 721–731, Jul 2000.
[21] R. Martins, R. Póvoa, N. Lourenço, and N. Horta, “Current-flow and current-density aware multi-objective optimization of analog ic placement,” Integration, the VLSI
Journal, vol. 55, pp. 295–306, Sept 2016.
[22] D. Long, X. Hong, and S. Dong, “Signal-path driven partition and placement for analog circuit,” in Proc. IEEE/ACM Asia and South Pacific Design Automation
Conference, Jan 2006, pp. 694–699.
[23] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Vlsi module placement based on rectangle-packing by the sequence-pair,” IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518–1524, Dec 1996.
[24] T.-C. Chen and Y.-W. Chang, “Modern floorplanning based on b*-tree and fast simulated annealing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 4, pp. 637–650, April 2006.
[25] X. Tang, R. Tian, and D. F. Wong, “Fast evaluation of sequence pair in block placement by longest common subsequence computation,” IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 12, pp. 1406–1413, Dec 2001.
[26] H. E. Graeb, Analog Layout Synthesis: A Survey of Topological Approaches, 1st ed. Springer Publishing Company, Inc., 2010.
[27] P.-C. Pan, H.-M. Chen, Y.-K. Cheng, J. Liu, and W.-Y. Hu, “Configurable analog routing methodology via technology and design constraint unification,” in Proc. IEEE/ACM International Conference on Computer-Aided Design, Nov 2012, pp.620–626.
[28] Y. Kubo, S. Nakatake, Y. Kajitani, and M. Kawakita, “Explicit expression and simultaneous optimization of placement and routing for analog ic layouts,” in Proc.
IEEE/ACM Asia and South Pacific Design Automation Conference, Jan 2002, pp. 467–472.
[29] C.-W. Lin, C.-C. Lu, J.-M. Lin, and S.-J. Chang, “Routability-driven placement algorithm for analog integrated circuits,” in Proc. ACM International Symposium on Physical Design, Mar 2012, pp. 71–78.
[30] K. Krishnamoorthy, S. C. Maruvada, and F. Balasa, “Topological placement with multiple symmetry groups of devices for analog layout design,” in Proc. IEEE Inter-
national Symposium on Circuits and Systems, May 2007, pp. 2032–2035.
[31] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.
[32] L. Zhang, R. Raut, Y. Jiang, and U. Kleine, “Placement algorithm in analog-layout designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and
Systems, vol. 25, no. 10, pp. 1889–1903, Oct 2006.
[33] H. Ou, K. Tseng, J. Liu, I. Wu, and Y. Chang, “Layout-dependent effects-aware analytical analog placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 8, pp. 1243–1254, Aug 2016.
[34] S. Koda, C. Kodama, and K. Fujiyoshi, “Linear programming-based cell placement with symmetry constraints for analog ic layout,” IEEE Transactions on Computer-
Aided Design of Integrated Circuits and Systems, vol. 26, no. 4, pp. 659–668, April 2007.
[35] D. B. Johnson, A priority queue in which initialization and queue operations take O(loglogD) time, Dec 1981, vol. 15, no. 1.
[36] H. Szu and R. Hartley, “Fast simulated annealing,” Physics Letters A, vol. 122, no. 3, pp. 157 – 162, 1987.
[37] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd ed. The MIT Press, 2009.
[38] Y.-P. Weng, H.-M. Chen, T.-C. Chen, P.-C. Pan, C.-H. Chen, and W.-Z. Chen, Fast analog layout prototyping for nanometer design migration,” in Proc. IEEE/ACM International Conference on Computer-Aided Design, Nov. 2011, pp. 517—522.
[39] H. Chi, Z. Lin, C. Hung, C. J. Liu, and H. Chen, “Achieving routing integrity in analog layout migration via cartesian detection lines,” in Proc. IEEE/ACM International
Conference on Computer-Aided Design, 2019, pp. 1–6.
[40] C.-W. Lin, C.-C. Lu, J.-M. Lin, and S.-J. Chang, “Routability-driven placement algorithm for analog integrated circuits,” in Proc. ACM International Symposium on Physical Design, ser. ISPD ’12. New York, NY, USA: ACM, 2012, p. 71–78.
[41] H. Yao, Y. Cai, and Q. Gao, “Lemar: A novel length matching routing algorithm for analog and mixed signal circuits,” in Proc. IEEE/ACM Asia and South Pacific
Design Automation Conference, 2012, pp. 157–162.
[42] H.-C. Ou, H.-C. C. Chien, and Y.-W. Chang, “Non-uniform multilevel analog routing with matching constraints,” in Proc. IEEE/ACM Design Automation Conference,
Jun. 2012, pp. 549—554.
[43] C. Alpert, D. Mehta, and S. Sapatnekar, Handbook of Algorithms for Physical Design Automation. CRC Press, 2008.
[44] R. Martins, N. Lourenço, A. Canelas, and N. Horta, “Multi-port multi-terminal analog router based on an evolutionary optimization kernel,” in Proc. IEEE Congress
on Evolutionary Computation, 2013, pp. 2789–2796.
[45] R. Martins, N. Lourenço, A. Canelas, and N. Horta, “Electromigration-aware analog router with multilayer multiport terminal structures,” Integration, the VLSI Journal, vol. 47, 09 2014.
[46] C. Y. Lee, “An algorithm for path connections and its applications,” IRE Transactions on Electronic Computers, vol. EC-10, no. 3, pp. 346–365, 1961.