儘管現有的全局擺置 (global placement) 演算法採用了不同的方法來優化線長和可繞度，但其結果仍有很大的改進空間。典型的設計流程通常於細部擺置 (detailed placement) 階段來優化擺置結果。由於合法化 (legalization) 會直接受到全局擺置的影響，本篇論文提出了在全局擺置階段後優化擺置。此外，隨著多行高度邏輯閘 (multi-row height cell) 數量的增加，細部擺置的優化變得更加的困難，因為在找到合法化的位置之前，邏輯閘可能會被推遠離其原始位置。我們在本篇論文中提出了兩個優化程序。第一個是線長感知邏輯閘重新安排方法，此方法將迭代的移動邏輯閘至更好的位置，而不會增加任何網絡 (net) 的線長。此外，為了獲得更多的線長減少，我們找到一個更好的移動邏輯閘順序。第二個是空白空間重新分配方法，此方法根據繞線溢出將空白空間分配至區域之中。為了確保可以將空白空間分配至繞線擁擠嚴重區域，我們根據乙狀 (sigmoid) 函數，基於區域的擁擠程度以及腳位 (pin) 密度增大其繞線需求。實驗的結果表明，和其它方法相比，我們提出的方法在工業設計上能獲得更少的線長以及更佳的可繞度。

Although existing global placement algorithms apply different methods to optimize wirelength and routability, it still has a large space to improve their results. Classic design flow usually optimizes placement results in the detailed placement stage. Because legalization is directed impacted by global placement results, this thesis proposes to optimize placement after the global placement stage. Moreover, as the number of multi-row height cells increases, optimization in the detailed placement becomes more difficult since cells may be pushed far away from their original locations before legal locations can be found.
We have proposed two optimization procedures in this thesis. The first one is a wirelength-aware cell re-arrangement method, which iteratively moves a cell to a better location without increasing wirelength for any net. Furthermore, to gain a larger wirelength reduction, we find a better ordering to move cells. The second one is a whitespace re-allocation approach, which allocates whitespace into regions according to their routing overflows. To ensure that whitespace will be allocated to a serious routing congestion region, we enlarge the routing demand of the region based on its congestion level and pin density according to a sigmoid function. The experimental results show that our proposed method obtains less wirelength and better routability in industrial designs compared to other works.

[1] Synopsys Inc. https://www.synopsys.com
[2] Himax Inc. https://www.himax.com.tw
[3] 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.
[4] W.-K. Chow, C.-W. Pui, E. F. Y. Young, “Legalization algorithm for multiple-row height standard cell design, ” in Proc. of IEEE/ACM Design Automation Conference (DAC), pp. 1-6 , 2016.
[5] 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.
[6] 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.
[7] K. -R. Dai, C. -H. Lu and Y. -L. Li, “GRPlacer: Improving routability and wire-length of global routing with circuit replacement,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 351-356, 2009.
[8] 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.
[9] 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.
[10] J.-M. Lin, C.-W. Huang, L.-C. Zane, M.-C. Tsai, C.-L. Lin, C.-F. Tsai, “Routability-driven Global Placer Target on Removing Global and Local Congestion for VLSI Designs, '' to be appeared in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2021.
[11] W. -H. Liu, C. -K. Koh and Y. -L. Li, “Optimization of placement solutions for routability, ” in Proc. of IEEE/ACM Design Automation Conference (DAC), pp. 1-9, 2013.
[12] C. Li, M. Xie, C. K. Koh, J. Cong and P. Madden, “Routability-driven placement and white space allocation, ” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 26, no. 5, pp. 858--871, 2007.
[13] M. Pan, N. Viswanathan and C. Chu, “An efficient and effective detailed placement algorithm, ” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 48-55, 2005.
[14] M. Pan and C. Chu, “IPR: An Integrated Placement and Routing Algorithm, ” in Proc. of IEEE/ACM Design Automation Conference (DAC), pp. 59-62, 2007.
[15] X. Yang, B. -K. Choi and M. Sarrafzadeh, “Routability-driven white space allocation for fixed-die standard-cell placement, ” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 22, no. 4, pp. 410-419, 2003.
[16] Y. Zhang and C. Chu, ``CROP: Fast and effective congestion refinement of placement,'' in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 344-350, 2009.