以下文章來源于OpenFPGA，作者碎碎思

在 FPGA 的設計流程里，有一個名字幾乎無人不知：PathFinder。

自 1990 年代末以來，PathFinder 一直是 FPGA 布線（routing）階段的主力算法，為設計工具提供“能連通又不重疊”的路徑規劃方案。

但最近 EPFL + AMD 的團隊在一篇新研究中指出：當電路越來越復雜、連線越來越密，「PathFinder 有時會失敗」——它的局限性終于被“撕開了”。

今天我們就來聊聊：

PathFinder 為什么關鍵？

它的經典缺點是什么？

在 FPGA 世界里，我們該如何看待和應對這個算法的瓶頸？

一、什么是 PathFinder？它為什么重要

在 FPGA 的后端流程里，布線是最關鍵的一步：你已經確定了模塊擺放（placement），下一步是把各個信號連通起來。這個過程中要滿足以下要求：

不重疊（線路不能沖突）

延遲受限（路徑不要過長）

布線資源有限

PathFinder 算法正是為了解決這類布線圖形化問題的經典工具：它會把信號當做“樹”（tree）來連通多個目標點（多點網絡），在布線資源有限的情況下生成通道。

因為 FPGA 的互連資源（routing wires、開關節點）是稀缺的，布線越好、沖突越少，設計的性能和可路由性就越高。PathFinder 的好壞，直接影響設計能不能“布”通、時序能不能達標。

正因為它穩定、可靠、行之多年，它就成了幾乎所有 FPGA 工具鏈里默認的布線模塊。

二、PathFinder 的經典缺陷：在大規模電路里“偶爾翻車”

雖說 PathFinder 長期以來表現“異常穩定”，但隨著設計變大，它的盲點也慢慢顯現。EPFL / AMD 團隊的研究就揭示了幾個關鍵弱點：

1. 構造出的 routing 樹往往“比必要的更大”

研究指出，PathFinder 在連接節點時，有時會“過度擴展”樹枝，使得樹形結構本可以更簡潔的情況下被拉得龐大。這樣一來，布線資源被占得更滿，沖突可能性更高。

換句話說，它有時不“精打細算”，而是把可能用得上的路徑都鋪開一點，以保安全，結果反而減低整體效率。

2. 分支順序敏感性強

在給信號添加不同分支（branch）的時候，PathFinder 的行為很受“添加順序”的影響。不同的順序可能產生完全不同的結果——有些版本能成功、有些就失敗。團隊發現在一些“本應可布線”的小例子里，PathFinder 表現反常。

也就是說，在復雜電路里，“順序”這個幾乎看不見的決策，可能決定能不能布線成功。

3. 對極端邊界 /密集連線 /擁塞場景脆弱

在信號非常密集、資源極度緊張的區域，PathFinder 有時被標簽為 “unroutable”（無法路由），即使理論上是有解的設計。很多設計師遇到這類問題時，只能換更大 FPGA、重排模塊、或者放棄部分連接。

這些缺陷在過去不太被注意，是因為設計規模沒那么大、資源余量足。但隨著 FPGA 越做越復雜，可能被壓到極限時，這些弱點就暴露出來了。

三、面對 PathFinder 的局限，設計師怎樣“保命”？

發現問題容易，能改進才難。下面是幾個在實際工程里常用／建議的對策：

這些方法各有利弊，有時得組合使用才穩定。

四、小結

PathFinder 是 FPGA 工具鏈里不可或缺的“布線路徑規劃器”，但它不是萬能的。

在大規模、資源緊張的設計場景中，它的弱點可能導致設計“明明可做，卻被標簽為不可路由”。

對普通 FPGA 開發者而言，了解這些局限有助于在設計早期就規避坑、在布線階段提升穩定性。

下次當工具提示“unroutable”時，別急著換板、別急著重寫邏輯，先想想是不是 PathFinder 那棵“樹”一著不好。