隨著製程的進步，現今電路設計變得越來越複雜，往往晶片中包含了數以百計的模組。由於模組的擺置會影響到標準邏輯閘的散佈，以及模組附近容易會有窄通道或者是模組過大而造成標準邏輯閘額外的繞線，這些問題對於總體繞線長度以及可繞度都有很大的影響。而現今的商業工具還未能在模組擺置階段得到一個可接受的擺置結果，模組擺置仍仰賴工程師的優化。除此之外，電路中往往存有預先擺置模組，預先擺置的模組容易讓模組擺置的區域更加不平整，導致模組擺置的複雜度更大幅的提升。
本篇論文採用三階段混合尺寸擺置的流程，包括：(1)初始擺置 (2)模組擺置 (3)標準邏輯閘擺置。其中我們專注在模組擺置的研究。首先，提出了擺置障礙物與預先擺置模組合併，它能有效的減少障礙物的數量;接著根據模組的階層式名稱建立階層樹，透過階層樹去群集階層相近的模組，有利於將功能相同的子電路擺置在鄰近區域；利用遞迴切割的方法，將過度密集區域的模組群集平均分配，能有效避免區域壅擠；接著利用模組合法化擺置器將子區域內的模組進行合法化，然後進入模組優化階段，採用模擬演化演算法更進一步的優化模組擺置，最後將模組擺置結果輸入到ICC (IC-Compiler) [32] 進行最後的標準邏輯閘擺置。實驗結果證實，我們的演算法能有效增加電路的可繞度，相較於前人的方法 [25] 能夠更有效率的合法化模組擺置。

Due to advance in manufacture technology, circuit designs become more and more complicated, and usually contain hundreds of macros. Macro placement is one of the most important stages since its result has great impact on wirelength and routability. Either the locations of macros will influence the distribution of standard cells or it is much easier to have routing congestions around macros. Furthermore, macro placement problems become more difficult because of preplaced macros. However, commercial tools cannot obtain acceptable results for macro placement, which still rely on experienced engineers to refine locations of macros. Therefore, this thesis adopts three-stage mixed size placement flow, which consists of: (1) placement prototyping, (2) macro placement, (3) standard-cell placement. Our research focuses on macro placement. In the beginning, we propose a placement blockage merger that can reduce the number of obstacles. Then, we group macros according to their hierarchies and the expansion of area of macros. Next, we redistribute macro groups by a recursive partition, where we can redistribute macro groups uniformly. Finally, we propose a macro legalizer based on corner stitching [26] to legalize macros in subregions, and refine macro legalization based on simulated evolution algorithm. We compare our method with the greedy algorithm [25]. Experimental results demonstrate our method can legalize macros efficiently, and can be better than the previous work.

