跳轉到

1990s - 靜態時序分析：不需要測試向量的 signoff#

案件摘要#

1990 年代，靜態時序分析（Static Timing Analysis, STA）成為數位設計的 signoff 標準， Synopsys PrimeTime（1995）、Cadence Pearl、Mentor SST Velocity 相繼問世。 它不跑任何測試向量，而是把整個電路當成有向圖，沿路徑累加延遲、逐一檢查每條 timing path 的 slack。 當晶片閘數突破百萬、模擬無法窮盡所有路徑時，STA 是唯一能「數學上保證」時序正確的偵探。

前因 -- 為什麼會有這個案子#

  • 動態模擬撐不住了：動態模擬靠測試向量激勵電路，時序違例只在「剛好那組向量」下現身；百萬閘電路的路徑組合是指數級，模擬永遠漏案。
  • 早期工具不夠用：1980 年代的 timing verifier（如 Synopsys 早期工具、Mentor 的直方圖分析）只能粗估，誤差大到不能 signoff。
  • 連線延遲接管戰場：深次微米製程中連線延遲比重超過閘延遲，還與佈局相關——時序必須在佈局之後、用 extract 出的 RC 來驗證。
  • 關鍵推理：時序檢查本質上只依賴圖的拓撲與延遲參數，不需要向量：
\[ \text{signoff} = \underbrace{\text{DAG 最長路徑}}_{\text{arrival time}} \times \underbrace{\text{時序約束}}_{\text{required time}} \times \underbrace{\text{corner 模型}}_{\text{製程變異}} \]

只要對每條路徑證明 \(\text{slack} \ge 0\) ，時序即數學上成立——不論輸入向量為何。

線索與推理 -- 數學式、程式、理論#

1. 案件現場：arrival、required、slack 三件套#

\[ \text{slack} = \underbrace{\text{required time}}_{\text{容許到達時刻}} - \underbrace{\text{arrival time}}_{\text{實際到達時刻}} \]
  • arrival time：訊號沿 fanin 樹累加到達某節點的最晚時刻。
  • required time：反向從輸出端要求回推的容許時刻。
  • \(\text{slack} < 0\) 即違例（violation），STA 報告最差 slack 與 top N 違例路徑。

2. DAG 最長路徑：STA 的數學心臟#

時序圖 \(G=(V,E)\) 是有向無環圖（暫存器把迴圈切斷），節點延遲沿路累加、分支取 \(\max\) ：

\[ A(v) = \max_{u \in \text{fanin}(v)} \big(A(u) + d(u \to v)\big),\qquad A(v_0)=0 \]
  • 一般圖的最長路徑是 NP-hard，但 DAG 上可以拓撲排序後線性時間求解——這是 STA 能窮盡百萬閘電路的原因。
  • 關鍵定理：對 DAG 拓撲序做一次掃描，即可在 \(O(|V|+|E|)\) 內算出所有 arrival time，等價於窮盡所有路徑。

3. Setup 與 hold：兩個方向的檢查#

setup 檢查（最壞 corner，慢）：資料在時脈來臨前要穩定——

\[ A_{\max}(d) + t_{su} \le T_{\text{clk}} + t_{\text{skew}} \]

hold 檢查（最好 corner，快）：資料在時脈來臨後要保持——

\[ A_{\min}(d) \ge t_{h} + t_{\text{skew}} \]
  • setup 用 worst corner（慢製程、低壓、高溫），hold 用 best corner（快製程、高壓、低溫）——兩個 corner 都要過。
  • hold 違例晶片直接不能開機，setup 違例只是跑得慢，因此 hold 是更凶險的案子。

4. False path 與 multicycle path#

並非所有路徑都要在單一 cycle 內過：非同步跨時脈域（clock domain crossing）、設定為 false path 的路徑、多週期路徑（multicycle）要放寬約束。STA 工具以約束檔（SDC）排除偽路徑：

\[ \text{true slack} = \min_{\text{path} \in \text{true paths}} \text{slack(path)} \]

約束寫錯（漏排除 false path）會造成「假違例」；過度排除則會「漏掉真違例」——偵探也可能被假線索誤導。

5. Verilog 速記：STA 檢查的電路本質#

// 兩級 FF 之間的 timing path：setup = Tclk - (comb 延遲 + tsu)
module pipe (input clk, d, output reg q2);
    reg q1;
    always @(posedge clk) begin
        q1 <= d;               // launch FF
        q2 <= q1 & ~d;         // capture FF：path delay = d(u->v) 累加
    end
endmodule
// STA 的立場：不必跑模擬，只要 q1 & ~d 的 arrival + tsu <= Tclk 即結案

6. Python 實作：DAG 拓撲排序 STA#

from collections import defaultdict

edges = {                                # (u -> v): delay，單位 ns
    ('in', 'a'): 0.0, ('a', 'b'): 0.8, ('a', 'c'): 1.2,
    ('b', 'd'): 0.6, ('c', 'd'): 0.3, ('d', 'out'): 0.1,
}
fanin, fanout = defaultdict(list), defaultdict(list)
for (u, v), d in edges.items():
    fanin[v].append((u, d)); fanout[u].append((v, d))

order = []                               # 拓撲排序（Kahn）
indeg = {n: 0 for n in fanin | fanout}
seen = set(indeg)
for u, v in edges: indeg[v] += 1
stack = [n for n in seen if indeg[n] == 0]
while stack:
    n = stack.pop(); order.append(n)
    for v, _ in fanout[n]:
        indeg[v] -= 1
        if indeg[v] == 0: stack.append(v)

arrival = {n: 0.0 for n in seen}
for n in order:                          # 正向掃描：A(v) = max(A(u) + d)
    for v, d in fanout[n]:
        arrival[v] = max(arrival[v], arrival[n] + d)

Tclk, tsu = 2.0, 0.2                     # 週期 2ns、setup 時間 0.2ns
slack = arrival['out'] - (Tclk - tsu)
for n in sorted(arrival, key=arrival.get, reverse=True):
    print(f"arrival({n}) = {arrival[n]:.1f} ns")
print(f"path delay = {arrival['out']:.1f} ns, slack = {slack:+.1f} ns")
# arrival(out) = 2.7 / arrival(d) = 2.6 / ... （最長路徑 in→a→c→d→out 不成立，實際為 a→b）
# path delay = 1.5 ns, slack = -0.7 ns → 若 worst path > 1.8ns 即違例

（程式輸出最長路徑與 slack：若 path delay + tsu > Tclk 則印出負 slack，即違例結案。）

結案 -- 後果與影響#

  • signoff 必備：沒有過 STA 就不能 tape-out；setup/hold + OCV 三重檢查成為每顆晶片的通關文牒。
  • 閉迴路成形：synthesis → placement → CTS → routing 每一步都呼叫 incremental STA，timing-driven 佈局繞線從此由 STA 驅動。
  • 理論延續：OCV/CRPR（on-chip variation 與 path-based 修正）、Statistical STA（變異分布）、ML 預測 delay 加速收斂，都在 1990s 這條線上。
  • 約束語言標準化：SDC（Synopsys Design Constraints）成為全產業通用約束格式，工具間可互換。

關鍵人物與文獻#

  • Synopsys PrimeTime（1995）、Cadence Pearl、Mentor SST Velocity：STA signoff 工具三強。
  • Kurt Keutzer、Aart de Geus 團隊（Synopsys）：timing-driven 設計流程的推手。
  • J. Bhasker, R. Chadha, Static Timing Analysis for Nanometer Designs, Springer, 2009。
  • N. Weste, D. Harris, CMOS VLSI Design, 4th ed., 2010——STA 章節為標準教材。