近年來，積體電路電腦輔助設計軟體隨著積體電路工業而越來越發達，擺置合法化是積體電路電腦輔助設計軟體中極為重要的部分。擺置合法化將電路元件擺在合法的位置。目前文獻上的擺置合法化方法通常只以位移量為考慮的準則，但卻有可能擺出線長過長的擺置結果。也因為管理空白空間的機制不好，導致執行效率不好。為此，合法化必須同時考慮到位移量與線長，並要有一套管理空白空間的機制。本論文中，提出了一套管理空白空間的機制，階層式地分群rows以建立索引，並藉由合理地計算出cell對每一群rows的距離以及修改深度優先搜尋的方式來搜尋，以達成縮小搜尋範圍的加速功能。在尋找空白空間時也同時考慮了位移量與線長。至於Cell擺入row中的方法，我們改進了Abacus [27]的公式，改為尋找中位數，也為此提出了更有效率的試擺方法。最後，藉由實作文獻上其他方法與本論文所提的方法，在2005年及2006年ACM ISPD擺置比賽用的電路上[30]進行合法化的動作，證明本論文之方法能有效率地獲得品質不錯的合法化結果。

In recent years, a number of studies have been done on Computer-Aided Design (CAD) for IC design. Legalization is one of important issues on CAD. The existed methods for legalization usually try to minimize the total displacements of cells. However, consideration of total displacements only may lead to the problem that wirelength is too large. Another critical problem is the row management, which may influence the efficiency of legalization. Therefore, the legalization must simultaneously consider the displacement and the wirelength, as well as the good row searching management. In this paper, we propose a novel clustering-based mechanism for row searching management. At first, a row index structure is established to search the best row by using recursive clustering algorithms. Then, we propose a method for trial placement to find the position of the cell on the row. Finally, all the cells would be inserted into their corresponding best rows. To evaluate our proposed method, we use ACM ISPD 2005 and 2006 placement contest benchmarks [30] as experimental data. Experimental results show that our proposed method can efficiently obtain high-quality results.

