本論文提出了一種利用移除一群巨集來避免產生破碎擺置空間的新穎巨集擺置細化(refinement)方法。同時也提出了巨集群(macro island)的概念，而每個巨集群可以藉由集合(set)的資料結構來記錄。此外，為了避免在細化階段產生破碎的擺置空間，使用了參考點(reference point)與巨集群來移除巨集，其中，參考點是由每個分割區域(partition region)中空白的幾何中心來決定的，而為了避免產生浮空(floating)的巨集，會在某些情況下調整參考點的位置。我們還將巨集群劃分成不同的類型(type)，並且根據類型的不同使用不同的擺置策略將巨集擺放回巨集群，以便巨集的擺放結果更加規則。我們還提出了基於歷史成本(historical cost)的繞線擁擠成本函數，來避免重複將巨集擺放回繞線擁擠的區域。最後，為了將那些電線具有高度連結(high-degree nets)的巨集移動到靠近晶片中心的位置，我們使用二分匹配(bipartite matching)演算法來交換巨集位置。實驗結果顯示，我們的方法可以獲得比其他巨集擺置器更好的結果。

This paper proposes an effective three-stage macro placement algorithm to improve routability. Our approach includes macro legalization, macro refinement, macro optimization stages. In order to avoid generating fragmented space, our macro legalization regards those macros placed in the contiguous locations as macro islands and rip up a set of macros in each macro island according to a reference point and a macro in the macro island in the macro refinement stage. Furthermore, we classify macro islands into different types and apply various strategies to re-place macros back to a macro island so that macros can be placed more regularly. Finally, to avoid repeatedly placing macros back to routing congested regions, we propose a history-based congestion cost function to give severe penalty if macros are placed into the routing congestion regions. The experimental results show that our methodology can obtain better results than the other macro placers.

[1] Himax Technologies, Inc. About Himax. Accessed: October 5, 2021. [Online]. Available: https://www.himax.com.tw/company/about-himax/
[2] Synopsys. Inc. IC Compiler Accessed: October 5, 2021. [Online]. Available: https://www.synopsys.com/implementation-and-signoff/physical-implementation/ic-compiler.html
[3] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia, “A semi-persistent clustering technique for VLSI circuit placement,” in Proc. ISPD, pp. 200-207, 2005.
[4] 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.
[5] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and T.-W. Chang, “NTUplace3: An analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE Trans. of TCAD, vol. 27, no. 7, pp. 1228-1240, 2008.
[6] 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 mixedsize designs,” IEEE Trans. of TCAD, vol. 27, no. 9, pp. 1621-1634, 2008.
[7] Y.-F. Chem. C.-C. Huang, C.-H Chiou, Y.-W. Chang, and C.-J. Wang, “Routability-driven blockage-aware macro placement,” in Proc. DAC, 2014, pp. 1-6.
[8] C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, “Circular-contour-based obstacle-aware macro placement,” in Proc. ASP-DAC, 2016, pp. 172-177.
[9] K.-R. Dai, W.-H. Liu, and Y.-L. Li, “NCTU-GR: Efficient simulated evolution-based rerouting and congestion-relaxed layer assignment on 3-D global routing,” IEEE Trans. of TVLSI, vol. 20, no. 3, pp. 459-472, 2012.
[10] 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 Trans. of TVLSI, vol. 11, no. 4, pp. 679-686, 2003.
[11] J.-M. Lin, Y.-L. Deng, S.-T. Li, B.-H. Yu, L.-Y. Chang, and T.-W. Peng, “Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles,” IEEE Trans. of TVLSI, vol. 27, no. 1, pp. 57-68, 2019.
[12] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen, and Y.-C. Chen, “A Novel Macro Placement Approach based on Simulated Evolution Algorithm,” in Proc. ICCAD, pp. 1-7, 2019.
[13] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen and P.-C. Lu, “Dataflow-Aware Macro Placement Based on Simulated Evolution Algorithm for Mixed-Size Designs,” IEEE Trans. of TVLSI, vol. 29, no. 5, pp. 973- 984, 2021.
[14] J.-M. Lin, S.-T. Li, and Y.-T. Wang, “Routability-driven Mixed-size Placement Prototyping Approach Considering Design Hierarchy and Indirect Connectivity Between Macros,” in Proc. DAC, pp. 1-6, 2019.
[15] J. K. Ousterhout, “Corner stitching: A data-structuring technique for VLSI layout tools,” IEEE Trans. of TLVSI, vol. 3, no. 1, pp. 87-100, 1984.
[16] A. Vidal-Obiols, J. Cortadella, J. Petit, M. Galceran-Oms, and F. Martorell, “RTL-aware dataflow-driven macro placement,” in Proc. DATE, pp. 186-191, 2019.
[17] M.-C. Wu and Y.-W. Chang, “Placement with alignment and performance constraints using the B*-tree representation,” in Proc. ICCD, pp. 568-571, 2004.