如果在构建自动布线器之前我知道这些事就好了：13条经验教训

autorouting

尝试构建世界上最快的自动布线器一年后的一些重要教训

Seve 2025年3月28日

我花了一年时间来开发一个用于 tscircuit（一个用 TypeScript 编写的开源电子 CAD 内核）的自动布线器。如果我能回到一年前，我会告诉自己以下 13 件事：

我们的自动布线器在键盘上布线的一个中间阶段。

1. 像了解你的手背一样了解 A* 算法，并在任何地方使用它

如果我能当一天国王，我会将 A* 重命名为“基础算法”。它确实是适用于任何类型搜索的最具适应性和最重要的算法之一。 它只是任何类型知情搜索（不仅仅是二维网格！）的最佳基础。

这是一个 A* 与二维网格上的“广度优先搜索”的动画版本：

A* 探索节点的方式更快、更直观。 这两种算法的主要区别在于 BFS 探索所有相邻节点，而 A* 优先探索更靠近目的地的节点。 因为它考虑了图之外的度量（到目的地的距离），所以它是一种知情搜索。

你已经在你的代码中使用 BFS 或 DFS（深度优先搜索）了。 递归算法是深度优先搜索。 任何在不排序候选者/邻居的情况下探索候选者/邻居的循环都是 BFS。 99% 的情况下，你可以将其转换为 A 并获得显着的性能提升！*

我们在自动布线器中最喜欢的技术之一是我们运行多个级别的 A* 来发现特定问题的最佳超参数。 所以我们基本上是将每个自动布线器作为候选者运行，然后使用 A* 来确定我们应该在哪个自动布线器上花费最多的时间！

看到顶部的所有数字了吗？ 这些是超参数的每种不同配置。 公平地运行每个自动布线器将是极大的浪费时间 - 如果一个自动布线器开始获胜（它正在以良好的成本成功布线），则为其分配更多迭代！ 这种元 A* 结合了惩罚距离的常规成本函数和惩罚迭代的成本函数。

2. 实现语言并不重要

颇具争议的是，我正在用 JavaScript 编写我们的自动布线器。 这是人们首先指出的事情，但它并不像你想象的那么不合理。 考虑到在优化算法时，你基本上是在寻找改进两件事的方法：

1. 降低所需的迭代次数（使算法智能化）
2. 提高每次迭代的速度

人们过于关注提高每次迭代的速度。 如果你正在做一些愚蠢的事情（例如将所有内容转换为网格以进行重叠测试），无论你使用哪种语言，JavaScript 的性能都会击败你！

最佳汇编中的愚蠢算法*仍然比 JavaScript 中的智能算法慢！*算法 > 语言！

95% 的精力应该集中在减少迭代次数上。 这就是语言无关紧要的原因。 无论哪种语言能让你最快地得到最智能、最可缓存的算法，就是最好的语言。

3. 空间哈希索引 > 树数据结构

你无法在多维空间优化中走 5 英尺，而不让某人提到 QuadTree，这是一种令人难以置信的数据结构，它使在 2d/3d 空间中搜索附近对象时，O(N) 搜索变为 O(log(N))。

**QuadTree 和每个通用树数据结构都慢得令人发指。**树不是数据的知情表示。

每次使用树时，你都在忽略 O(~1) 哈希算法，而使用更复杂的 O(log(N)) 算法

为什么 JavaScript 默认情况下以及每次都使用 HashSet 和 HashMap？ 它们超级超级快。 空间哈希索引与 HashMap 的概念相同，但我们不是哈希对象，而是哈希它的位置并将其存储在单元格中（或“彼此靠近的事物桶”）。

让我们看看如何用 20% 的代码量将 QuadTree 替换为 SpatialHashIndex：

这种基本数据结构有很多变体，适用于不同类型的对象，但它们看起来都很相似。 我们基本上只是创建带有空间哈希的“buckets”，并用包含在由空间哈希表示的单元格中的任何对象填充它们。

空间哈希不太流行的原因是你需要小心选择单元格大小 - 这使得它成为一种知情算法。 如果你的单元格大小没有很好地校准，你最终将为每次检索支付高昂的固定成本。 在实践中，选择合理的单元格大小并不那么困难。

