1982-增量式靜態時序分析#

案件摘要#

時序分析的老方法：丟一堆輸入向量，跑模擬看最壞延遲——但最壞向量永遠猜不準，漏一個就是流片失敗。1982 年，IBM 的 Roy Hitchcock 等人發表「Timing Analysis of Computer Hardware」：反向——不去猜向量，而是靜態地遍歷所有路徑，用「抵達時間（arrival time）/需求時間（required time）/裕量（slack）」三量在 DAG 上做動態規劃。靜態時序分析（STA）從此誕生：不依賴向量、遍歷全晶片、可增量重跑。這是此後四十年時序簽核（PrimeTime、Tempus）的數學基礎，也讓「時序收斂」變成可以迭代閉環的工程。

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

向量模擬的盲區：動態模擬（測試向量 + 模擬器）只能驗證「你想到的路徑」；最壞路徑常在意想不到的組合——覆蓋率是偽命題。
時鐘越來越快：VLSI 世代，路徑延遲逼近時脈週期，任何一條路徑超時都是災難，必須窮盡所有路徑。
路徑指數爆炸： \(n\) 個邏輯級的路徑數是指數級——窮舉也不行，必須動態規劃。
PERT 的先例（1957-58，北極星計畫）：專案排程用「最早開始/最晚開始時間」在活動網路上找關鍵路徑——數學模板已就緒。

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

核心：DAG 上的動態規劃#

把同步電路拆成組合邏輯 DAG（暫存器切邊）。設單元延遲 \(d(v)\) 、線延遲 \(w(u,v)\) ：

正向傳播（arrival time）——拓撲序掃描，取所有輸入路徑的最大值：

\[ A(v) = \max_{u \in \text{fanin}(v)} \big(A(u) + d(u) + w(u,v)\big), \quad A(\text{PI}) = 0 \]

反向傳播（required time）——從時脈截止時間倒推：

\[ R(u) = \min_{v \in \text{fanout}(u)} \big(R(v) - d(u) - w(u,v)\big), \quad R(\text{PO}) = T_{\text{clk}} \]

裕量（slack）：

\[ S(v) = R(v) - A(v), \quad S(v) < 0 \Rightarrow \text{違規路徑} \]

複雜度： \(O(|V| + |E|)\) ——一次線性掃描遍歷所有路徑的資訊。動態規劃的魔力：指數條路徑的極值被壓縮成線性掃描。

關鍵：最壞是 max，不是「猜」#

模擬法問「這個向量多快」；STA 問「任何輸入下最壞多快」——後者才是簽核問題。正向傳播的 \(\max\) 運算，正是「考慮所有可能輸入組合」的數學化身。

增量式：改一處、只重算受影響處#

優化迴圈（閘尺寸、緩衝器插入）改一個單元，只有其下游的 arrival 與上游的 required 變。增量 STA 從改動點局部重掃，把 \(O(V+E)\) 的全量重算降到局部——這是「時序收斂迴圈」能反覆執行數千次的關鍵。真路徑/假路徑：配 false path 與 multicycle 註解（SDC 約束）過濾非關鍵路徑。

結案 -- 後果與影響#

時序簽核的標準：STA 成為所有先進製程 tape-out 的必經關卡；Synopsys PrimeTime、Cadence Tempus 都是其工業化後代。
時序驅動設計的引擎：佈局、繞線、合成的每一步都要查 slack——STA 把「時序」變成全域優化的目標函數，催生時序驅動佈局繞線（1990s）。
路徑為王的物理化：slack 負值最大的路徑 = 關鍵路徑，優化資源自動聚焦——「抓首惡」的工程策略。
理論的移植典範：PERT/CPM 的關鍵路徑法（運籌學 1957）移植到晶片——EDA 跨學科借力的經典案例。

關鍵人物與文獻#

Roy E. Hitchcock：IBM Watson，STA 與增量分析的提出者。
文獻：
R. B. Hitchcock, G. L. Smith, D. D. Cheng, "Timing Analysis of Computer Hardware," IBM J. Res. Dev. 26, 100 (1982).
G. L. Smith, R. J. Bahnsen, H. Halliwell, "Boolean Comparison of Hardware and Flowcharts," IBM J. Res. Dev. 26, 106 (1982)（同期 IBM 時序驗證系統）。
D. E. Wallace, "Timing Analysis of Logic Circuits," MIT thesis / 工業化：Synopsys PrimeTime 手冊。