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

在 FPGA 的設(shè)計(jì)流程里，有一個(gè)名字幾乎無人不知：PathFinder。

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

但最近 EPFL + AMD 的團(tuán)隊(duì)在一篇新研究中指出：當(dāng)電路越來越復(fù)雜、連線越來越密，「PathFinder 有時(shí)會(huì)失敗」——它的局限性終于被“撕開了”。

今天我們就來聊聊：

PathFinder 為什么關(guān)鍵？

它的經(jīng)典缺點(diǎn)是什么？

在 FPGA 世界里，我們?cè)撊绾慰创蛻?yīng)對(duì)這個(gè)算法的瓶頸？

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

在 FPGA 的后端流程里，布線是最關(guān)鍵的一步：你已經(jīng)確定了模塊擺放（placement），下一步是把各個(gè)信號(hào)連通起來。這個(gè)過程中要滿足以下要求：

不重疊（線路不能沖突）

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

布線資源有限

PathFinder 算法正是為了解決這類布線圖形化問題的經(jīng)典工具：它會(huì)把信號(hào)當(dāng)做“樹”（tree）來連通多個(gè)目標(biāo)點(diǎn)（多點(diǎn)網(wǎng)絡(luò)），在布線資源有限的情況下生成通道。

因?yàn)?FPGA 的互連資源（routing wires、開關(guān)節(jié)點(diǎn)）是稀缺的，布線越好、沖突越少，設(shè)計(jì)的性能和可路由性就越高。PathFinder 的好壞，直接影響設(shè)計(jì)能不能“布”通、時(shí)序能不能達(dá)標(biāo)。

正因?yàn)樗€(wěn)定、可靠、行之多年，它就成了幾乎所有 FPGA 工具鏈里默認(rèn)的布線模塊。

二、PathFinder 的經(jīng)典缺陷：在大規(guī)模電路里“偶爾翻車”

雖說 PathFinder 長期以來表現(xiàn)“異常穩(wěn)定”，但隨著設(shè)計(jì)變大，它的盲點(diǎn)也慢慢顯現(xiàn)。EPFL / AMD 團(tuán)隊(duì)的研究就揭示了幾個(gè)關(guān)鍵弱點(diǎn)：

1. 構(gòu)造出的 routing 樹往往“比必要的更大”

研究指出，PathFinder 在連接節(jié)點(diǎn)時(shí)，有時(shí)會(huì)“過度擴(kuò)展”樹枝，使得樹形結(jié)構(gòu)本可以更簡潔的情況下被拉得龐大。這樣一來，布線資源被占得更滿，沖突可能性更高。

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

2. 分支順序敏感性強(qiáng)

在給信號(hào)添加不同分支（branch）的時(shí)候，PathFinder 的行為很受“添加順序”的影響。不同的順序可能產(chǎn)生完全不同的結(jié)果——有些版本能成功、有些就失敗。團(tuán)隊(duì)發(fā)現(xiàn)在一些“本應(yīng)可布線”的小例子里，PathFinder 表現(xiàn)反常。

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

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

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

這些缺陷在過去不太被注意，是因?yàn)樵O(shè)計(jì)規(guī)模沒那么大、資源余量足。但隨著 FPGA 越做越復(fù)雜，可能被壓到極限時(shí)，這些弱點(diǎn)就暴露出來了。

三、面對(duì) PathFinder 的局限，設(shè)計(jì)師怎樣“保命”？

發(fā)現(xiàn)問題容易，能改進(jìn)才難。下面是幾個(gè)在實(shí)際工程里常用／建議的對(duì)策：

這些方法各有利弊，有時(shí)得組合使用才穩(wěn)定。

四、小結(jié)

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

在大規(guī)模、資源緊張的設(shè)計(jì)場景中，它的弱點(diǎn)可能導(dǎo)致設(shè)計(jì)“明明可做，卻被標(biāo)簽為不可路由”。

對(duì)普通 FPGA 開發(fā)者而言，了解這些局限有助于在設(shè)計(jì)早期就規(guī)避坑、在布線階段提升穩(wěn)定性。

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