成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林城伍 Lin, Cheng-Wu
論文名稱：	考量元件匹配性與可繞線性之類比積體電路擺置演算法 Matching-Driven and Routing-Aware Placement Algorithms for Analog Integrated Circuits
指導教授：	張順志 Chang, Soon-Jyh
共同指導教授:	林家民 Lin, Jai-Ming
學位類別：	博士 Doctor
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2013
畢業學年度：	101
語文別：	英文
論文頁數：	135
中文關鍵詞：	類比電路擺置、共質心擺置、電容陣列、可繞線性
外文關鍵詞：	Analog placement, common-centroid placement, capacitor array, routability
相關次數：	點閱：121 下載：3
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

由於類比電路的敏感度強，因此有許多的設計考量，例如製程變異、寄生效應不匹配、繞線所衍生之訊號偶合等等，除了電路設計的本質之外，電路佈局的品質也會嚴重地影響到電路效能。由於不同應用的類比電路有不同的設計考量，我們難以用一種通用的方法來實現所有電路的佈局，過去文獻有非常多關於類比電路的擺置方法，其中大部分的方法是以最小化佈局面積與繞線總長度作為目標，但是將面積最小化的結果可能會產生一個過度密集的擺置，進而造成可繞線性問題。
在本論文中，所探討的類比電路擺置方法著重在兩個課題：電容擺置與可繞線性擺置。電容擺置是針對電容陣列來產生合適的共質心擺置，其中電容陣列是廣泛應用在切換式電容電路中的一個基本單元，我們提出了兩個方法來實現匹配性考量之電容擺置，第一個方法是利用模擬退火演算法，在同時考量多個擺置限制的情況下依然有優異的擺置結果，而第二個方法則是利用解析法來減少擺置所需花費的時間。另一方面，為了解決電路擺置結果所可能衍生之繞線問題，我們進一步考量對稱島的邊界條件，並提出一個可繞線性考量之擺置方法，先評估繞線的擁擠程度，再對擺置結果進行擴展以產生足夠的繞線空間，如此一來，在擺置階段就可以消除一些繞線問題。
實驗結果顯示，我們所提出的二個電容擺置方法與過去文獻相比較，皆能夠達到較好的匹配性以及較高的元件相關性。此外，所提出的可繞線性考量之擺置方法可以有效地降低繞線的擁擠程度，並且確保類比電路擺置所要求之對稱性質。

Analog circuits are sensitive to many factors such as process variation, parasitic mismatches, and routing-induced signal coupling. In addition to circuit sizing, layout generation has a great impact on circuit performance. Since different analog circuits have different trade-offs among various aspects, it is difficult to apply a unified layout implementation approach for all circuits. Many placement methods have been studied for analog circuits, and most of these works were devoted to the minimization of layout area and total wirelength. However, area minimization may generate an over compact placement and thus cause routability issue.
In this dissertation, the proposed analog placement methods focus on two subjects, capacitor placement and routability-driven placement. The capacitor placement is used to construct common-centroid placements for capacitor arrays, which are a common component in switched-capacitor circuits. We present two methods to achieve mismatch-aware capacitor placement. The first method uses the simulated annealing algorithm to obtain superior results under various placement constraints. The second method employs an analytical approach to accelerate the placement process. To deal with possible routing issues caused by placement, we further consider symmetry-island boundary constraint and introduce a routability-driven placement methodology to alleviate the routing effects during the placement phase. The proposed placement algorithm performs congestion estimation followed by placement expansion to accomplish sufficient routing space.
Experimental results show that both the proposed capacitor placement methods achieve lower oxide-gradient-induced mismatch and higher capacitance correlation than those of previous works. Moreover, the proposed routability-driven placement approach is effective to minimize routing congestion without breaking the symmetry property of analog placement.

