从狗腿布线到单元上布线：聊聊VLSI物理设计中那些有趣的布线算法（附图解）
芯片布线艺术的进化论：从经典算法到现代设计智慧
在集成电路设计的微观世界里，金属线的排布如同城市交通网络规划，既要确保信号准确到达目的地，又要避免线路间的"交通事故"。VLSI物理设计中的布线阶段，特别是详细布线（Detailed Routing），堪称芯片设计中最具挑战性的"精细活"。本文将带您穿越时空，从早期简单的通道布线开始，逐步探索那些巧妙解决复杂布线难题的经典算法，直至现代先进工艺下的创新布线技术。
1. 布线基础：通道与约束的艺术
芯片布线本质上是在三维空间（多个金属层）中寻找最优路径的数学游戏。想象一下，我们需要在有限的"土地"（布线区域）上规划无数条"道路"（金属线），而这些道路还需要在不同层之间通过"立交桥"（通孔）相互连接。这就是详细布线工程师每天面对的挑战。
1.1 通道布线的核心概念
通道布线（Channel Routing）是最基础的布线场景，通常出现在标准单元之间的水平通道中。这种布线区域的特点是只有上下两侧有需要连接的端口（引脚），左右两侧则是封闭的。就像在一条狭长的走廊两侧安装电线，我们需要遵循一些基本规则：
- 布线层规则：传统两层布线中，一层专用于水平走向（如Metal1），另一层专用于垂直走向（如Metal2）
- 设计约束：包括最小线宽、最小间距、通孔尺寸等工艺限制
- 电气约束：确保信号完整性，避免串扰和延迟问题
一个典型的通道布线问题可以用两个向量表示上下两侧的端口分布。例如：
TOP = [B, 0, B, C, D, B, C] BOT = [A, C, A, B, 0, B, C]其中字母代表不同网络，0表示该位置没有连接需求。
1.2 约束图：布线冲突的数学表达
布线中的冲突可以通过两种约束图来精确描述：
**水平约束图（HCG）**展示了哪些网络在水平方向上存在重叠，不能在同一轨道布线。构建HCG的关键步骤：
- 识别所有共享列的网络组合
- 为每个共享列的网络对建立无向边
- 合并冗余边形成最终约束图
**垂直约束图（VCG）**则描述了网络间的上下覆盖关系，是有向无环图（DAG）。VCG构建方法：
- 按列检查上下端口的网络关系
- 若上端口网络A覆盖下端口网络B，则添加A→B的有向边
- 消除传递性冗余边（如A→B和B→C存在时，省略A→C）
下表对比了两种约束图的特点：
| 特性 | 水平约束图(HCG) | 垂直约束图(VCG) |
|---|---|---|
| 图类型 | 无向图 | 有向图 |
| 边含义 | 网络不能共享轨道 | 网络上下覆盖关系 |
| 关键指标 | 最大团大小决定最小轨道数 | 最长路径影响布线顺序 |
| 循环处理 | 无循环概念 | 循环必须消除 |
提示：在实际布线中，垂直约束循环（VCG中出现环）是最棘手的问题之一，通常需要通过"狗腿"布线等技术来打破循环。
2. 经典算法解析：从左侧边到狗腿创新
2.1 左侧边算法：简洁而优雅的解决方案
左侧边算法（Left-Edge Algorithm）是通道布线中最经典的贪心算法，由Hashimoto和Stevens在1971年提出。其核心思想可以概括为："先到先得，能挤就挤"。算法步骤如下：
- 网络排序：按每个网络的左端点位置进行升序排列
- 轨道分配：从最上方轨道开始，尽可能多地放置不冲突的网络
- 迭代处理：对剩余网络重复步骤2，直到所有网络都完成布线
def left_edge_algorithm(nets): # 按左端点排序网络 sorted_nets = sorted(nets, key=lambda x: x.left) tracks = [] while sorted_nets: current_track = [] last_right = -1 remaining_nets = [] for net in sorted_nets: if net.left > last_right: # 无冲突 current_track.append(net) last_right = net.right else: remaining_nets.append(net) tracks.append(current_track) sorted_nets = remaining_nets return tracks该算法在VCG无环时能保证找到最优解（使用最少数量的轨道）。其优势在于：
- 时间复杂度仅为O(nlogn)，适合处理大规模问题
- 实现简单，结果直观易懂
- 为后续算法提供了基础框架
2.2 狗腿布线的革命性突破
"狗腿"布线（Dogleg Routing）得名于其布线形态——当网络需要在中间位置"拐弯"时，会形成一个类似犬类后腿的L形结构。这种技术由Deutsch在1976年提出，主要解决了两大难题：
- 垂直约束循环：通过将多引脚网络拆分为子网络来打破VCG中的环
- 轨道数优化：灵活的网络分段可以更紧凑地利用布线资源
狗腿布线的关键创新点在于：
- 网络拆分：将具有p个引脚的网络拆分为p-1个双引脚子网络
- 拆分策略：通常在中间引脚位置进行拆分，平衡各子网络的长度
- 混合布线：结合左侧边算法完成最终布线
下表展示了狗腿布线与传统方法的对比：
| 指标 | 传统布线 | 狗腿布线 |
|---|---|---|
| 处理循环能力 | 无法处理 | 可有效消除 |
| 所需轨道数 | 较多 | 减少15-30% |
| 布线复杂度 | 较低 | 中等增加 |
| 适用场景 | 简单通道 | 复杂通道 |
注意：虽然狗腿布线增加了灵活性，但也带来了额外的通孔（via）开销，这在深亚微米工艺中需要谨慎权衡，因为通孔会引入寄生电阻并影响良率。
3. 复杂场景扩展：交换盒与单元上布线
3.1 交换盒布线：四边受敌的挑战
交换盒（Switchbox）是比通道更复杂的布线区域，其特点是四边都有需要连接的端口。这就好比在一个十字路口的四个方向都需要布置交通线路，难度显著增加。交换盒布线的主要挑战包括：
- 端口密度高：四边都可能存在密集的端口分布
- 约束复杂：水平和垂直约束相互交织
- 解空间有限：布线路径的选择受到严格限制
解决交换盒布线问题的常见策略：
- 顺序扩展法：从最左侧端口开始，逐步向右、上、下方向扩展布线
- 区域分割法：将交换盒划分为多个简单通道分别处理
- 启发式调整：在冲突区域引入局部绕线或层切换
一个典型的交换盒布线示例如下：
左侧端口：A, B, C, D 右侧端口：E, F, G, H 顶部端口：I, J, K, L 底部端口：M, N, O, P在这种情况下，布线器需要综合考虑所有端口的连接需求，通常需要更多的金属层和更复杂的通孔结构来实现完整连接。
3.2 单元上布线：第三维度的解放
随着工艺进步，金属层数量不断增加（现代工艺可达10层以上），单元上布线（Over-the-Cell Routing，OTC）成为提高集成度的关键。OTC技术的核心优势在于：
- 资源扩展：利用高层金属（如Metal3及以上）在标准单元上方布线
- 面积优化：减少对专用布线通道的依赖，芯片面积可缩小15-25%
- 性能提升：更短的互连意味着更快的速度和更低的功耗
OTC布线的典型流程：
- 网络分类：识别适合OTC布线的长距离关键网络
- 区域规划：在单元上方分配布线资源，避开障碍物
- 层分配：根据网络特性选择合适的金属层
- 通道补充：在传统通道内完成剩余网络的布线
现代OTC技术已经发展出多种变体：
- 多层OTC：同时利用多个金属层进行立体布线
- 混合OTC：结合传统通道与OTC的优势
- 智能OTC：根据时序关键性动态调整布线策略
4. 现代挑战与创新解决方案
4.1 先进工艺带来的布线难题
随着工艺节点不断缩小（从28nm到5nm甚至更小），详细布线面临前所未有的挑战：
- 制造变异：线宽和间距的微小变化可能导致电气特性显著改变
- 多 patterning：多重曝光技术引入复杂的颜色分配问题
- 通孔可靠性：纳米级通孔的良率成为瓶颈
- 信号完整性：串扰、IR drop等问题更加突出
应对这些挑战的创新方法包括：
- 通孔冗余：对关键连接使用多个通孔提高可靠性
- 自适应线宽：根据电流需求动态调整金属线宽度
- 智能屏蔽：插入屏蔽线减少串扰影响
- 机器学习辅助：利用AI预测和优化布线方案
4.2 布线技术的未来方向
展望未来，VLSI布线技术可能朝以下方向发展：
- 3D IC布线：应对芯片堆叠带来的垂直互连挑战
- 光互连集成：在特定场景引入光学布线层
- 自修复布线：内置检测和修复机制提高可靠性
- 异构布线：针对不同功能区块采用定制化布线策略
在最近的一个7nm芯片项目中，工程师们采用了一种创新的"形状驱动"布线方法，通过动态调整金属线的形状（如采用波浪形边缘）来优化信号传输特性，同时满足严格的制造规则。这种突破传统曼哈顿结构（直角布线）的方法，展示了布线算法仍然存在广阔的创新空间。