2. 布线问题建模：网格图模型、线网模型、设计规则约束

好，咱们进入正题。布线问题，说白了就是把一堆需要连通的点，在芯片上找到合适的路径。但芯片不是一张白纸，上面有各种障碍、规则限制。所以第一步，就是要把这个物理世界，翻译成计算机能懂的语言——也就是建模。

我个人习惯，建模这一步花的时间，往往比后面跑算法还多。模型建得不好，后面算法再牛也白搭。咱们一个一个来看。

2.1 网格图模型：把芯片切成格子

想象一下，你手里有一张芯片的俯视图。上面密密麻麻布满了标准单元、宏模块、还有各种走线层。怎么让计算机去理解“哪里能走线，哪里不能”？

最直观的办法，就是切格子。

我们把整个布线区域，划分成一个个均匀的小方格。每个格子，要么是“空闲”的，要么是“被占用”的。这就构成了一个网格图（Grid Graph）。

嗯，这里要注意，网格的粒度很关键。格子太大，路径不够精细，浪费面积；格子太小，计算量爆炸。我记得在28nm项目上，我们试过0.1um的网格，结果跑一个模块的布线要三天三夜……后来改成0.5um，效果就平衡了。

网格图模型有几个变种，我简单列一下：

• 均匀网格： 最简单，所有格子一样大。适合标准单元布线。
• 非均匀网格： 在关键区域（比如引脚附近）用细网格，其他区域用粗网格。节省计算资源。
• 分层网格： 先粗粒度规划大方向，再细粒度局部调整。这是工业界的主流做法。

你想想看，为什么非均匀网格能省资源？因为大部分区域其实没什么障碍，粗网格就能搞定。只有那些引脚密集、障碍复杂的地方，才需要细看。

2.2 线网模型：从“点”到“网”

网格图搞定了“哪里能走”，接下来要解决“谁和谁要连在一起”。这就是线网（Net）的概念。

一个线网，就是一组需要电气连通的引脚集合。比如一个时钟信号要连到100个触发器，这100个引脚就属于同一个线网。

在建模时，我们通常把线网抽象成：

• 二端线网： 只有两个引脚，最简单。比如一个缓冲器的输入和输出。
• 多端线网： 三个及以上引脚。比如时钟线、复位线、数据总线。

对于多端线网，我们不会直接去连所有引脚，而是先构建一个斯坦纳树（Steiner Tree）。说白了，就是找一些额外的中间点（斯坦纳点），让总连线长度最短。

线网模型还有一个重要参数——线网权重。关键路径上的线网，权重高，布线时要优先保证它的延迟和拥塞。普通线网，权重低，可以绕一绕。

2.3 设计规则约束：不能越的雷池

模型建好了，线网也定义清楚了。但还不能直接跑算法。为什么？因为芯片制造有物理限制。你画出来的线，必须满足一系列设计规则（Design Rules）。

这些规则，说白了就是“线不能太细”、“线间距不能太小”、“通孔不能太小”等等。违反了，芯片就造不出来，或者造出来也是坏的。

我给大家梳理一下最常见的几类约束：

约束类型	具体内容	我的经验
最小宽度	金属线的宽度不能小于某个值（如0.1um）	电源线通常要加宽，否则IR Drop会出问题
最小间距	相邻两条线之间的间距不能小于某个值	同层金属间距比不同层要严格得多
通孔规则	通孔的大小、层叠方式、最小间距	我曾经因为通孔间距不够，导致DRC报了几万个错……
天线效应	长金属线在刻蚀时积累电荷，可能击穿栅氧	跳层走线或者加天线二极管可以解决
密度规则	每层金属的覆盖率不能太高也不能太低	这个在先进工艺（7nm以下）特别头疼

这些约束怎么融入到模型里？很简单：

• 在网格图中，把违反规则的格子标记为“障碍”。
• 在路径搜索时，检查每一步是否满足规则。
• 在拥塞评估时，考虑规则带来的额外绕线成本。

举个例子，如果最小间距是2个格子，那么一条线占用的，就不只是它自己那个格子，还包括它周围一圈的格子。这些格子对其他线网来说，就是“禁区”。

2.4 三者如何协同工作

好，现在三个模型都有了。它们不是孤立的，而是一个整体：

1. 网格图 提供了“地图”——哪里能走，哪里不能走。
2. 线网模型 提供了“任务”——哪些点需要连通。
3. 设计规则 提供了“交通规则”——怎么走才合法。

布线算法，就是在这张地图上，为每个线网找到一条合法路径，同时尽量让所有线网都能走通，不打架（拥塞）。

我个人习惯，在建模阶段就把这三者统一到一个数据结构里。比如，每个网格节点除了记录“是否空闲”，还要记录“被哪些线网占用”、“是否满足规则”。这样后面跑算法时，就不用频繁查表了。

下一节，咱们就聊聊，在这个模型基础上，怎么用迷宫算法和A*算法去找路径。到时候我会拿一个实际案例，带大家一步步走一遍。