Abstract (Chinese) I
Abstract III
Acknowledgements (Chinese) V
List of Tables IX
List of Figures X
Chapter 1. Introduction 1
1 Analog Placement 1
1.1 Placement Constraints 2
1.2 Placement Approaches 4
1.3 Placement Representations 6
2 Beyond the Minimization of Layout Area and Total Wirelength 8
2.1 Application-Specific Placer 8
2.2 Routing Congestion 11
3 Overview of the Dissertation 12
3.1 Matching-Driven Capacitor Placement 12
3.2 Analytical Method for Fast Capacitor Placement 13
3.3 Routing-Aware Analog Placement 14
4 Organization of the Dissertation 15
Chapter 2. Matching-Driven Capacitor Placement 16
1 Motivation 16
2 Problem Formulation 20
2.1 Oxide Gradient Model 22
2.2 Spatial Correlation Model 23
3 Pair-Sequence Representation 24
3.1 Matrix to Pair Sequence Transformation 24
3.2 Pair Sequence to Matrix Transformation 26
4 Basic Unit-Capacitor Pairing 27
5 Extended Unit-Capacitor Pairing 30
5.1 Dummy Unit Capacitors 34
5.2 Adjacent Unit Capacitors 35
5.3 Pairing Procedure 36
6 Placement Algorithm 40
6.1 Overview of Placement Flow 40
6.2 Placement Initialization 42
6.3 Perturbation 44
6.4 Maintaining a Feasible Placement 45
6.5 Efficiency Improvements 48
7 Experimental Results 49
7.1 Arbitrary-Ratio Capacitor Arrays 50
7.2 Integer-Ratio Capacitor Arrays 51
7.3 Capacitor Arrays with Dummy Capacitors 54
Chapter 3. Analytical Method for Fast Capacitor Placement 57
1 Motivation 57
2 Placement Exploration 59
2.1 Linear (First-Order) Gradient Error 64
2.2 Quadratic (Second-Order) Gradient Error 65
2.3 High-Order Gradient Errors and Device Correlation 67
2.4 Routing Channel Width 68
3 Placement Facilitation 70
3.1 Representative Entries 71
3.2 Representative Unit Capacitors 72
4 Modeling of Placement Cost Function 74
4.1 Linear Gradient Error 75
4.2 Quadratic Gradient Error 75
4.3 Routing Channel Width 77
5 Placement Algorithm 79
5.1 Global Placement 79
5.2 Legalization 81
5.3 Post Optimization 82
6 Experimental Results 84
Chapter 4. Routing-Aware Analog Placement 90
1 Motivation 90
2 Preliminaries 94
2.1 Symmetry Island and ASF-B*-tree Representation 94
2.2 Hierarchical Placement and HB*-tree Representation 95
3 Symmetry-Island Boundary Constraint 96
3.1 Boundary Constraint in 1D Symmetry Island 97
3.2 Boundary Constraint in 2D Symmetry Island 100
3.3 Maintaining a Feasible Placement 102
4 Routability-Driven Placement Methodology 105
4.1 Problem Formulation 105
4.2 Overview of Placement Flow 106
4.3 Congestion Estimation and Placement Expansion 107
4.4 Dummy Node Insertion outside a Symmetry Group 110
4.5 Dummy Node Insertion in a Symmetry Group 113
4.6 Placement Algorithm 117
5 Experimental Results 119
Chapter 5. Concluding Remarks and Future Work 122
1 Concluding Remarks 122
2 Future Work 124
Bibliography 126
Publication List 133
                                    

