隨著製程技術進步，現今的系統級單晶片(System-on-Chip)使用越來越多的矽智財電路(Intellectual Property)，包含類比模組、嵌入式記憶體、I/O連接埠。除此之外，晶片中還有許多預先擺置的模組(Preplaced macro)，其中甚至包含非貼齊晶片周圍的模組(Floating preplaced macros)。使得晶片的形狀從原本的矩形變成了不規則形，大幅度提高混合尺寸電路擺置的複雜度。過去的文獻針對混合型晶片模組擺置並沒有有效處理非貼齊周圍的模組的方法，且效率不高。因此本篇論文針對這些問題，提出解決的方法。為了能夠找出有效的擺置區域，首先將擺置障礙物合併，再根據區域擁擠度調整模組面積，接著利用遞迴切割的方式將模塊散布到晶片並且依此建立子區域，最後，針對子區域的模組合法化提出利用角落點搜尋的方式，找到模組的合法化位置，且在此過程中能夠減少擺置後產生的浪費空間(Deadspace)，以優化標準邏輯閘擺置的區域面積。我們的實驗利用工業界的電路並且根據電子設計自動化軟體進行標準邏輯閘擺置和繞線，實驗結果證實，本論文提出的演算法不但能夠快速且有效的決定模組位置，且能接近實際業界的擺置結果。

Due to advance in manufacture technology, a modern SoC usually contains hundreds of macros. Besides, there exist some macros which are preplaced at specified positions, which makes the problem more difficult. There exists limited woks which can handle macro placement with the preplaced macros. But, none of these works are able to handle floating preplaced macros. Therefore, this thesis proposes a fast macro placer which can handle floating preplaced macros. We merge placement blockages to reduce placement complexity, and adjust each macro’s area according to region congestion to consider routability. Furthermore, a partition based approach is used to further spread movable macros, which also divides a placement region into several sub-regions. Finally we propose a macro legalizer based on a corner point search algorithm to find a legalization solution in each sub-region. Wirelength, displacement and deadspace are considered during the procedure. We compare our method with CP-tree and manual macro placement results in the experiment. Experimental results show our algorithm can find feasible solutions without spending a lot of time, and can be closed to the actual result placement.

[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 pre-placed 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.