4. 有效的空间分区 + 缓存比算法性能重要 1000 倍

像 IPhone 内部的电路板可能在 10,000 到 20,000 条走线之间，并且需要一个团队花费几个月的时间才能使用世界上最好的 EDA 工具进行布线。 尝试优化如此极其复杂的任务似乎令人生畏 - 但事实是整个行业都在忽略一个非常简单的想法：已经布线的都已经被布线过了。

游戏开发者将导航网格“预烘焙”到游戏中，占用数 GB 的空间。 LLM 将整个互联网压缩成权重以进行搜索。 下一代自动布线器将对其问题进行空间分区，然后调用大量缓存来获取预先解决的解决方案。 当你拥有一个包含 99% 的自动布线问题预先解决的大型缓存时，算法的速度无关紧要。

今天的大多数算法都不关注有效的缓存可重用性或有效的空间分区，但未来自动布线器的一个关键组成部分将是以空间分区的方式缓存每个阶段的输入和输出。

此外，存储和缓存的大小下降速度似乎快于计算速度的上升速度。 拥有一个千兆字节的缓存来使你的自动布线器速度提高 50% 没什么大不了的。

归根结底，缓存将获胜。 可缓存的算法比快速算法更重要！

5. 如果你没有问题的可视化，你将永远无法解决它

如果有一件事我可以打印在海报上，那就是可视化问题。 你无法通过盯着数字来调试问题。

对于我们解决的每一个小问题，我们都有一个可视化。 我们通常会从可视化开始。 一次又一次地，这使我们能够以比其他方式快 10 倍的速度调试和解决问题。 这是我们为寻找 45 度路径的子算法制作的可视化，我们在自动布线器的约最后阶段“路径简化阶段”中使用它。

6. JavaScript 分析非常棒 - 使用它！

JavaScript 分析工具非常强大，你可以轻松地看到每行代码花费的确切总时间（以毫秒为单位）。 你不需要使用任何性能框架，只需在浏览器中执行你的 JavaScript 并调出性能选项卡即可。 还有很棒的功能，如火焰图和内存使用情况等。

调试 @tscircuit/core 中的性能的火焰图示例

你可以轻松地在 Chrome 的性能工具中查看每行代码花费的时间！

这是一个关于它的 youtube short

7. 永远不要使用递归函数

递归函数有多个原因不好：

• 它们几乎总是同步的（无法中断以进行动画处理）
• 它们本质上是深度优先搜索，并且无法轻松地转换为 A*
• 你无法轻松地跟踪迭代
• 可变性在递归函数中通常是不自然的，但对于性能至关重要

这是一个转换为非递归函数的“显式递归”函数的示例：

基于迭代的实现速度更快，因为它保留了一组 visitedNodes 并在探索之前检查节点。 你可以使用递归函数来做到这一点，但你必须传递一个可变对象并做其他不自然的事情。 在编写高性能代码时，最好避免使用递归函数。

8. Monte Carlo 算法是 hack，避免使用

Monte Carlo 算法使用随机性来迭代到解决方案。 它们不好，因为：

• 它们会导致非确定性的、难以调试的算法
• 相对于启发式方法，它们基本上永远不是最优的

有时，当我不知道算法应该如何得到解决方案时，但我知道如何对候选者进行评分，我会使用 Monte Carlo 风格的算法。 它们可以帮助你对如何解决问题有一些基本的直觉。 一旦你有了一些近似成本函数的东西，就做一些比 Monte Carlo 或任何其他随机技术（如模拟退火）更智能的事情。 如果你的算法对局部最小值敏感，请考虑使用超参数或更复杂的成本函数。 你用人眼可以看到的几乎任何局部最小值都可以作为成本函数的一部分。

另一种思考方式是：有多少 PCB 设计人员在他们的电路板上随机绘制线条？ 没有人这样做。 这对于这个领域来说不是一个好的技术。 你总是能够找到更好的启发式方法。

9. 保持中间算法的基础

我们的自动布线器目前是一个包含 13 个阶段的管道，大约有 20 个子算法，我们测量其迭代计数，以用于各种事情，例如确定空间分区或简化独立自动布线部分的边界处的路径。