[1] J. M. Cohn, D. J. Garrod, R. A. Rutenbar, and L. R. Charley, Analog Device-Level Layout Automation. Kluwer Academic Publishers, 1994.
[2] S. W. Mehranfar, “STAT: a schematic to artwork translator for custom analog cells,” in Proc. IEEE Custom Integr. Circuits Conf., 1990, pp. 30.2.1-30.2.4.
[3] D. Long, X. Hong, and S. Dong, “Signal-path driven partition and placement for analog circuit,” in Proc. IEEE/ACM Asia South Pacific Design Autom. Conf., 2006, pp. 694-699.
[4] P.-H. Wu, M. P.-H. Lin, Y.-R. Chen, B.-S. Chou, T.-C. Chen, T.-Y. Ho, and B.-D. Liu, “Performance-driven analog placement considering monotonic current paths,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2012, pp. 613-619.
[5] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[6] M. Strasser, M. Eick, H. Graeb, U. Schlichtmann, and F. M. Johannes, “Deterministic analog circuit placement using hierarchically bounded enumeration and enhanced shape functions,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2008, pp. 306-313.
[7] D. W. Jepsen and C. D. Gellat Jr., “Macro placement by Monte Carlo annealing,” in Proc. IEEE Int. Conf. Comp. Design, 1983, pp. 495-498.
[8] J. M. Cohn, D. J. Garrod, R. A. Rutenbar, and L. R. Carley, “KOAN/ANAGRAM II: new tools for device-level analog placement and routing,” IEEE J. Solid-State Circuits, vol. 26, no. 3, pp. 330-342, Mar. 1991.
[9] K. Lampaert, G. Gielen, and W. Sansen, “A performance-driven placement tool for analog integrated circuits,” IEEE J. Solid-State Circuits, vol. 30, no. 7, pp. 773-780, July 1995.
[10] E. Malavasi, E. Charbon, E. Felt, and A. Sangiovanni-Vincentelli, “Automation of IC layout with analog constraints,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 15, no. 8, pp. 923-942, Aug. 1996.
[11] Y.-X. Pang, F. Balasa , K. Lampaert, and C.-K. Cheng, “Block placement with symmetry constraints based on the O-tree non-slicing representation,” in Proc. ACM/IEEE Design Autom. Conf., 2000, pp. 464-467.
[12] F. Balasa, “Modeling non-slicing floorplans with binary trees,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2000, pp. 13-16.
[13] P.-H. Lin and S.-C. Lin, “Analog placement based on novel symmetry-island formulation,” in Proc. ACM/IEEE Design Autom. Conf., 2007, pp. 465-470.
[14] F. Balasa and K. Lampaert, “Symmetry within the sequence-pair representation in the context of placement for analog design,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 19, no. 7, pp. 721-731, July 2000.
[15] Y.-C. Tam, E. F. Y. Young, and C. Chu, “Analog placement with symmetry and other placement constraints,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2006, pp. 349-354.
[16] J.-M. Lin, G.-M. Wu, Y.-W. Chang, and J.-H. Chuang, “Placement with symmetry constraints for analog layout design using TCG-S,” in Proc. IEEE/ACM Asia South Pacific Design Autom. Conf., 2005, pp. 1135-1138.
[17] L. Zhang, C.-J. R. Shi, and Y. Jiang, “Symmetry-aware placement with transitive closure graphs for analog layout design,” in Proc. IEEE/ACM Asia South Pacific Design Autom. Conf., 2008, pp. 180-185.
[18] Q. Ma, E. F. Y. Young, and K. P. Pun, “Analog placement with common centroid constraints,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2007, pp. 579-585.
[19] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-trees: a new representation for non-slicing floorplans,” in Proc. ACM/IEEE Design Autom. Conf., 2000, pp. 458-463.
[20] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “An O-tree representation of non-slicing floorplan and its applications,” in Proc. ACM/IEEE Design Autom. Conf., 1999, pp. 268-273.
[21] D. B. Ribner and M. A. Copeland, “Biquad alternatives for high-frequency switched-capacitor filters,” IEEE J. Solid-State Circuits, vol. 20, no. 6, pp. 1085-1095, Dec. 1985.
[22] D. Khalil, M. Dessouky, V. Bourguet, M.-M. Louerat, A. Cathelin, and H. Ragai, “Evaluation of capacitor ratios in automated accurate common-centroid capacitor arrays,” in Proc. IEEE Int. Symp. Quality Electron. Design, 2005, pp. 143-147.
[23] M. J. McNutt, S. LeMarquis, and J. L. Dunkley, “Systematic capacitance matching errors and corrective layout procedures,” IEEE J. Solid-State Circuits, vol. 29, no. 5, pp. 611-616, May. 1994.
[24] J.-B. Shyu, G. C. Temes, and F. Krummenacher, “Random error effects in matched MOS capacitors and current sources,” IEEE J. Solid-State Circuits, vol. 19, no. 6, pp. 948-956, Dec. 1984.
[25] E. Felt, A. Narayan, and A. Sangiovanni-Vincentelli, “Measurement and modeling of MOS transistor current mismatch in analog IC’s,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 1994, pp. 272-277.
[26] A. Hastings, The Art of Analog Layout, 2nd ed. Prentice Hall, 2006.
[27] M. J. M. Pelgrom, A. C. J. Duinmaijer, and A. P. G. Welbers, “Matching properties of MOS transistors,” IEEE J. Solid-State Circuits, vol. 24, no. 5, pp. 1433-1440, Oct. 1989.
[28] P.-W. Luo, J.-E Chen, C.-L. Wey, L.-C. Cheng, J.-J. Chen, and W.-C. Wu, “Impact of capacitance correlation on yield enhancement of mixed-signal/analog integrated circuits,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 27, no. 11, pp. 2097-2101, Nov. 2008.
[29] J.-E Chen, P.-W. Luo, and C.-L. Wey, “Placement optimization for yield improvement of switched-capacitor analog integrated circuits,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 29, no. 2, pp. 313-318, Feb. 2010.
[30] 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 Int. Conf. Comput.-Aided Design, 2010, pp. 675-679.
[31] D. Sayed and M. Dessouky, “Automatic generation of common-centroid capacitor arrays with arbitrary capacitor ratio,” in Proc. ACM/IEEE Design Autom. Test Eur. Conf. Exhibit., 2002, pp. 576-580.
[32] L. Xiao and E. F. Y. Young, “Analog placement with common centroid and 1-D symmetry sonstraints,” in Proc. IEEE/ACM Asia South Pacific Design Autom. Conf., 2009, pp. 353-360.
[33] Q. Ma, L. Xiao, Y.-C. Tam, and E. F. Y. Young, “Simultaneous handling of symmetry, common centroid, and general placement constraints,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 30, no. 1, pp. 85-95, Jan. 2011.
[34] M. P.-H. Lin, H. Zhang, M. D. F. Wong, and Y.-W. Chang, “Thermal-driven analog placement considering device matching,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 30, no. 3, pp. 325-336, Mar. 2011.
[35] J.-E Chen, P.-W. Luo, and C.-L. Wey, “Yield evaluation of analog placement with arbitrary capacitor ratio,” in Proc. IEEE Int. Symp. Quality Electron. Design, 2009, pp. 179-184.
[36] D. A. Johns and K. Martin, Analog Integrated Circuit Design. John Wiley & Sons, 1997.
[37] D. Khalil, M. Dessouky, V. Bourguet, M.-M. Louerat, A. Cathelin, and H. Ragai, “Compensated layout for automated accurate common-centroid capacitor arrays,” in Proc. IEEE Int. Conf. Elect. Electron. Comput. Eng., 2004, pp. 481-484.
[38] R. C. J. Taylor, “Switched capacitor filters,” in Analog Circuit Design, R. J. van de Plassche, W. M. C. Sansen, and J. H. Huijsing, Eds. Norwell, MA: Kluwer, 1995, pp. 203-225.
[39] Y.-W. Chang, Z.-W. Jiang, and T.-C. Chen, “Essential issues in analytical placement algorithms,” IPSJ Trans. System LSI Design Methodology, vol. 2, pp. 145-166, Aug. 2009.
[40] Y. Cong and R. L. Geiger, “Switching sequence optimization for gradient error compensation in thermometer-decoded DAC arrays,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 47, no. 7, pp. 585-595, July 2000.
[41] G. A. M. Van Der Plas, J. Vandenbussche, W. Sansen, M. S. J. Steyaert, and G. G. E. Gielen, “A 14-bit intrinsic accuracy Q2 random walk CMOS DAC,” IEEE J. Solid-State Circuits, vol. 34, no. 12, pp. 1708-1718, Dec. 1999.
[42] K.-C. Kuo and C.-W. Wu, “A switching sequence for linear gradient error compensation in the DAC design,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 58, no. 8, pp. 502-506, Aug. 2011.
[43] M. Vadipour, “Gradient error cancellation and quadratic error reduction in unary and binary D/A converters,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 50, no. 12, pp. 1002-1007, Dec. 2003.
[44] C. F. T. Soares and A. Petraglia, “Automatic placement of identical unit capacitors to improve capacitance matching,” in Proc. IEEE Int. Symp. Circuits and Systems, 2009, pp. 1739-1742.
[45] J. Bastos, A. M. Marques, M. S. J. Steyaert, and W. Sansen, “A 12-bit intrinsic accuracy high-speed CMOS DAC,” IEEE J. Solid-State Circuits, vol. 33, no. 12, pp. 1959-1969, Dec. 1998.
[46] Y. Nakamura, T. Miki, A. Maeda, H. Kondoh, and N. Yazawa, “A 10-b 70-MS/s CMOS D/A converter,” IEEE J. Solid-State Circuits, vol. 26, no. 4, pp. 637-642, Apr. 1991.
[47] J. Bastos, M. S. J. Steyaert, A. Pergoot, and W. M. Sansen, “Influence of die attachment on MOS transistor matching,” IEEE Trans. Semicond. Manuf., vol. 10, no. 2, pp. 209-218, May 1997.
[48] W. C. Naylor, R. Donelly, and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer,” U.S. Patent 6 301 693, Oct. 9, 2001.
[49] E. K. P. Chong and S. H. Zak, An Introduction to Optimization, 3rd ed. Hoboken, NJ: Wiley-Interscience, 2008.
[50] C.-W. Lin, J.-M. Lin, Y.-C. Chiu, C.-P. Huang, and S.-J. Chang, “Common-centroid capacitor placement considering systematic and random mismatches in analog integrated circuits,” in Proc. ACM/IEEE Design Automation Conf., 2011, pp. 528-533.
[51] F. Balasa, S. C. Maruvada, and K. Krishnamoorthy, “On the exploration of the solution space in analog placement with symmetry constraints,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 23, no. 2, pp. 177-191, Feb. 2004.
[52] M. Pan and C. Chu, “FastRoute: a step to integrate global routing into placement,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2006, pp. 464-471.
[53] C. Chu and Y.-C. Wong, “FLUTE: Fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 27, no. 1, pp. 70-83, Jan. 2008.
[54] Y.-J. Chang, Y.-T. Lee, and T.-C. Wang, “NTHU-Route 2.0: A fast and stable global router,” in Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, 2008, pp. 338-343.

校內：立即公開
校外：立即公開

簡易檢索 / 詳目顯示

相關論文