跳轉到

06.1 Elmore 延遲與 RC 樹：一個 1948 年模型的長壽#

在 EDA 演算法的萬神殿裡，很少有哪個演算法能像 Elmore delay 一樣，從誕生到今天七十八年（截至本文寫作的 2020 年代）始終站在生產線的核心位置。今天每一個做靜態時序分析（STA）的引擎、每一個佈局繞線工具內建的延遲估計器、甚至本書討論的 veryl2chip 這類開源 ASIC 流程中，綜合後估計互連延遲的第一步幾乎都是 Elmore 模型。一個比電晶體積體電路早了十幾年、比第一個商用 EDA 工具早了三十年的公式，為什麼能活這麼久？要回答這個問題，得先回到 1948 年，回到一個和晶片完全無關的領域：核子物理實驗中的脈波量測。

曼哈頓計畫的副產品#

William Cotter Grey Elmore（1911–2009）是一位美國物理學家，二戰期間在曼哈頓計畫的體系中工作。當時的核子實驗——例如以游離腔、蓋格計數器偵測粒子，並用示波器觀察脈波——有一個共同的痛點：實驗者量到的脈波上升時間，究竟是訊號本身的物理特性，還是被前級放大器、長電纜與示波器電路「吃掉」的部分？要回答這個問題，必須能夠解析地預測一個線性電路（放大器、濾波器、RC/RLC 網路）對階躍或脈波的響應時間。1948 年，Elmore 在 Journal of Applied Physics 上發表了〈The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers〉，提出了一套用「電路的矩（moments）」來刻劃暫態響應的方法。這篇論文定義了後來以他為名的兩個量：rise time 的度量，以及我們今天所稱的 Elmore delay——階躍響應歸一化一階矩，物理上是「脈衝響應重心的時間」。

Elmore 的出發點是這樣的：對一個線性非時變電路，階躍響應 \(v(t)\) 的「延遲」可以定義為

\[ t_D = \frac{\int_0^\infty t\, v'(t)\, dt}{\int_0^\infty v'(t)\, dt} \]