能够覆盖算法每个阶段的不同输入/输出可视化有助于你了解解决问题的上下文。 我经常在下游阶段（通常是我们的“高密度布线”阶段）遇到问题，可以通过改进先前阶段的输出解决这些问题。

构建子算法的诱惑是将算法隔离到其最简单的形式，甚至可能围绕 (0, 0) 进行归一化。 归一化或任何复杂转换的危险在于，它可能会影响快速查看从算法的早期阶段到后期阶段的后果的能力。 为了防止这种情况，只需在算法的整个生命周期中保持你的坐标空间一致即可。

这是我们的算法的每个阶段一个接一个地进行。 我们经常放大它，以查看哪个阶段是设计规则检查失败的最严重的罪魁祸首。

10. 动画化你的迭代以捕捉愚蠢的行为

还记得降低迭代次数有多重要吗？

动画化算法的迭代会通过让你直观地了解有多少迭代浪费在探索无关紧要的路径上，来向你展示它有多“愚蠢”。 这在调整贪婪乘数（在 12 中讨论）时特别有用。

此视频是一个简单的走线未能解决的动画，但它没有直接失败，而是试图无休止地向外解决。 没有动画，很难说发生了什么！

11. 交集数学很快，你真的需要网格吗？

考虑两种确定走线 A 是否与另一条走线 B 重叠的方法：

1. 考虑 A 和 B 的每个线段，并检查交点1
2. 创建一个二进制网格，标记走线 B 所在的每个正方形，然后检查走线 A 所在的每个正方形以查看 B 是否在那里

信不信由你，大多数人会选择使用带有二进制网格检查的选项 2，即使这很容易慢 1000 倍。 人们这样做是因为数学很难 🤦

幸运的是，LLM 使这种交集数学变得微不足道。 使用快速矢量数学！！ 检查一个网格正方形（内存访问！）可能比做点积来确定两个线段是否相交慢！

12. 测量每个阶段的空间失败概率，优先考虑可解性

在对问题进行空间分区时，你可以使用一些领先指标来测量每个阶段的解失败概率。 例如，在 Unravel Autorouter 中，我们跟踪每个主要管道阶段中每个“容量节点”的失败概率。 每个阶段都侧重于重新配置相邻节点或重新布线以降低失败概率。

将失败概率作为度量的最大好处是你可以实际测量它并随着算法的变化改进你的预测。 然后，每个阶段都可以尽最大努力最大限度地减少未来阶段失败的机会。

我认为总的来说，优先考虑可解性比尝试纳入太多约束更好。 一旦解决了板，通常更容易“使用该解决方案”，而不是从头开始生成最佳解决方案。

13. “贪婪乘数”，以最优性为代价将 A* 性能提高 100 倍的秘密技巧

好的，它不完全是一个秘密，可能是一个“众所周知的秘密”，但如果你不知道它，你就没有正确使用 A*。

默认情况下，A* 保证为你提供最佳解决方案，但是如果你更关心速度而不是最优性怎么办？ 对你的 f(n) 做一个很小的改变，你就有了加权 A*，它是 A* 的一个变体，可以更贪婪地解决问题，并且通常更快得多！

普通 A*：f(n) = g(n) + h(n) 加权 A*：f(n) = g(n) + w * h(n)

你可以在此处阅读有关加权 A* 和其他 A* 变体的更多信息。

游戏开发者有很多与自动布线开发者相同的问题，所以如果你正在寻找相关工作，寻找游戏开发论文并不是一个坏主意！

我们正在制作一个自动布线器。

如果这对你来说很有趣，我很乐意在你发布自动布线器时向你展示我们的自动布线器。 我相信解决自动布线将为物理世界的创新带来巨大的解锁，并且是实现电子产品“共鸣构建”的关键部分。 我们所有的工作都是 MIT 许可的开源。 你也可以 在 Twitter 上关注我。

感谢阅读 autorouting！ 订阅以在发布我们速度极快的自动布线器时听到消息！

1

从技术上讲，你应该使用“线段到线段”的距离来确保适当的边距，这比交集稍微复杂一些，但差别不大