- 學位論文
通過破解固有關鍵路徑以加速靜態時序分析
Inherent Critical Path Breaking for Accelerating Static Timing Analysis
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
隨著 VLSI 電路設計的複雜度不斷提升，以及對時序分析精度要求的增加，導致靜態時序分析逐漸成為 VLSI 設計週期的一個挑戰。儘管有許多應用機器學習來預測時序分析結果的研究，但是諸如擱筆時序分析及更安全的製造流程，完成時序分析計算仍是不可替代的一個重要步驟。平行加速在靜態時序分析中的應用縮短了所需要花費的時間，但是，由於晶片設計的複雜度導致元件有錯綜復雜的依賴約束，如何有效的平行加速是一項挑戰。本篇論文提出一種克服依賴約束的手法來達到更有效的平行化加速的演算法，應用了電壓轉換率差異收斂的現象，並搭配多層級演算法框架，在不同顆粒度的迭代下優化任務調度，以縮短完成靜態時序分析的整體時間。實驗結果表明此種做法不僅優化了運算資源利用率，並透過降低調度同步成本來達到有效的加速。
並列摘要
As the complexity of VLSI circuit design continues to increase, along with the demand for higher precision in timing analysis, static timing analysis (STA) has gradually become a challenging aspect of the VLSI design cycle. Despite numerous studies employing machine learning techniques to predict timing analysis outcomes, completing STA calculations remains an indispensable step, particularly for ensuring robust timing closure, such as sign-off analysis, and secure manufacturing processes. Parallel acceleration has been applied to STA to reduce computation time; however, the intricate dependency constraints inherent in complex chip designs pose significant challenges to effective parallelization. This paper proposes an algorithm to overcome these dependency constraints, thereby achieving more efficient parallel acceleration. By leveraging the phenomenon of slew difference convergence and incorporating a multi-level algorithmic framework, the proposed method optimizes the makespan of STA through iterative refinement at different granularity, ultimately reducing the makespan of completing STA. Experimental results demonstrate that this approach successfully accelerating STA by fully utilizing the computing resources.
參考文獻
[1] A. Ger, Y.-Y. Tien, P.-Y. Lee, and I. H.-R. Jiang, “A general multi-level framework for makespan minimization in parallel dag scheduling,” 2024, unpublished master’s thesis, National Taiwan University.
[2] Z. Guo, T.-W. Huang, and Y. Lin, “Gpu-accelerated static timing analysis,” in Proceedings of the 39th international conference on computer-aided design, pp. 1–9, 2020.
[3] Z. Guo, T. W. Huang, and Y. Lin, “Accelerating static timing analysis using cpu–gpu heterogeneous parallelism,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 42, no. 12, pp. 4973–4984, 2023.
[4] J. Hu, G. Schaeffer, and V. Garg, “TAU 2015 contest on incremental timing analysis,” in International Conference on Computer-Aided Design (ICCAD), pp. 882–889, 2015.
[5] T.-W. Huang, G. Guo, C.-X. Lin, and M. D. F. Wong, “OpenTimer v2: A new parallel incremental timing analysis engine,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, vol. 40, no. 4, pp. 776–789, 2021.