也就是脈衝響應 \(v'(t)\) 的重心。如果電路的單位脈衝響應是單峰、且近似對稱的形狀，這個重心就是輸出波形跨越 50% 位準的好估計。對單一 RC 節點（電阻 \(R\) 對電容 \(C\) 放電），解析解是指數衰減，跨過 50% 的時間是 \(t_d = \ln 2 \cdot RC \approx 0.69\,RC\) ；而用 Elmore 的矩方法算出來的重心恰是 \(RC\) ，兩者只差一個常數因子 0.69。這就是工程師口中「Elmore delay 等於 0.69 RC」的由來——更精確地說，Elmore 給的是一階矩，0.69 這個係數是單極點情形下的換算。

RC 樹上的逐節點公式#

Elmore 公式在 EDA 裡真正大放異彩，是因為它有一個驚人的性質：對於一個樹狀（無迴路、單一輸入源）的 RC 網路，任何節點 \(i\) 的 Elmore 延遲有一個純粹拓樸的閉式解：

\[ t_i = \sum_{k \in \text{path}(s \to i)} R_k \cdot C_k^{\text{down}} \]

其中 path \((s \to i)\) 是從訊號源到節點 \(i\) 的唯一路徑， \(R_k\) 是路徑上第 \(k\) 段的電阻， \(C_k^{\text{down}}\) 是以 \(k\) 為根的子樹的總電容。白話版本：某節點的延遲，等於「沿途每一段電阻，乘上該電阻下游所有電容」的總和。用 pseudo code 寫出來就是一次樹的後序走訪加一次前序累加：

# 後序：算每個節點下游總電容 Cdown
def calc_cdown(u):
    Cdown[u] = C[u]
    for v in children(u):
        Cdown[u] += calc_cdown(v)
    return Cdown[u]

# 前序：累加延遲
def elmore(u, acc_R):
    delay[u] = delay[parent[u]] + acc_R ... 
    # 或等價形式：delay[u] = delay[parent] + R[u]*Cdown[u]
    for v in children(u):
        elmore(v, ...)

整體計算量是 \(O(n)\) ， \(n\) 是樹上節點數（例如繞線後切出來的互連 segment 數）。對照動態模擬：即使是簡化的 SPICE，解一個有 \(n\) 個電容節點的電路也要對 \(n \times n\) 矩陣反覆做數值積分，典型成本是 \(O(n^2)\) 到 \(O(n^3)\) ，而且只給你「這一次激勵下的波形」。Elmore 給的是每個節點一個純量數字（延遲），成本線性，而且——這是關鍵——它不需要知道輸入波形，只要電路是 RC 樹。

這個逐節點閉式解在 EDA 文獻中常被歸功於 1980 年代的工作，例如 Penfield 與 Rubinstein（1981，MIT）對 RC 網路上界延遲的分析，以及 Rubinstein、Penfield、Horowitz（1983）明確寫出樹狀 RC 網路的 Elmore 公式並證明其 \(O(n)\) 計算。這些工作發生的背景是：VLSI 設計在 1980 年代初爆發，晶片上金屬繞線的 RC 延遲開始在百萬閘設計中變得不可忽略，設計者需要能在整個晶片規模上反覆呼叫的互連延遲估計，而逐網段跑 SPICE 在當時的電腦上完全不現載。歷史在此出現一個漂亮的巧合：1981 年 Ron Rohrer 在 UC Berkeley 的電路模擬課上，把「如何快速估計互連延遲」當作專題，學生裡出了 SPICE 的維護者與 Tau（Timing Analyzer with approximations，IBM 術語）路線的關鍵人物；而 Elmore 1948 年的矩方法恰好是現成答案。Rubinstein、Penfield、Horowitz 的論文题目就叫 "Signal Delay in RC Tree Networks"，把 Elmore 的矩正式變成 EDA 的演算法。

單極點近似的物理意義#

Elmore delay 為什麼「準」？它的物理詮釋是：把整個 RC 樹看成一個單極點系統，等效時間常數 \(\tau = t_D\) ，於是輸出近似為 \(v(t) = 1 - e^{-t/\tau}\) ，50% 跨越點約在 \(0.69\,t_D\) 。對於緩慢輸入、純電容負載、無電感的樹狀網路，脈衝響應確實近單峰對稱，這個近似誤差通常在 3–5% 以內。但它有三個已知的天花板：一是對輸入 slew 敏感，陡的輸入會低估、緩的輸入會高估，所以實務上還要配上一個 slew 傳播模型（例如把 slew 定義為 \(2.2\,\tau\) 之類的換算，或用Lookup table 修正）；二是對於有大電感、有耦合電容、或深次微米後的長線（傳輸線效應），單極點假設崩壞；三是它只給 50% 延遲，給不了波形細節。

EDA 產業的答案向來是務實的：Elmore 不夠準時，就上「打表」——用nonlinear delay model（NLDM），對每個 cell 預先用 SPICE 掃出 delay/slew 對輸入 transition 與輸出負載的二維表；Elmore 延遲與 slew 被用來把繞線寄生參數折算成等效負載，再進 NLDM 查表。換言之，現代 STA 引擎裡，Elmore 通常不再直接給「最終數字」，而是給「把幾何變成電學」的那一步。這一步便宜到可以在優化迴圈裡被呼叫幾十億次，而它後面接的查表模型補足了非線性。這種「便宜的一階模型 + 預計算的非線性校正」分層架構，是 EDA 演算法設計反覆出現的母題。

與 SPICE 的分工#

1973 年，Laurence Nagel 在 UC Berkeley 發表 SPICE（Simulation Program with Integrated Circuit Emphasis），把電路模擬從昂貴的實驗室工具變成每個設計者桌上的標準動作。SPICE 解的是完整非線性微分方程組：牛頓迭代解非線性直流/暫態、隱式積分解時間演化、稀疏矩陣解聯立。它準確，但每次模擬的成本與電路規模成高次方成長，且給出的是波形而非「通路是否違約」的判斷。當設計規模從千閘走向百萬閘，產業需要的不是「這個波形長怎樣」，而是「這五百萬條路徑裡哪些違反 setup/hold」——這是一個組合最佳化問題，不是微分方程問題。於是 1970 年代末，IBM（內部工具如 EINST/Timmu 系列的先驅）、TI、Bell Labs 等公司各自發展了不模擬波形、直接在邏輯圖上傳播延遲數字的「timing verifier」，這就是靜態時序分析（STA）的起源。而 STA 要成立，第一個前提就是得有一個 \(O(n)\) 、閉式、可增量更新的延遲模型——Elmore delay 正是那塊基石。

為什麼 1948 年的模型活到今天#

總結 Elmore 延遲的長壽，可以歸納出三層原因。技術上，它抓住了問題的結構：RC 樹延遲的本質是「電阻與下游電容的捲積和」，這個線性結構允許 \(O(n)\) 閉式解與增量更新，任何更精確的模型（如 PRIMA 約化、moment matching 的高階方法）都更貴，而準確度提升的邊際價值在打表模型出現後變小。經濟上，晶片設計的瓶頸是「在優化迴圈裡跑得夠快」，延遲模型被呼叫的次數（ \(10^9\) 量級）遠比單次準確度重要；精確度被外包給 signoff 階段的 SPICE 與寄生參數抽取（parasitic extraction）工具。制度上，一旦 Liberty/NLDM 這種「cell 延遲查表 + 網路 Elmore/等效電容」的介面成為 foundry 標準交付物（.lib 檔），整個生態就被鎖進這個架構——這是典型的路徑依賴：一個夠好的近似，加上標準化的介面，就能打敗更好的演算法。

Elmore 本人在 2000 年接受 IEEE Solid-State Circuits Magazine（2011 年刊出的回顧）訪談時，恐怕不會想到他為了看清楚示波器螢幕上的核子脈波而寫下的積分，會變成設計 iPhone 晶片時每天被執行十億次的公式。演算法史常常如此：一個模型能長壽，不是因為它當年多完美，而是因為它恰好卡在一個後來長成巨人的產業的最底層，而且形狀剛好。

理解了延遲的計算之後，下一個問題自然是：這些延遲數字如何在整個晶片的邏輯圖上組合、傳播，變成「setup 違約在第五萬條路徑上」這種可執行的工程結論？這就要進入靜態時序分析的計算框架——DAG 上的最長路徑，那是 6.2 節的主題。