07.4 PathFinder 協商繞線：FPGA 世代共享的擁塞哲學#

一個新問題：資源不能改，線也不能少#

1990 年代，FPGA 產業快速崛起。Xilinx、Altera 的元件把可程式化的邏輯塊（LUT、FF）與一張固定的可程式化互連網路封在一顆晶片裡。對繞線工具而言，FPGA 帶來一個與 ASIC 截然不同的處境：互連資源在晶片出廠時就固定死了——每條線段、每個開關、每個 mux 的位置與容量都寫在架構描述裡，工具只能「用」，不能「畫」。而且沒有後路：ASIC 詳細繞線繞不通還可以 ripup 重繞到天荒地老，FPGA 繞不通這顆晶片就報廢了這個設計；反過來說，設計者也不會重畫晶片，所以繞線器必須在這張固定的資源圖上，把所有線網 100% 繞完。

在這個處境下，傳統「先繞者占格、繞不過就懲罰重繞」的做法暴露了弱點：懲罰要怎麼調才能收斂？誰讓誰？1980 年代的 ripup 迴圈在小規模上憑經驗調參尚可運作，但 FPGA 繞線資源緊張、圖的拓撲又極不均勻（不同方向的線段長度、開關密度都不同），工程式的懲罰很快失效。這正是 1995 年 University of Washington 的 Larry McMurchie 与 Carl Ebeling 發表《PathFinder: A Negotiation-Based Approach to Timing-Driven Routing of FPGAs》要解決的問題。

協商的核心公式#

PathFinder 的洞見是：與其一開始就避免擁塞，不如允許所有線網在早期「合法地超容」（share resources），然後透過一個不斷加價的拍賣機制，讓共用者自己協商出誰改道。每條線網先各自用 A*/迷宮搜尋找自己最便宜的路；若資源被超用，就提高它的 cost，下一輪大家都會重新考慮。資源的成本函數定義為

\[ \mathrm{cost}(n) = (b_n + h_n) \cdot p_n \]

其中 \(b_n\) 是資源 \(n\) 的基本成本（反映 delay：FPGA 上開關與長線段的延遲差異極大，這個乘積形式把時序驅動繞線自然納入）， \(h_n\) 是歷史成本（history cost）， \(p_n\) 是當下擁塞（present congestion）。兩個動態項的更新規則是：

\[ p_n = 1 + \max\big(0,\; (\text{占用數} - \text{容量} + 1) \cdot p_{\text{fac}}\big), \qquad h_n \leftarrow h_n + (\text{本輪超用量}) \cdot h_{\text{fac}} \]

關鍵在於 \(h_n\) 只增不減、且隨迭代累積：一個長期被搶佔的資源，歷史成本會越墊越高，最後逼著部分線網永久放棄它。早期的迭代寬容擁塞（ \(p_{\text{fac}}\) 設小，讓線網盡量走自己 delay 最優的路），後期逐步提高 \(p_{\text{fac}}\) 與 \(h_{\text{fac}}\) 加大擁塞壓力，最終在無超容狀態下收斂——只要資源總量夠，協商一定成功；若真的繞不完，收斂失敗本身就是明確的「架構容量不足」訊號，回饋給架構設計者。整套機制可用一個迴圈概括：

PathFinder:
    for each net: route it with cheapest paths (ignoring congestion at first)
    while any resource overused:
        for each overused resource r:
            h[r] += overuse(r) * h_fac
        for each net:
            rip up; reroute with cost = (b + h) * p   # A*/Dijkstra on RRG
        p_fac *= growth  (逐步加大當下擁塞壓力)
        # 收斂後：所有資源 usage <= capacity

這個機制的哲學意義值得停下來說清楚：它把「擁塞」從一個要被避免的錯誤，轉變為一種資訊傳遞的媒介——每輪迭代的超容狀態告訴所有線網「這裡搶手，你們自己商量」。最終誰讓路，不是由某個中央排程器決定，而是由分散的代價比較決定。這是市場機制在繞線器裡的體現，也解釋了為何它幾乎不需要問題相關的調參就能跨架構收斂。

為何 FPGA 世界完全依賴它#

PathFinder 問世後迅速成為學界與業界 FPGA 繞線的事實標準。Ebeling 後來把這套技術帶入商業工具——PathFinder 的思想成為 Seattle 一帶 FPGA 工具研發的基礎，也直接影響了商用廠商的繞線引擎設計。學術這邊，多倫多大學的 VPR（Versatile Place and Route，Jonathan Rose 團隊，1997 年起）採用了 negotiated congestion 作為其繞線引擎，成為此後二十年全世界 FPGA 架構研究的標準實驗平台；VTR（VPR + Verilog-to-Bits 流程）沿用至今。原因不難理解：FPGA 的繞線資源圖是固定、已知、可窮舉的，negotiated congestion 恰好是一種「在固定圖上反覆重繞直到無衝突」的方法，兩者天作之合。時至今日，幾乎所有學術與開源 FPGA 繞線器——VPR/Tor（VTR 的明星繞線器，含 timing-driven 版本）、各家自行研發的工具鏈——都是 PathFinder 的直系或旁系後裔。

反哺 ASIC：協商思想回到晶片世界#

有趣的是，這個在 FPGA 上成熟的技術，二十五年後又回流到 ASIC。2020 年前後，開源 EDA 運動（OpenROAD、DARPA IDEA 計畫資助的生態）面對的正是當年 FPGA 的同款難題：要有一個不靠商業秘方、行為可預期、對規模收斂的全局繞線器。UCSD（Kahng 團隊）與合作者開發的 FlexRoute 採用了兩步式 negotiated congestion：先在結構化（gridded）的 coarse 圖上做協商繞線，再把結果映射回真實層軌道；OpenROAD 的 global routing 流程（以及其後續的詳細繞線器 TritonRoute 的擁塞驅動重繞）都吸收了 path-based negotiation 的思想——用 history cost 累積逼線網讓路、用 present cost 引導當下決策，與 1995 年的公式血緣分明。協商繞線證明了一件事：好的演算法思想不屬於某一種晶片，而屬於問題本身——「多個爭奪者、有限資源、需要收斂」的結構在哪裡出現，它就在哪裡有用。

為什麼收斂：直覺與理論#

PathFinder 為何能收斂，值得用一段話說明。首先，history cost 是單調遞增的：一個資源只要曾被超用，它的價格就永久抬升，超用越久價格越高，因此「賴在同一個資源上不走」的策略會變得越來越貴，任何線網最終都會被逼著另尋出路。其次，present cost 隨迭代增長，使得「當下還在搶的衝突」在後期被懲罰得極重，系統整體從「寬容」平滑過渡到「嚴格」。直覺上，這像一場不斷加租的房地產市場：需求超過供給的路段租金節節高升，租客各自比較成本後自然分流，直到每個地點的租客數不超過房間數。形式上，可以把它視為對偶上升法（dual ascent）的近似：資源的「影子價格」就是 \(b+h\) ，反覆讓線網在最短路上重繞，等價於在鬆弛問題上迭代調價；只要圖上存在一個不超容的可行解，且調價速度夠快，協商最終會停在可行解附近。McMurchie 與 Ebeling 的論文並沒有給出完整收斂證明，收斂性更多靠實證（在數百個 FPGA 測試電路上全部收斂）與後續研究補強——這也再次印證 EDA 的傳統：先有能用的機制，理論後至。

FPGA 能孕育 PathFinder，靠的是它把繞線資源變成一張固定、明確的圖。這張圖長什麼樣、開關與線段如何組織、工具如何描述與遍歷它，是下一節的主題：switch box、connection box 與 routing resource graph。