對於現今的積體電路(Integrated Circuits, ICs)而言，可繞度(Routability) 已然成為一個重要的議題。我們注意到晶片中標準元件(Standard Cells)的擺置(Placement)結果，對於晶片整體的可繞度有著舉足輕重的影響。在三維積體電路(3-Dimension ICs, 3D ICs)中，矽穿孔(Through-Silicon Vias, TSVs) 佔據標準元件擺置面積、消耗繞線資源的特性，使得三維積體電路中可繞度相關的議題變得更為複雜與重要。在本篇研究中，我們提出了以可繞度為導向並能考慮矽穿孔因素的三維積體電路全域擺置方法。儘管在此之前已有數篇關於三維積體電路擺置的研究被提出，然而卻沒有任何研究同時將可繞度與預擺置模塊(preplaced macro)納入考慮。再者，在先前研究中，由於其數學分析式方法對於標準元件所在層分析的不精確性，元件可能同時被分配到三維積體電路的多層之上，進而對擺置結果造成影響。為了更準確的預估晶片中的擺置密度與矽穿孔數量，我們提出了一個能精準預測元件所在層之數學模型並將之整合進數學分析式擺置方法中；另外，我們也使用了基於切分方格之方法來預測晶片中矽穿孔的位置，以利三維積體電路各層正確之繞線擁擠圖的建立。因此，我們的方法能根據當前擺置狀態動態的膨脹標準元件之擺置密度，以有效減少晶片的整體繞線擁擠程度。實驗結果顯示，我們所提出的方法相較於先前所提出之三維擺置方法而言，能夠在可繞度等方面得出更好的結果。

Routing congestion has become a critical issue for modern integrated circuits (ICs). We notice that the placement result of standard cells will significantly affect the routability of a chip. In 3D ICs, TSVs also occupy area for placing standard cells and require routing resources and thus, routability issue should be well concerned. This paper proposes a routability-driven TSV-aware 3D global placement methodology for large-scale designs. Although several researches about 3D placement have been proposed, there exists no work addressing routability and considering preplaced macros at the same time. Moreover, cells may be assigned to several tiers in their global placement stage due to an imprecise tier assignment model in an analytical placement formulation, which causes them to get worse placement result. To estimate correct placement utilization and TSV number, we propose a precise model to assign cells to exact tiers and integrate it into the analytical formulation. More importantly, a bin based approach is used to predict the locations of TSVs so that correct routing congestion maps can be constructed. Hence, our approach can inflate cells dynamically according to a placement result to further reduce routing congestion. Experimental results show that our methodology can obtain better results than previous works.

[1] P. Batude et al., “Demonstration of low temperature 3D sequential FDSOI integration down to 50 nm gate length,” 2011 Symposium on VLSI Technology – Digest of Technical Papers, pp. 158-159, 2011.
[2] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Yao-Wen Chang, “NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints,” IEEE TCAD, vol. 27, no. 7, pp. 1228-1240, July 2008.
[3] C. Cheng, A. B. Kahng, I. Kang, and L. Wang, “RePlAce: advancing solution quality and routability validation in global placement,” IEEE TCAD, vol. 38, no. 9, pp. 1717-1730, Sept. 2019.
[4] J. Cong and G. Luo, “A multilevel analytical placement for 3D ICs,” in Proc. ASP-DAC, pp. 361-366, Feb. 2009.
[5] J. Cong and G. Luo. “An analytical placer for mixed-size 3D placement,”in Proc. of ISPD, pp. 61-66, March 2010.
[6] B. Goplen and S. Sapatnekar, ”Placement of 3D ICs with thermal and interlayer via considerations,” in Proc. of DAC, pp. 626-631, June 2007.
[7] X. He, Y. Wang, Y. Guo, and E. F. Y. Young, “Ripple 2.0: improved movement of cells in routability-driven placement,” IEEE TCAD, vol. 22, no. 10, pp. 1-26, Dec. 2016.
[8] M. Hsu, V. Balabanov and Y. Chang,“TSV-aware analytical placement for 3-D IC designs based on a novel weighted-average wirelength model,” IEEE TCAD, vol. 32, no. 4, pp. 497-509, April 2013.
[9] M.-K. Hsu, Y.-F. Chen, C.-C. Huang, S. Chou, T.-H. Lin, T.-C. Chen, and Y.-W. Chang, “NTUplace4h: a novel routability-driven placement algorithm for hierarchical mixed-size circuit designs,” IEEE TCAD, vol. 33, no. 12, pp. 1914-1927, Dec. 2014.
[10] C.-C. Huang, H.-Y. Lee, B.-Q. Lin, S.-W. Yang, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, “NTUplace4dr: a detailed-routing-driven placer for mixed-size circuit designs with technology and region constraints,” IEEE TCAD, vol. 37, no. 3, pp. 669-681, March 2018.
[11] Z.-W. Jiang, B.-Y. Su, and Y.-W. Chang, “Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs,” in Proc. of DAC, pp. 167-172, July 2008.
[12] A.B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer” IEEE TCAD, vol. 24, no. 5, pp. 734-747, May 2005.
[13] G. Karypis and V. Kumar, “hMETIS, a hypergraph partitioning package version 1.5.3, ”http://glaros.dtc.umn.edu/gkhome/metis/hmetis/download
[14] M.-C. Kim, J. Hu, D. J. Lee, and I. L. Markov, “A SimPLR method for routability driven placement,” in Proc. of ICCAD, pp. 67-73, Dec. 2011.
[15] 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. of DAC, pp. 1-6, Aug. 2019.
[16] T. Lin and C. Chu, “POLAR 2.0: an effective routability-driven placer,”in Proc. of DAC, pp. 1-6, Aug. 2014.
[17] J. Lu et al., “ePlace-3D: electrostatics based placement for 3D-ICs,” in Proc. of ISPD, pp. 11-18, April 2016.
[18] T. Lu, Z. Yang and A. Srivastava, “Electromigration-aware placement for 3D-ICs” in Proc. of ISQED, pp. 35-40, May 2016.
[19] G. Luo, Y. Shi and J. Cong, “An analytical placement framework for 3-D ICs and its extension on thermal awareness,” IEEE TCAD, vol. 32, no. 4, pp. 510-523, April 2013.
[20] Heechun Park, Bon Woong Ku, Kyungwook Chang, Da Eun Shim, and Sung Kyu Lim. “Pseudo-3D approaches for commercial-grade RTL to-GDS tool flow targeting monolithic 3D ICs,” in Proc. of ISPD, pp. 47-54, March 2020.
[21] N. Sillon, A. Astier, H. Boutry, L. Di Cioccio, D. Henry and P. Leduc, “Enabling technologies for 3D integration: From packaging miniaturization to advanced stacked ICs,” IEEE IEDM, pp. 1-4, Dec. 2008.
[22] P. Spindler and F. M. Johannes, “Fast and accurate routing demand estimation for efficient routability-driven placement,” in Proc. of DATE, pp. 1-6, May 2007.
[23] Synopsys. IC Compiler. https://www.synopsys.com.
[24] S. S. Wong and A. E. Gamal,“The prospect of 3D-IC,” in Proc. of CICC, pp. 445-448, Sept. 2009.