在先進半導體製程中，佈局特徵的急劇縮小對電路延遲和電子遷移（EM）現象產生了重大影響。近來，網狀式堆導通孔（MSV）被提出作為改善電路時序和信號完整性的解決方案，每個MSV都是由平行金屬線和導通孔組成的多層網狀結構。 由於引入了MSV設計規則以及越來越複雜的佈局規則，MSV設計成為一個非常具有挑戰性的問題，而以前的研究都沒有解決這個問題。在本文中，我們是目前第一篇提出MSV設計的研究，並且有兩種設計方法：基於整數線性規劃（ILP）的方法和基於動態規劃（DP）的方法。 與大多數以前致力於為每個複雜的佈局規則制定約束的工作不同，我們提出了一種自動限制生成（ACG）架構來迭代解決佈局規則違規（DRV），而無需費力地理解所有佈局規則，從而為MSV設計做出了貢獻，並且可適用於不同的技術節點。實驗結果表明，對於業界測資，基於ILP的方法和基於DP的方法平均可以實現92％的MSV插入率。 此外，通過採用本篇提出的ACG架構搭配前面兩個方法，皆可以實現100％MSV插入率，而不會引起任何DRV。

In advanced semiconductor processes, the dramatic shrink of layout features has made a significant impact on circuit delay and electromigration (EM). Recently, meshed stack vias (MSVs) have been proposed as a solution to improve circuit timing and signal integrity, each of which is a multi-layer mesh structure composed of parallel metal shapes and vias. Due to the introduced MSV rules and more and more complicated design rules, MSV design becomes a very challenging problem, while no previous work has addressed this issue.
In this thesis, we propose the first work of MSV design by developing two different methods: an integer linear programming (ILP)-based and a dynamic programming (DP)-based methods.
Unlike most previous works devoting themselves to formulating sophisticated constraints for each complicated design rule, we propose an automatic constraint generation (ACG) framework to iteratively resolve design rule violations (DRVs) without any effort in understanding all design rules, which contributes to a general MSV design methodology applicable to different technology nodes.
Experimental results show that both the ILP-based and DP-based approaches can averagely achieve 92% MSV insertion rate for a set of industrial benchmarks. In addition, by adopting the proposed ACG framework, 100% MSV insertion rate can be achieved without causing any DRV.

[1] IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[2] L. C. Lu, "Physical Design Challenges and Innovations to Meet Power, Speed, and Area Scaling Trend," in Proceedings of International Symposium of Physical Design, pp. 63-63, 2017.
[3] Y. Zhong, T.C. Yu, K.C. Yang, S.Y. Fang, "Via Pillar-aware Detailed Placement,"
in Proceedings of International Symposium of Physical Design, pp. 17-24, 2020.
[4] W. H. Liu, S. Mantik, W. K. Chow, Y. Ding, A. Farshidi and G. Posser, "ISPD 2019 Initial Detailed Routing Contest and Benchmark with Advanced Routing Rules," in Proceedings of International Symposium of Physical Design, pp. 147-151, 2019.
[5] F. K. Sun, H. Chen, C.Y. Chen, C.H. Hsu and Y.W. Chang, "A Multithreaded Initial Detailed Routing Algorithm Considering Global Routing Guides," in Proceedings of International Conference on Computer-Aided Design, pp. 1-7, 2018.
[6] G. Chen, C.W. Pui, H. Li, J. Chen, B. Jiang and E. F. Young, "Detailed Routing by Sparse Grid Graph and Minimum-Area-Captured Path Search," in Proceedings of Asia and South Pacic Design Automation Conference, pp. 754-760, 2019.
[7] M. Ahrens, M. Gester, N. Klewinghaus, D. Muller, S. Peyer, C. Schulte, and G. Tellez, "Detailed routing algorithms for advanced technology nodes," IEEE Transactions on Computer-Aided Design and Integrated Circuits Systems, vol. 34, no. 4, pp. 563-576, 2015.
[8] K. Han, A. Kahng, and H. KhooAn, "Evaluation of BEOL Design Rule Impacts Using An Optimal ILP-based Detailed Router," in Proceedings of Design Automation Conference, pp. 1-6, 2015.
[9] X. Jia, Y. Cai, Q. Zhou, and B. Yu, "A Multicommodity Flow-Based Detailed Router With Ecient Acceleration Techniques," IEEE Transactions on Computer-Aided Design and Integrated Circuits Systems, vol. 37, no. 1, pp. 217-230, 2017.
[10] X. Jia, Y. Cai, Q. Zhou, G. Chen, Z. Li and Z. Li "MCFRoute: A Detailed Router Based on Multi-Commodity Flow Method," in Proceedings of International Conference on Computer-Aided Design, pp. 397-404, 2014.
[11] I. Kang, C. Han, D. Park and C.K. Cheng "Fast and Precise Routability analysis with Conditional Design Rules," in Proceedings of International Workshop on System Level Interconnect Prediction, pp. 4, 2018.
[12] H. Li, G. Chen, B. Jiang, J. Chen and E. F. Young, "Dr. CU 2.0: A Scalable Detailed Routing Framework with Correct-by-Construction Design Rule Satisfaction," in IEEE/ACM International Conference on Computer-Aided Design, pp. 1-7, 2019.
[13] Y. Zhang and C. Chu, "RegularRoute: An ecient detailed router applying regular routing patterns," in IEEE transactions on very large scale integration (VLSI) systems, pp. 1655-1668, 2012.