請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/99251完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張耀文 | zh_TW |
| dc.contributor.advisor | Yao-Wen Chang | en |
| dc.contributor.author | 吳宗翰 | zh_TW |
| dc.contributor.author | Zong-Han Wu | en |
| dc.date.accessioned | 2025-08-21T16:59:29Z | - |
| dc.date.available | 2025-08-22 | - |
| dc.date.copyright | 2025-08-21 | - |
| dc.date.issued | 2025 | - |
| dc.date.submitted | 2025-08-05 | - |
| dc.identifier.citation | [1] L. Amar`u, P.-E. Gaillardon, and G. De Micheli, “The EPFL Combinational Benchmark Suite,” in Proceedings of International Workshop on Logic and Synthesis, pp. 171–178, Zurich, June 2015.
[2] Z.-Z. Bai, “Modulus-Based Matrix Splitting Iteration Methods for Linear Complementarity Problems,” Numerical Linear Algebra with Applications, vol. 17, no. 6, pp. 917–933, 2010. [3] G. Chen, Z. Zeng, B. Zhu, J. Li, K. Wang, J. Yu, and J. Chen, “Mixed-cell-height Placement with Minimum-Implant-Area and Drain-to-Drain Abutment Constraints,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, San Francisco, CA, July 2023. [4] J. Chen, Z. Huang, Y. Huang, W. Zhu, J. Yu, and Y.-W. Chang, “An Efficient EPIST Algorithm for Global Placement with Non-Integer Multiple-Height Cells,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, San Francisco, CA, July 2020. [5] J. Chen, P. Yang, X. Li, W. Zhu, and Y.-W. Chang, “Mixed-Cell-Height Placement with Complex Minimum-Implant-Area Constraints,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–8, San Diego, CA, November 2018. [6] J. Chen, Z. Zhu, Q. Liu, Y. Zhang, W. Zhu, and Y.-W. Chang, “Hamiltonian Path Based Mixed-Cell-Height Legalization for Neighbor Diffusion Effect Mitigation,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, San Francisco, CA, July 2020. [7] J. Chen, Z. Zhu, W. Zhu, and Y.-W. Chang, “Toward Optimal Legalization for Mixed-Cell-Height Circuit Designs,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, Austin, TX, June 2017. [8] J. Chen, Z. Zhu, W. Zhu, and C. Yao-Wen, “A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization,” ACM Transactions on Design Automation of Electronic Systems, vol. 26, no. 2, 2020. [9] K.-Y. Chen, H.-C. Hsu, W.-K. Mak, and T.-C. Wang, “HybridGP: Global Placement for Hybrid-Row-Height Designs,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 294–299, Taipei, Taiwan, January 2022. [10] W.-K. Chow, C.-W. Pui, and E. F. Y. Young, “Legalization Algorithm for Multiple-Row Height Standard Cell Design,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, Austin, TX, June 2016. [11] S. A. Dobre, A. B. Kahng, and J. Li, “Design Implementation with Noninteger Multiple-Height Cells for Improved Design Quality in Advanced Nodes,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 4, pp. 855–868, 2019. [12] C. Han, A. B. Kahng, L. Wang, and B. Xu, “Enhanced Optimal Multi-Row Detailed Placement for Neighbor Diffusion Effect Mitigation in Sub-10 nm VLSI,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 9, pp. 1703–1716, 2019. [13] M. Hatamian and P. Penzes, “Non-integer Height Standard Cell Library,” U.S. Patent 8 788 998, 2014. [14] D. Hill, “Method and System for High Speed Detailed Placement of Cells within an Integrated Circuit Design,” U.S. Patent 6 370 673, 2002. [15] C.-Y. Huang and W.-K. Mak, “Row Planning and Placement for Hybrid-Row-Height Designs,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 306–311, Incheon, January 2024. [16] D.-W. Huang, Y.-J. Jiang, and S.-Y. Fang, “Spacing Cost-aware Optimal and Efficient Mixed-Cell-Height Detailed Placement for DFM Considerations,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–8, San Francisco, CA, November 2023. [17] T.-P. Huang and S.-Y. Fang, “Practical Mixed-Cell-Height Legalization Considering Vertical Cell Abutment Constraint,” in Proceedings of ACM International Symposium on Physical Design, pp. 151–159, New York, NY, March 2024. [18] T.-W. Huang and M. D. F. Wong, “OpenTimer: A High-Performance Timing Analysis Tool,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 895–902, Austin, TX, November 2015. [19] H. Li, W.-K. Chow, G. Chen, E. F. Y. Young, and B. Yu, “Routability-Driven and Fence-Aware Legalization for Mixed-Cell-Height Circuits,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, San Francisco, CA, June 2018. [20] H. Li, W.-K. Chow, G. Chen, B. Yu, and E. F. Young, “Pin-Accessible Legalization for Mixed-Cell-Height Circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 1, pp. 143–154, 2022. [21] X. Li, J. Chen, W. Zhu, and Y.-W. Chang, “Analytical Mixed-Cell-Height Legalization Considering Average and Maximum Movement Minimization,” in Proceedings of ACM International Symposium on Physical Design, pp. 27–34, New York, NY, April 2019. [22] Y. Lin, B. Yu, X. Xu, J.-R. Gao, N. Viswanathan, W.-H. Liu, Z. Li, C. J. Alpert, and D. Z. Pan, “MrDP: Multiple-Row Detailed Placement of Heterogeneous-Sized Cells for Advanced Nodes,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–8, Austin, TX, November 2016. [23] Z.-Y. Lin and Y.-W. Chang, “A Row-Based Algorithm for Non-Integer Multiple-Cell-Height Placement,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–6, Munich, November 2021. [24] J. Mai, C. Zhao, Z. Zhang, Z. Di, Y. Lin, R. Wang, and R. Huang, “LEGALM: Efficient Legalization for Mixed-Cell-Height Circuits with Linearized Augmented Lagrangian Method,” in Proceedings of ACM International Symposium on Physical Design, pp. 22–30, New York, NY, March 2025. [25] M. Martins, J. M. Matos, R. P. Ribas, A. Reis, G. Schlinker, L. Rech, and J. Michelsen, “Open Cell Library in 15nm FreePDK Technology,” in Proceedings of ACM International Symposium on Physical Design, pp. 171–178, Monterey, CA, March/April 2015. [26] Y. Pu, F. Liu, Y. Zhang, Z. He, Y. Lin, K.-Y. Chao, and B. Yu, “Lesyn: Placement-aware Logic Resynthesis for Non-Integer Multiple-Cell-Height Designs,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–6, San Francisco, CA, June 2024. [27] M. Soeken, H. Riener, W. Haaswijk, E. Testa, B. Schmitt, G. Meuli, F. Mozafari, S.-Y. Lee, A. T. Calvino, D. S. Marakkalage, and G. D. Micheli, “The EPFL Logic Synthesis Libraries,” 2022. [Online]. Available: https://arxiv.org/abs/1805.05121 [28] P. Spindler, U. Schlichtmann, and F. M. Johannes, “Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement,” in Proceedings of ACM International Symposium on Physical Design, pp. 47–53, New York, NY, April 2008. [29] Y.-W. Tseng and Y.-W. Chang, “Mixed-Cell-Height Placement Considering Drain-to-Drain Abutment,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–6, San Diego, CA, November 2018. [30] C.-H. Wang, Y.-Y. Wu, J. Chen, Y.-W. Chang, S.-Y. Kuo, W. Zhu, and G. Fan, “An Effective Legalization Algorithm for Mixed-Cell-Height Standard Cells,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 450–455, Chiba, Japan, January 2017. [31] Y. Wen, B. Zhu, Z. Lin, and J. Chen, “Effective Analytical Placement for Advanced Hybrid-Row-Height Circuit Designs,” in Proceedings of IEEE/ACM Asia and South Pacific Design Automation Conference, pp. 300–305, Incheon, Korea, January 2024. [32] C.-H. Wu, W.-K. Mak, and C. Chu, “Linear-time Mixed-Cell-Height Legalization for Minimizing Maximum Displacement,” in Proceedings of ACM International Symposium on Physical Design, pp. 211–218, New York, NY, March 2022. [33] S.-Y. Wu, C. Chang, M. Chiang, C. Lin, J. Liaw, J. Cheng, J. Yeh, H. Chen, S. Chang, K. Lai, M. Liang, K. Pan, J. Chen, V. Chang, T. Luo, X. Wang, Y. Mor, C. Lin, S. Wang, M. Hsieh, C. Chen, B. Wu, C. Lin, C. Liang, C. Tsao, C. Li, C. Chen, C. Hsieh, H. Liu, P. Chen, C. Chen, R. Chen, Y. Yeo, C. Chui, W. Chang, T. Lee, K. Huang, H. Lin, K. Chen, M. Tsai, K. Chen, X. Chen, Y. Cheng, C. Wang, W. Shue, Y. Ku, S. M. Jang, M. Cao, L. Lu, and T. Chang, “A 3nm CMOS FinFlex™ Platform Technology with Enhanced Power Efficiency and Performance for Mobile SoC and High Performance Computing Applications,” in Proceedings of IEEE International Electron Devices Meeting, pp. 27.5.1–27.5.4, San Francisco, CA, December 2022. [34] Y.-Y. Wu and Y.-W. Chang, “Mixed-Cell-Height Detailed Placement Considering Complex Minimum-Implant-Area Constraints,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 65–72, Irvine, CA, November 2017. [35] Y. Zhang, Y. Pu, F. Liu, P. Liao, K.-Y. Chao, K. Zhu, Y. Lin, and B. Yu, “Multi-Electrostatics Based Placement for Non-Integer Multiple-Height Cells,” in Proceedings of ACM International Symposium on Physical Design, pp. 1–8, Taipei, March 2024. [36] C. Zhou, Y. Cao, Q. Shi, L. Wang, and X. Wen, “A Robust Newton Iteration Method for Mixed-Cell-Height Circuit Legalization Under Technology and Region Constraints,” ACM Transactions on Design Automation of Electronic Systems, vol. 29, no. 6, pp. 1–25, 2024. [37] B. Zhu, Z. Zeng, and J. Chen, “Late Breaking Results: Mixed-Cell-Height Detailed Placement under Multi-Cell Spacing Constraints,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1–2, San Francisco, CA, June 2024. [38] Z. Zhu, X. Li, Y. Chen, J. Chen, W. Zhu, and Y.-W. Chang, “Mixed-Cell-Height Legalization Considering Technology and Region Constraints,” in Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 1–8, San Diego, CA, November 2018. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/99251 | - |
| dc.description.abstract | 當前超大型積體電路 (very-large scale integration, VLSI) 快速提升的複雜度，以及包含非整數倍數高度（non-integer multiple-cell-height, NIMCH）之標準元件的設計，對時序感知電路節點重映射 (remapping) 帶來新的挑戰。現有的重映射流程在處理所有電路節點與邏輯閘對應組合時需進行全面列舉，並依賴序列式動態規劃 (dynamic programming) 演算法，導致運算開銷龐大。為了解決上述效率問題，我們提出一種創新的考慮非整數倍數高度之標準元件 (standard cell) 之電路節點重映射演算法，包含以下兩項策略：平行化最長路徑優先策略以及迭代最小時序裕量 (slack) 優先策略。這兩種策略皆優先處理時序關鍵電路節點，以加速整體流程。其中，最長路徑優先策略允許平行運算，顯著提升重映射速度。實驗結果顯示，與現有最先進方法相比，我們的方法平均可達到 8.92 倍的執行速度提升，同時維持相同的布局品質。本流程的效率與可擴展性大幅提升，使其非常適合應用於需快速達成時序收斂的大規模實體設計中。 | zh_TW |
| dc.description.abstract | The fast-growing complexity of VLSI circuits with non-integer multiple-cell-height (NIMCH) standard cells poses new challenges for timing-aware node remapping. The existing remapping flow suffers from significant computational overhead due to exhaustive enumeration of all node-to-gate mapping combinations and the sequential dynamic programming algorithm. To remedy this inefficiency, we propose a novel NIMCH node remapping flow consisting of the following two schemes: a parallel longest-path-first scheme and an iterative minimum-slack-first scheme. Both schemes prioritize timing-critical nodes to reduce runtime. Moreover, the longest-path-first scheme enables parallel execution, substantially accelerating the remapping process. Experimental results show that our proposed method achieves an average runtime speedup of 8.92X compared to the state-of-the-art approach, while preserving placement quality. The improved efficiency and scalability of our flow make it well-suited for large-scale physical design applications where rapid timing closure is essential. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2025-08-21T16:59:29Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2025-08-21T16:59:29Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements iii
Abstract (Chinese) iv Abstract vi Table of Contents vii List of Tables x List of Figures xi Chapter 1. Introduction 1 1.1 Multiple-Cell-Height Standard Cells . . . . . . . . . . . . . . . . . . . . . 1 1.2 Classification of Multiple-Cell-Height Design Flows . . . . . . . . . . . . 3 1.3 Previous Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 IMCH Placement and Legalization . . . . . . . . . . . . . . . . . . 5 1.3.2 NIMCH Placement and Legalization with Different Sub-region Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2.1 Grid-Structured Sub-Regions . . . . . . . . . . . . . . . . 9 1.3.2.2 Row-Structured Sub-Regions . . . . . . . . . . . . . . . . 10 1.3.2.3 The Resynthesis-Based Strategy . . . . . . . . . . . . . . . 11 1.4 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Chapter 2. Preliminaries 16 2.1 Layout Constraints in NIMCH Designs . . . . . . . . . . . . . . . . . . . 16 2.2 Logic Synthesis and Resynthesis . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 NIMCH Legalization with Node Remapping . . . . . . . . . . . . . . . . 18 2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chapter 3. Our Proposed Algorithm 21 3.1 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 NIMCH Node Remapping . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Parallel NIMCH-Aware Longest Paths Identification . . . . . . . . 23 3.2.2 Parallel DP-Based Longest-Path-First Node Remapping . . . . . . 25 3.2.3 Iterative Minimum-Slack-First Node Remapping . . . . . . . . . . 29 3.3 Postprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Chapter 4. Experimental Results 33 4.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Results and Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2.1 Comparison with Lesyn . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2.2 Performance at Different Thread Counts . . . . . . . . . . . . . . . 37 4.2.3 Empirical Time Complexity . . . . . . . . . . . . . . . . . . . . . . 38 4.2.4 Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.2.5 Layouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Chapter 5. Conclusions and Future Works 42 5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.2.1 Simultaneous Height Assignment and Node Remapping . . . . . . 44 5.2.2 DFM-Aware Node Remapping . . . . . . . . . . . . . . . . . . . . 44 5.2.3 Node Remapping for Hybrid-Row-Height Designs . . . . . . . . . . 46 Bibliography 48 Publication List 55 | - |
| dc.language.iso | en | - |
| dc.subject | 實體設計 | zh_TW |
| dc.subject | 非整數倍高度擺置 | zh_TW |
| dc.subject | 合法化 | zh_TW |
| dc.subject | 節點重映射 | zh_TW |
| dc.subject | Non-Integer Multiple-Cell-Height Placement | en |
| dc.subject | Legalization | en |
| dc.subject | Physical Design | en |
| dc.subject | Node Remapping | en |
| dc.title | 考慮非整數倍數高度之標準元件之平行化電路節點重映射 | zh_TW |
| dc.title | Parallel Non-Integer Multiple-Cell-Height Node Remapping | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 113-2 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 江蕙如;黃婷婷;方劭云 | zh_TW |
| dc.contributor.oralexamcommittee | Iris Hui-Ru Jiang;Ting-Ting Hwang;Shao-Yun Fang | en |
| dc.subject.keyword | 實體設計,非整數倍高度擺置,合法化,節點重映射, | zh_TW |
| dc.subject.keyword | Physical Design,Non-Integer Multiple-Cell-Height Placement,Legalization,Node Remapping, | en |
| dc.relation.page | 55 | - |
| dc.identifier.doi | 10.6342/NTU202503877 | - |
| dc.rights.note | 同意授權(全球公開) | - |
| dc.date.accepted | 2025-08-11 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電子工程學研究所 | - |
| dc.date.embargo-lift | 2025-08-22 | - |
| 顯示於系所單位： | 電子工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-113-2.pdf | 2.43 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。