有效率的靜態時序分析研究

On Efficient Static Timing Analysis

郭天鈺(Tien-Yu Kuo)

指導教授 ： 麥偉基

國立清華大學/電機資訊學院/資訊工程學系/碩士(2012年)

摘要

由於效能一直都是電路設計上的關鍵要素，且引導時序最佳化的是時序分析的結果，故而時序分析是設計流程內最重要的步驟之一。時序分析旨在求出電路的時序情形，並且檢查是否符合時序限制的要求。現今工業界的電子設計自動化工具仍然以靜態時序分析(STA)為主流，因此，以其在設計流程內的重要性，我們需要仔細斟酌多項因素以提高其分析效率。我們在本篇論文內研究了兩個靜態時序分析內的重要議題︰真實路徑測定與時序限制驗證，並提出了一個有效率的演算法以解決真實路徑測定的問題以及分享靜態時序分析引擎的設計思路。實驗結果除了展現所提出演算法的效率之外，我們也從中發現了一些有趣的趨勢。

關鍵字

靜態時序分析 ； 平行程式 ； 演算法 ； 電子設計自動化 ； 偽路徑

並列摘要

Since the performance of a circuit is always a key factor to be considered, timing analysis, whose result guides timing optimization, is the most important procedure in the design flow.
Timing analysis is the step to evaluates the timing behavior of a circuit and checks whether the design can meet timing constraints or not. Current industrial EDA tools still use Static Timing Analysis (STA) as the mainstream. Due to its importance in the design flow, we need to carefully consider various factors so as to have better efficiency. In this thesis, we study two important issues in STA: true path determination and timing constraint verification. We propose an effective algorithm for the true path determination problem and share the experiences of designing an efficient STA engine to verify that all timing constraints of a circuit are satisfied. Experimental results show the efficiency of the proposed algorithm and we also find some interesting trends in the results.

並列關鍵字

Static Timing Analysis ； Parallel programming ； Algorithm ； Electronic Design Automation ； False path

參考文獻

110-115, 2009

ing second-order polynomial fitting,” In Proceedings of Asia and South Pacific Design

[3] Kanupriya Gulati and Sunil P. Khatri, “Accelerating Statistical Static Timing Analysis

Using Graphics Processing Units,” In Proceedings of Asia and South Pacific Design

Automation Conference, pp. 260-265, 2009