請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/92624完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳中平 | zh_TW |
| dc.contributor.advisor | Charlie Chung-Ping Chen | en |
| dc.contributor.author | 連德宇 | zh_TW |
| dc.contributor.author | De-Yu Lian | en |
| dc.date.accessioned | 2024-05-14T16:07:33Z | - |
| dc.date.available | 2024-05-15 | - |
| dc.date.copyright | 2024-05-14 | - |
| dc.date.issued | 2024 | - |
| dc.date.submitted | 2024-04-25 | - |
| dc.identifier.citation | [1] P. R. Amestoy, T. A. Davis, and I. S. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4):886–905,1996.
[2] C.-P. Chen, C. C. Chu, and D. Wong. Fast and exact simultaneous gate and wire sizing by lagrangian relaxation. In Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, pages 617–624, 1998. [3] V. A. Chhabria and S. S. Sapatnekar. Openpdn: A neural-network-based framework for power delivery network synthesis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(10):3515–3528, 2022. [4] S. Chowdhury. Optimum design of reliable ic power networks having general graph topologies. In Proceedings of the 26th ACM/IEEE Design Automation Conference, pages 787–790, 1989. [5] S. Chowdhury and M. Breuer. Minimal area design of power/ground nets having graph topologies. IEEE Transactions on Circuits and Systems, 34(12):1441–1451, 1987. [6] S. Chowdhury and M. A. Breuer. Optimum design of ic power/ground nets subject to reliability constraints. IEEE transactions on computer-aided design of integrated circuits and systems, 7(7):787–796, 1988. [7] R. Dutta and M. Marek-Sadowska. Automatic sizing of power/ground (p/g) networks in vlsi. In Proceedings of the 26th ACM/IEEE Design Automation Conference, pages 783–786, 1989. [8] R. E. Griffith and R. Stewart. A nonlinear programming technique for the optimization of continuous processing systems. Management science, 7(4):379–392, 1961. [9] A. if known. Title of the article. Zhihu post, 2023. [10] G. S. P. Kadagala and V. A. Chhabria. The CAD Contest at ICCAD Problem C: Static IR Drop Estimation Using Machine Learning, 2023. [11] A. Mirhoseini, A. Goldie, M. Yazgan, J. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, S. Bae, et al. Chip placement with deep reinforcement learning. arXiv preprint arXiv:2004.10746, 2020. [12] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928–1937. PMLR, 2016. [13] L. W. Nagel and D. Pederson. Spice (simulation program with integrated circuit emphasis). Technical Report UCB/ERL M382, EECS Department, University of California, Berkeley, Apr 1973. [14] S. R. Nassif. Power grid analysis benchmarks. In 2008 Asia and South Pacific Design Automation Conference, pages 376–381, 2008. [15] E. C. Nwokorie, A. A. Elusoji, J. C. Odiketa, C. G. Onukwugha, and R. S. Babatunde. A review approach of power grid analysis in vlsi designs. 2013. [16] Quora. Can integrated circuits go below 1.8v operating voltage? what are the constraints that set the minimum operating voltage of ics?, 2024. [17] M. Roser, H. Ritchie, and E. Mathieu. What is moore’s law? Our World in Data, 2023. https://ourworldindata.org/moores-law. [18] X.-D. Tan and C.-J. Shi. Fast power/ground network optimization based on equivalent circuit modeling. In Proceedings of the 38th Design Automation Conference (IEEE Cat. No.01CH37232), pages 550–554, 2001. [19] X.-D. Tan, C.-J. R. Shi, D. Lungeanu, J.-C. Lee, and L.-P. Yuan. Reliability-constrained area optimization of vlsi power/ground networks via sequence of linear programmings. In Proceedings of the 36th annual ACM/IEEE Design Automation Conference, pages 78–83, 1999. [20] T.-Y. Wang and C.-P. Chen. Optimization of the power/ ground network wire-sizing and spacing based on sequential network simplex algorithm. In Proceedings International Symposium on Quality Electronic Design, pages 157–162, 2002. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/92624 | - |
| dc.description.abstract | 在先進製程的持續發展下，由於電壓持續下降，帶寬需求又持續上升，電路實體設計的演算法較過往更為困難，因此設計電源供應網絡(PDN)需要充分考慮線寬比、電壓降甚至是熱效應等多個面向，盡可能降低佔有面積來提供繞線更多空間。
本文分為兩部分，分析以及最佳化，分析部份開發基於節點分析法的 voltage drop simulator，在TSMC提供的電路樣本的實驗結果中表明，速度相較於golden tool Synopsys HSPICE在更少的記憶體使用的情況下，達到了39倍快，並將accuracy loss控制在零誤差，並且與IBM 基準測試相比，實現了223倍的加速。 最佳化部分與以往使用序列線性規劃迭代求解不同，本文基於數學規劃法，直接求解原始網絡問題。實驗結果顯示，我們的方法可以有效避免電壓降問題，並且在滿足可靠性約束條件下，優化電源供應網絡的面積。在超過一百萬分支的電源/接地網絡可以在幾分鐘內完成最佳化。 | zh_TW |
| dc.description.abstract | Under the continuous development of advanced processes, the algorithm for physical design has become more difficult due to the continuous reduction in voltage and the increasing demand for bandwidth. Therefore, the design of power delivery networks (PDN) needs to fully consider multiple aspects such as the width and length ratio, voltage drop, and even thermal effects to minimize the area and provide more space for routing.
This paper is divided into two parts: analysis and optimization. The analysis section develops a voltage drop simulator based on nodal analysis. Experimental results from circuit samples provided by TSMC indicate that, compared to the golden tool, Synopsys HSPICE, our simulator achieves 39 times speedup with less memory usage and maintains zero error, and achieves 223 times speedup with the IBM benchmark. The optimization part, unlike previous methods that employed iterative solutions with sequential linear programming, solves the original network problem directly through mathematical programming. The experimental results demonstrate that our method can effectively avoid voltage drop issues and optimize the area of the power supply network while satisfying reliability constraints. The optimization of power/ground networks with over one million branches can be completed within a few minutes. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2024-05-14T16:07:33Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2024-05-14T16:07:33Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i
Acknowledgements ii 摘要 iv Abstract v Contents vii List of Figures x List of Tables xii Chapter 1 Introduction 1 1.1 Background and Motivation . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Theory 6 2.1 SPICE Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Nodal Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Data Structures for Sparse Matrix . . . . . . . . . . . . . . . . . . . 14 2.3.1 Linked List (LL) based Format . . . . . . . . . . . . . . . . . . . . 14 2.3.2 Compressed Sparse Row (CSR) Format . . . . . . . . . . . . . . . 15 Chapter 3 Dataset 18 3.1 Benchmark Brief Description . . . . . . . . . . . . . . . . . . . . . 19 3.2 Modified IBM’s Power Grid Analysis Benchmarks . . . . . . . . . . 19 Chapter 4 Proposed Methods 21 4.1 Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2.1 An Approximate Minimum Degree Ordering . . . . . . . . . . . . . 24 4.2.2 Data Storage Format . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.1 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.2 Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Chapter 5 Experimental Results 34 5.1 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2 Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Chapter 6 Conclusion and Future Work 50 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.1 Dynamic Voltage Drop . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.2 GPU Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.3 Reinforcement Learning . . . . . . . . . . . . . . . . . . . . . . . 51 6.2.4 Lagrangian Relaxation . . . . . . . . . . . . . . . . . . . . . . . . 53 References 54 | - |
| dc.language.iso | en | - |
| dc.title | VLSI 電源供應網絡優化 | zh_TW |
| dc.title | VLSI Power Delivery Network Optimization | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 李建模;江介宏;Florin Dartu;張世良 | zh_TW |
| dc.contributor.oralexamcommittee | Chien-Mo Li;Jie-Hong Roland Jiang;Florin Dartu;Si-Liang Anthony Chang | en |
| dc.subject.keyword | 電源供應網絡,數學規劃法,最佳化,實體設計,電壓降, | zh_TW |
| dc.subject.keyword | Power Delivery Network(PDN),Mathematical Programming,Optimization,Physical Design,IR Drop, | en |
| dc.relation.page | 56 | - |
| dc.identifier.doi | 10.6342/NTU202400896 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2024-04-25 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電子工程學研究所 | - |
| dc.date.embargo-lift | 2029-05-13 | - |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-2.pdf 此日期後於網路公開 2029-05-13 | 16.35 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。