[1]. Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: A new representation for non-slicing floorplans,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 458-463, 2000.
[2]. C. Chu, “FLUTE: Fast Lookup Table Based Wirelength Estimation Technique,” in Proceedings of International Conference on Computer Aided Design, pp. 696-701, 2004.
[3]. C. Chu and Y.-C. Wong, “Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” in Proceedings of International Symposium on Physical Design, pp. 28-35, 2005.
[4]. C. Chu and Y.-C. Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 1, pp.70-83, January 2008.
[5]. H.-C. Chen, Y.-L. Chung, Y.-W. Chang, and Y.-C. Chang, “Constraint graph-based macro placement for modern mixed-size circuit designs,” in Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pp. 218-223, 2008.
[6]. T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 1228-1240, July 2008.
[7]. T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, “MP-trees:A packing-based macro placement algorithm for modern mixed-size designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuit and Systems, vol. 27, no. 9, pp. 1621-1634, September 2008.
[8]. Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, “Routability-driven blockage-aware macro placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1-6, 2014.
[9]. M. R. Hestenes, E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards, vol. 49, no. 6, pp. 409-436, December 1952.
[10]. J. Hao and J. Orlin, “A faster algorithm for finding the minimum cut in a directed graph,” Journal of Research of National Bureau of Standards, vol. 17, no. 3, pp. 426-446, 1994.
[11]. P. -Y. Hsiao, J. K. -H. Li, and C.-C. Tsai, “A Sweeping Line Algorithm Based on Two Dimensional Region Search,” IEEE Computer and Communication Systems, vol. 2, pp. 496-500, 1990.
[12]. D. Hill, “Method and system for high speed detailed placement of cells within integrated circuit designs,” U.S.Patent 6370673, April 2002.
[13]. M.-K. Hsu, and Y.-W. Chang, “Unified analytical global placement for large-scale mixed-size circuit designs,” IEEE Thansactions on computer-Aided Design of Integrated Circuits and systems, vol. 31, no. 9, pp. 1366-1378, September 2012.
[14]. C.-W. Lin, S.-L. Huang, K.-C. Hsu, M.-X. Lee, and Y.-W. Chang, “Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spamming Graphs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, pp. 2007-2016, 2008.
[15]. S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[16]. A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Transactions Computer-Aided Design Integrated Circuits and Systems, vol. 24, no. 5, pp. 734–747, May 2005.
[17]. M.-C. Kim, D.-J. Lee, and I. L. Markov, “SimPL: An effective placement algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 1, pp. 50-60, January 2012.
[18]. M.-C. Kim, N. Viswanathan, C. J. Alpert, I. L. Markov, S. Ramji, “MAPLE: Multilevel Adaptive PLacEment for Mixed-Size Designs” in Proceedings of ACM international symposium on International Symposium on Physical Design, pp. 193-200, 2012.
[19]. J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng, and C.-K. Cheng. “ePlace: Electrostatics based placement using Nesterov’s method,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1-6, 2014.
[20]. M. D. Moffitt, A. N. Ng, I. L. Markov, and M. E. Pollack, “Constraint-driven floorplan repair,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1103-1108, 2006.
[21]. P. Spindler, U. Schlichtmann, and F. M. Johannes, “Abacus: Fast legalization of standard cell circuits with minimal movement,” in Proceedings of ACM International Symposium on Physical Design, pp. 47-53, 2008.
[22]. J. Z. Yan, N. Viswanathan, and C. Chu, “Handling complexities in modern large-scale mixed-size placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 436-441, 2009.
[23]. E. Wein and J. Benkoski, “Hard macros will revolutionize SoC design,”EE Times Online, August 2004.
[24]. J. Z. Yan and C. Chu, “DeFer: DeFered Decision Making Enable Fixed-outline Floorplanning Algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 3, pp. 119-130, 2010.
[25]. F. T. Chen, J. M. Lin, “A Macro Legalization Approach with Preplaced Blocks.”
[26]. J. K. Ousterhout, “Corner stitching: A data-structuring technique for VLSI layout tools,” IEEE Trans on CAD/ICAS, CAD-3, January, 1984.
[27]. C. H. Chiou, C. H. Chang, S. T. Chen, and Y. W. Chang.” Circular-contour based obstacle-aware macro placement,” In Proc. of ASPDAC, pages 172–177.IEEE, 2016.
[28]. C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. G. Villarrubia, ”A semi-persistent clustering technique for VLSI circuit placement,” in Proc. ISPD, pp. 200-207, 2005.
[29]. Y. L. Chuang, G. J. Nam, C. J. Alpert, Y. W. Chang, J. A. Roy, N. Viswanathan. “Design-hierarchy Aware Mixed-size Placement for Routability Optimization,” in Proc. ICCAD, pp 663 - 668, 2010.
[30]. C. H. Chang, Y. W Chang, and T. C. Chen “A Novel Damped-wave Framework for Macro Placement,” in Proc. ICCAD, pp. 504-511, 2017.
[31]. J. M. Lin, Y. W. Chang and S. P. Lin, “Corner Sequence - A Padmissible Floorplan Representation with a Worst Case Linear-time Packing Scheme.” IEEE VLSI, Vol. 11, pages 679–686, 2003.
[32]. Synopsys Inc. https://www.synopsys.com/company.html.
[33]. Himax Inc. http://www.himax.com.tw/zh/.
[34]. Cadence Inc. https://www.cadence.com/.