類比積體電路在繞線的階段，為了減少寄生效應和串線干擾，最佳的繞
線線路最好不要通過類比裝置所在的區域。所以，緊密的佈局擺置是不
實際的類比設計。因為在類比裝置之間，需要保留足夠空間來繞線，才
能使得繞線成功。雖然已經存在許多關於類比佈局擺置並且考慮拓撲限
制的研究，但是在類比佈局擺置時考慮可繞度的相關研究卻是很少。所
以在本文中，我們提出一個以可繞度為導向之類比積體電路佈局擺置。
該佈局擺置演算法首先產成一個緊密的佈局擺置，接著在沒有破壞類比
佈局對稱的特性下，擴大此佈局擺置來消除擁擠的繞線。實驗的結果證
明，我們的類比佈局擺置可以有效的減少擁擠的繞線和滿足多種拓樸的
限制。

In order to reduce parasitics and cross-talk effects during the routing phase, wires are preferred not to pass above the active area of analog devices. For successful routing, it is required to preserve enough routing spaces between devices. Therefore, a compact placement is not practical for analog design. Although many works have been proposed to consider topological constraints for analog placement, there exists limited studies on analog placement considering routability. In this thesis, we present a routability-driven analog placer. The placement algorithm first generates a compact placement, and then expands the placement to eliminate routing congestion without breaking the symmetry property of analog layout. Experimental results show that our analog placer can effectively minimize routing congestion and satisfy multiple topological constraints.

[1] H. Graeb, F. Balasa, R. Castro-Lopez, Y.-W. Chang, F.V. Fernandez, P.-H. Lin, and M. Strasser, “Analog layout synthesis - Recent advances in topological approaches,” Proc. DATE, 2009, pp. 274-279.
[2] J. M. Cohn, D. J. Garrod, R. A. Rutenbar, and L. R. Charley, “Analog Device-level Layout Automation,” Kluwer Academic Publishers, 1994.
[3] L. Xiao, E. F.Y. Young, X. He, and K.P. Pun, “Practical placement and routing techniques for analog circuit designs,” Proc. ICCAD, 2010, pp. 675-679.
[4] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[5] F. Balasa and K. Lampaert, “Module placement for analog layout using the sequence-pair representation,” Proc. DAC, 1999, pp. 274-279.
[6] Y.-X. Pang, F. Balasa , K. Lampaert, and C.-K. Cheng, “Block placement with symmetry constraints based on the O-tree non-slicing representation,” Proc. DAC, 2000, pp. 464-467.
[7] F. Balasa, “Modeling non-slicing floorplans with binary trees,” Proc. ICCAD, 2000, pp.13-16.
[8] J.-M. Lin, G.-M. Wu, Y.-W. Chang, and J.-H. Chuang, “Placement with symmetry constraints for analog layout design using TCG-S,” Proc. ASPDAC, 2005, pp. 1135-1138.
[9] J. Liu, S. Dong, Y. Ma, D. Long, and X. Hong, “Thermal-driven symmetry constraint for analog layout with CBL representation,” Proc. ASPDAC, 2007, pp. 191-196.
[10] P.-H. Lin and S.-C. Lin, “Analog placement based on novel symmetry-island formulation,” Proc. DAC, 2007, pp. 465-470.
[11] P.-H. Lin, H. Zhang, M. D. F.Wong, and Y.-W. Chang, “Thermal-driven analog placement considering device matching,” Proc. DAC, 2009, pp. 593-598.
[12] Q. Ma, E. F. Y. Young, and K. P. Pun, “Analog placement with common centroid constraints,” Proc. ICCAD, 2007, pp. 579-585.
[13] L. Xiao and E. F. Y. Young, “Analog placement with common centroid and 1-D symmetry sonstraints,” Proc. ASPDAC, 2009, pp. 353-360.
[14] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing-based module placement,” Proc. ICCAD, 1995, pp. 472-479.
[15] Y.-C. Tam, E. F. Y. Young, and C. Chu, “Analog placement with symmetry and other placement constraints,” Proc. ICCAD, 2006, pp. 349-354.
[16] P.-H. Lin and S.-C. Lin, “Analog placement based on hierarchical module clustering,” Proc. DAC, 2008, pp. 50-55.
[17] M. Strasser, M. Eick, H. Graeb, U. Schlichtmann, and F. M. Johannes, “Deterministic analog circuit placement using hierarchically bounded enumeration and enhanced shape functions,” Proc. ICCAD, 2008, pp. 306-313.
[18] J.-M. Lin, C.-W. Lin, C.-P. Huang, and S.-J. Chang, “Performance-driven analog placement considering boundary constraint,” Proc. DAC, 2010, pp. 292-297.
[19] Chris C. N. Chu, Yiu-Chung Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” Proc. TCAD, 2008, pp. 70-83.
[20] M. Pan and C. Chu, “FastRoute: A step to integrate global routing into placement,” Proc. ICCAD, 2006, pp. 464-471.
[21] Dimitris Bertsimas and John Tsitsiklis, “Simulated Annealing,” Proc. Statistical Science 1993, Vol. 8, No1, 10-15.