在現代超大型積體電路 (VLSI) 設計中，標準邏輯單元擺置仍然是一個關鍵的挑戰，尤其是考慮到可繞度時。擺置的繞線擁塞可能來自於全域繞線擁塞 (global routing congestion) 和局部繞線擁塞 (local routing congestion)。為了有效地解決這兩個繞線擁塞議題，本論文提出了一種基於數學分析擺置公式 (analytical placement formulation) 和多階層架構 (multilevel framework) 之以可繞度為導向的全局擺置演算法。為了消除全域繞線擁塞，本論文的方法將每個網絡視為一個可移動的模塊 (movable macro)，並且根據一種新穎的擁塞感知網絡懲罰模型估計每個網絡的擁塞懲罰，如果該網絡覆蓋了多個繞線擁塞區域，則會給予該網絡較大的懲罰。因此，可以在不顯著影響線長的情況下有效地將網絡從繞線擁塞的區域移開。此外，本論文提出了一種膨脹技術，可以根據叢集 (cluster) 內部連接強度和擁塞圖 (congestion map) 來擴展叢集的面積，以消除局部繞線擁塞。實驗結果表明，與目前先進的擺置演算法NTUplace4h和NTUplace4dr相比，本論文的方法可以獲得更好的可繞度及線長。

Cell placement remains a critical challenge in a modern VLSI design especially when routability is considered. Routing congestion of a placement may come from global routing congestion and local routing congestion. To effectively resolve these two issues, this thesis proposes a routability-driven global placement algorithm based on an analytical placement formulation and the multilevel framework.
To remove global routing congestion, our approach considers each net as a movable macro and gives a large penalty to the net if it covers more routing congested regions according to a novel congestion-aware net penalty model. Thus, nets can be moved away from routing congested regions effectively without affecting wirelength significantly. In addition, we propose an inflation technique to expand areas of clusters according to their internal connectivity intensities and a congestion map to remove local routing congestion. The experimental results demonstrate that our approaches can get better routability and wirelength compared to the state-of-art placement algorithms NTUplace4h and NTUplace4dr.

[1] Synopsys Inc. https://www.synopsys.com
[2] Cadence Inc. https://www.cadence.com
[3] Himax Inc. https://www.himax.com.tw
[4] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia, “A semi-persistent clustering technique for VLSI circuit placement,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 200--207, 2005.
[5] T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie, “mPL6: Enhanced multilevel mixed-Size placement,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 212--214, 2006.
[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 (TCAD), vol. 27, no. 7, pp. 1228--1240, 2008.
[7] C. Cheng, A. B. Kahng, I. Kang, and L. Wang, “RePlAce: Advancing solution quality and routability validation in global placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 38, no. 9, pp. 1717--1730, 2019.
[8] Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. Roy, and N. Viswanathan, “Design-hierarchy aware mixed-size placement for routability optimization,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2010.
[9] X. He, T. Huang, L. Xiao, H. Tian, G. Cui, and E. F. Y. Young, “Ripple: An effective routability-driven placer by iterative cell movement,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2011.
[10] X. He, Y. Wang, Y. Guo, and E. F. Y. Young, “Ripple 2.0: Improved movement of cells in routability-driven placement,” ACM Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 22, no. 1, 2016, Art. no. 10.
[11] 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 (TCAD), vol. 31, no. 9, pp. 1366--1378, 2012.
[12] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 33, no. 12, pp. 1914--1927, 2014.
[13] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 37, no. 3, pp. 669--681, 2018.
[14] 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 IEEE/ACM Design Automation Conference (DAC), 2008.
[15] A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 24, no. 5, pp. 734--747, 2005.
[16] A. B. Kahng and Q. Wang, “A faster implementation of APlace,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 218--220, 2006.
[17] G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” in Proc. of IEEE/ACM Design Automation Conference (DAC), 1999.
[18] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: applications in VLSI domain,” IEEE Transactions on Very Large Scale Integration Systems (TVLSI), vol. 7, no. 1, pp. 69--79, 1999.
[19] M.-C. Kim, J. Hu, D. J. Lee, and I. L. Markov, “A SimPLR method for routability-driven placement,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2011.
[20] M.-C. Kim and I. Markov, “ComPLx: A competitive primal-dual Lagrange optimization for global placement,” in Proc. of IEEE/ACM Design Automation Conference (DAC), 2012.
[21] M. Kuwano and Y. Takashima, “Stable-LSE based analytical placement with overlap removable length,” in Proc. of Synthesis And System Integration of Mixed Information technologies (SASIMI), 2010.
[22] T. Lin, C. Chu, J. R. Shinnerl, I. Bustany, and I. Nedelchev, “POLAR: Placement based on novel rough legalization and refinement,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2013.
[23] T. Lin and C. Chu, “POLAR 2.0: An effective routability-driven placer,” in Proc. of IEEE/ACM Design Automation Conference (DAC), 2014.
[24] 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 Transactions on Very Large Scale Integration Systems (TVLSI), vol. 27, no. 1, pp. 57--68, 2019.
[25] 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 IEEE/ACM Design Automation Conference (DAC), 2019.
[26] 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. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2019.
[27] J. Lu, P. Chen, C.-C. Chang, L. Sha, Dennis J.-H. Huang, C.-C. Teng, and C.-K. Cheng, “FFTPL: An analytic placement algorithm using fast Fourier transform for density equalization,” in Proc. of International Conference on ASIC (ASICON), 2013.
[28] J. Lu, P. Chen, C.-C. Chang, L. Sha, Dennis J.-H. Huang, C.-C. Teng, and C.-K. Cheng, “ePlace-MS: Electrostatics-based placement for mixed-size circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 34, no. 5, pp. 685--698, 2015.
[29] P. Spindler and F. M. Johannes, “Fast and accurate routing demand estimation for efficient routability-driven placement,” in Proc. of IEEE/ACM Design Automation and Test in Europe Conference (DATE), 2007.
[30] N. Viswanathan, M. Pan, and C. Chu, “FastPlace3.0: A fast multilevel quadratic placement algorithm with placement congestion control,” in Proc. of Asia and South Pacific Design Automation Conference (ASP-DAC), 2007.