隨著半導體製程技術進步，現今的系統級單晶片(System-on-Chip)廣泛地使用矽智財電路(Intellectual Property)，其中包含類比模組、嵌入式記憶體、I/O連接埠等巨集電路。除此之外，晶片中還有許多預先擺置的模組(Preplaced macro)，使得晶片的形狀從原本的矩形變成了不規則形，大幅度提高混合尺寸電路擺置的複雜度。現有的文獻大多對於現代的混合型晶片並沒有有效的擺置。因此本篇論文針對這些問題，提出了一個新的模組擺置方法。我們所提出的巨集電路合法器同時優化了線長、可繞度，以及標準邏輯閘的擺置區域。我們提出了區域結構，它能描述模組周圍的情形，基於這個結構，我們可以有效地找到模組的合法化位置，且在之後的過程中能夠減少擺置後產生的浪費區域(Deadspace)，以優化標準邏輯閘擺置的區域面積。我們的實驗利用工業界的電路並且根據電子設計自動化軟體進行標準邏輯閘擺置和繞線，實驗結果證實，本論文提出的演算法接近實際業界的擺置結果。

Due to advance in manufacture technology, a modern SoC widely uses intellectual property (IP). Besides, there exist some macros which are preplaced at specified positions, which makes the placing problem more difficult. However, most of existing works may fail to obtain a legal placement for modern mixed-size designs. Therefore, we propose a macro legalizer which optimizes wirelength, routability, and standard-cell placement region. We propose a region structure that can describe the situation around the macro. Based on this structure, we can effectively find the legal location of the macro. Meanwhile, the area of the standard-cell placement region can also be optimized. Experimental results show our algorithm 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]. W.-H. Liu, W.-C. Kao, Y.-L. Li, and K.-Y. Chao, “NCTU-GR 2.0: Multithreaded collision-aware global routing with bounded-length maze routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 709-722, 2013.
[3]. W.-H. Liu, Y.-L. Li and C.-K. Koh, “A fast maze-free routing congestion estimator with hybrid unilateral monotonic routing,” in Proceedings of ACM/IEEE International Conference on Computer-Aided Design, pp. 713-719, 2012.
[4]. W.-H. Liu, C.-K. Koh, and Y.-L. Li, “Case study for placement solutions in ispd11 and dac12 routability-driven placement contests,” in Proceedings of ACM international symposium on International Symposium on Physical Design, pp. 114-119, 2013.
[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, pp. 1228-1240, 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, pp. 1621-1634, 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, pp. 409-436, 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, pp. 426-446, 1994.
[11]. C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, “Circular-contour-based obstacle-aware macro placement,” in Proceedings of Asia and South Pacific Design Automation Conference, pp. 172-177, 2016.
[12]. D. Hill, “Method and system for high speed detailed placement of cells within integrated circuit designs,” U.S.Patent 6370673, 2002.
[13]. M.-K. Hsu, and Y.-W. Chang, “Unified analytical global placement for large-scale mixed-size circuit designs,” IEEE Transactions on computer-Aided Design of Integrated Circuits and systems, pp. 1366-1378, 2012.
[14]. J.-M. Lin, Y.-W. Chang, and S.-P. Lin, “Corner sequence—a P-admissible floorplan representation with a worst case linear-time packing scheme,” IEEE Transactions on Very Large Scale Integration Systems, pp. 679-686, 2003.
[15]. M.-K. Hsu, Y.-F. Chen, C.-C. Huang, and Y.-W. Chang, “Routability-driven placement for hierarchical mixed-size circuit designs,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1-6, 2013.
[16]. A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Transactions Computer-Aided Design Integrated Circuits and Systems, pp. 734–747, 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, pp. 50-60, 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]. S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, “Optimization by simulated annealing,” Science , 1983.
[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, 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, pp. 119-130, 2010.
[25]. N. Viswanathan, C. Alpert, C. Sze, Z. Li, and Y. Wei, “ICCAD-2012 CAD contest in design hierarchy aware routability-driven placement and benchmark suite,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 345-348, 2012.
[26]. T.-W. Peng, F.-T. Chen, J.-M. Lin, “Puzzle: A fast obstacle-avoiding algorithm, for routability-aware macro placement,”
[27]. “An integrated-spreading-based macro-refining algorithm for large-scale mixed-size circuit designs,” in Proceedings of ACM/IEEE International Conference on Computer-Aided Design, 2017.