作者：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 那棵“树”一着不好。
核心论点参考以下文章及论文
https://techxplore.com/news/2025-10-weakness-classic-algorithm-reconfigurable-chips.html
https://www.computer.org/csdl/proceedings-article/fccm/2025/028100a143/275kN0A3SA8
Pathfinder: A Negotiation-Based Performance-Driven Router for FPGAs