[1] Ameya Agnihorti, Mehmet Can Yildiz, Ateen Khatkhate, Ajita Mathur, Satoshi Ono, and Patrick H. Madden, “Fractional cut: Improved recursive bisection placement,” Proc. ICCAD, pp. 307-310, 2003.
[2] Ulrich Brenner and Jens Vygen, “Legalizing a placement with minimum total movement,” IEEE TCAD, 23(12):1597-1613, Dec.2004.
[3] Ulrich Brenner and Markus Struzyna, “Faster and better global placement by a new transportation algorithm,” Proc. DAC, pp. 591-596, 2005.
[4] Tony Chan, Jason Cong, Kento Sze, and Min Xie, “mPL6: Enhanced multilevel mixed-size placement,” Proc. ISPD, pp. 212-214, 2006.
[5] Yun-Chih Chang, Yao-Wen Chang, Guang-Ming Wu, and Shu-Wei Wu, “B*-Trees: A New Representation for Non-Slicing Floorplans,” Proc. DAC, pp.458-463 ,2000
[6] Yao-Wen Chang, Jai-Ming Lin, “TCG: A Transitive Closure Graph-Based Representation for Non-Slicing Floorplans,” Proc. DAC, pp.764-769, 2001
[7] Tung-Chieh Chen and Yao-Wen Chang, “Modern Floorplanning Based on Fast Simulated Annealing,” Proc. ISPD I, pp.104-112, 2005
[8] Tung.Chieh. Chen, Zhe.Wei. Jiang, Tien.Chang. Hsu, Hsin.Chen. Chen, and Yao.Wen. Chang, “NTUplace3:A high-quality mixed-size analytical placer considering preplaced blocks and density constraints,” Proc. ICCAD, pp. 187-192, 2006.
[9] Konrad Doll, Frank M. Johannes, and Kurt J. Antreich, “Iterative placement improvement by network flow methods,” IEEE TCAD, 13(10):1189-1200, Oct. 1994.
[10] J. A. Hartigan and M. A. Wong, “A K-Means Clustering Algorithm,” Proc. Applied Statistics, Vol. 28, No. 1, p100-108.
[11] Dwight Hill, “Method and system for high speed detailed placement of cells within integrated circuit designs,” U.S. Patent 6370673, Apr. 2002.
[12] Sung-Woo Hur and John Lillis, “Mongrel: Hybrid techniques for standard cell placement,” Proc. ICCAD, pp. 165-170, 2000.
[13] Andrew B. Kahng, Paul Tucker and Alex Zelikovsky, “Optimization of Linear Placements for Wirelength Minimization with Free Sites,” Proc. Asia and South Pacific Design Automation Conference 1999 (ASP-DAC'99), pp. 241-244, 1999.
[14] Andrew B. Kahng, Igor L. Markov, and Sherief Reda, “On legalization of row-based placements,” Proc. GLS-VLSI, pp. 214-219, 2004.
[15] Andrew B. Kahng and Qinke Wang, “Implementation and extensibility of an
analytic placer,” IEEE TCAD, 24(05):734-747, May 2005.
[16] Jai-Ming Lin and Yao-Wen Chang, “TCG-S: orthogonal coupling of P*-admissible representations for general floorplans,” Proc. DAC, pp.842-847, 2002
[17] Jai-Ming Lin, Yao-Wen Chang, and Shih-Ping Lin, “Corner sequence - a P-admissible floorplan representation with a worst case linear-time packing scheme,” Proc. TVLSI, pp. 679- 686, Aug. 2003
[18] Carlos B. Lucasius, Adrie D. Dane, and Gerrit Kateman, “On k-medoid clustering of large data sets with the aid of a genetic algorithm: background, feasibility andcomparison,” Analytica Chimica Acta, vol. 282, no3, pp. 647-669, 1993.
[19] Tao Luo, Haoxing Ren, Charles J. Alpert, and David Z. Pan, “Computational geometry based placement migration,” Proc. DAC, pp. 41-47, 2007.
[20] Hiroshi Murata, Kunihiro Fujiyoshi, Shigetoshi Nakatake, and Yoji Kajitani, “Rectangle-packing-based module placement,” Proc. ICCAD, pp.472 - 479 ,1995
[21] Min Pan, Natarajan Viswanathan, and Chris Chu, “An efficient and effective detailed placement algorithm,” Proc. ICCAD, pp. 48-55, 2005.
[22] Haoxing Ren, David Z. Pan, Charles J. Alpert, and Paul Villarrubia, “Diffusion-
based placement migration,” Proc. DAC, pp. 515- 520, 2005.
[23] Jarrod A. Roy, David A. Papa, Saurabh N. Adya, Haward H. Chan, Aaron N. Ng, James F. Lu, and Igor L. Markov, “Capo: Robust and scalable open-source min-cut floorplacer,” Proc. ISPD, pp. 224- 226, 2005.
[24] T. Ohtsuki, N. Sugiyama, and H. Kawanishi, “An optimization technique for integrated circuit layout design,” Proc. ICCST-Kyoto, pp. 67-68, Sept. t970.
[25] M. Sarrafzadeh and M. Wang,“ NRG: Global and detailed placement,” Proc. ICCAD, pp. 532-537, 1997.
[26] Peter Spindler and Frank M. Johannes, “Fast and robust quadratic placement combined with an exact linear net model,” Proc. ICCAD, pp. 179-186, 2006.
[27] Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes, “Abacus: Fast legalization of standard cell circuits with minimal movement,” Proc. ISPD, pp. 47-53, 2008.
[28] T. C. Wang and D. F. Wong, “Optimal floorplan area optimization,” IEEE Trans. Computer-Aided Design,11 (1992), 992–1002.
[29] D. F. Wong and C. L. Liu, “A new algorithm for floorplan design,” Proc. ACM/IEEE Design Automation Conference, pp. 101-107, 1986.
[30] http://www.ispd.cc/