【芯片设计】从RTL到GDS（九）：布线

这就是本篇文章将要谈论的主题，布线即Routing。

1、Introduction

大家可能会觉得，把该连的接口都连好不就行了。实际中可能没有这么简单粗暴，因为芯片的规模很大，有非常多非常多的门，因此也会有非常多非常多的连线，我们不光要连，还要连好。

我们来考虑两个东西，首先是几何复杂性，在布线过程中，通常使用网格表示法作为基本的出发点。但是在纳米尺度上，几何规则变得非常复杂。此外，集成电路中通常有多个布线层，每个层的“成本”（如制造难度、电阻、电容等）都不同，这增加了布线的复杂性。

然后是电气复杂性：仅仅连接所有电线是不够的。还必须确保电线中的延迟尽可能小，因为信号在传输过程中延迟过大会影响电路的性能。同时，还需要确保电线之间的相互作用（如串扰）不会干扰电路的行为。串扰是指信号在一条电线中传输时，无意中影响到另一条相邻电线上的信号的现象，这可能导致信号失真或错误。

我们把Routing这个问题细化一下，其主要包含以下几个要点。

问题：在给定的芯片布局（placement）和固定的金属布线层数的条件下，找到一个有效的水平线和垂直线的模式，以连接网的端点。

输入：单元位置，网表。单元位置指的是各个标准单元在芯片上的物理位置，网表则列出了所有需要连接的端点组合，即哪些端点属于同一个网。

输出：net的几何布局，即每个net在芯片上的实际布线图案，连接了各个标准单元。

两步过程：全局布线（Global routing）和详细布线（Detailed routing）。全局布线确定电线的大致路径，而详细布线则在这些路径上精确地放置电线。

目标：系统的100%连通性，即所有网都必须正确连接；最小面积，即在满足布线要求的前提下，占用最小的芯片面积；最短线长，即电线总长度尽可能短，以减少延迟和串扰。

约束条件：布线层数的限制，设计规则（Design rules），时序（延迟），串扰（Crosstalk）和工艺变化（Process variations）。设计规则定义了布线时可以采用的路径和间距等规则，时序约束要求电线的延迟必须满足特定的性能要求，串扰约束要求布线时要减小电线之间的相互干扰，工艺变化则要求布线能够适应制造过程中的不确定性。

2、Routing Algorithms

在了解了Routing的概念以后，我们来看以下Routing常用的算法，这里主要是从EDA工具的视角看，学习一下EDA工具背后的原理。下面的例子都是非常简化的版本，但对于我们的学习还是有帮助的。

在处理纳米尺度的集成电路布线问题时，尽管实际布线可能非常复杂，但为了简化问题，我们首先假设布线是在一个规则的网格上进行的。

在这个假设下，导线只能在网格的垂直和水平方向上走线，形成直角路径，这种布线方式被称为曼哈顿布线。网格中的某些单元可能被标记为障碍物，导线必须绕过这些障碍物。这样的简化假设有助于我们更容易地理解和计算布线问题，随着问题的深入，我们可以逐步引入更多的复杂性以更接近实际情况。

我们首先看一个算法，Maze Routers，其策略如下：

• 
  

• 一次布线一个net。

• 为当前net找到最佳的布线路径。

• 
  

存在的问题是：

• 
  

• 早期布线的net可能会阻挡后来net的路径。

• 对一个net的最优选择可能会阻塞其他net。

• 
  

该算法基本思路包括三个步骤：

• Expand（扩展）：从源点到目标点，以四个基本方向（上、下、左、右）扩展，寻找可行路径。这一过程通常使用广度优先搜索（BFS）或类似的方法来实现。

• Backtrace（回溯）：一旦找到目标点，通过标记的路径回溯到源点，确定最终的布线路径。

• Cleanup（清理）：在确认了布线路径之后，移除所有为了寻找路径而设置的临时标记，只保留最终的布线路径。

迷宫布线器的这种逐步扩展和回溯的方法，可以有效地找到从源点到目标点的路径，但是它可能会遇到早期布线网络对后续网络布线的阻碍问题。因此，在实际应用中，可能需要结合其他布线策略和优化算法来提高整体布线质量和成功率。

迷宫布线中的扩展（Expansion）阶段是布线过程的第一步，其目的是从源点开始，逐渐扩展到目标点，寻找所有可能的路径。这个过程可以描述如下：

• 
  

• 从源点开始，寻找所有与源点相邻的、可达的单元格（即没有被障碍物占据的单元格）。

• 以这些单元格为新的起点，继续寻找它们相邻的可达单元格，如此类推，不断扩展。

• 这个过程一直持续，直到达到目标点。

• 
  

在扩展过程中，我们可以想象一个“波前”（wavefront）从源点向外扩散，逐渐接近目标点。这个波前代表了布线过程在网格中扩散的边界。当我们到达目标点时，我们就可以确定从源点到目标点的最短路径。在这个例子中，我们找到了一条最短路径，它包含6个单位步骤。这意味着从源点到目标点的路径长度是6个网格单元。

需要注意的是，迷宫布线算法在扩展过程中可能会找到多条路径到达目标点，但在回溯阶段，我们通常会选择其中一条最短的路径作为最终的布线路径。

在迷宫布线过程中，一旦扩展阶段找到了从源点（S）到目标点（T）的路径，接下来就会进行回溯和清理阶段。

回溯阶段：

• 
  

• 回溯是指从目标点开始，沿着路径长度递减的顺序反向追踪。

• 这样做可以标记出一条到目标点的最短路径。

• 通常情况下，可能存在多条同样长度的最短路径，这时可以采用优化策略来选择最佳路径。例如，可以根据路径的直线性、拐角数量或与其他网络的干扰程度来决定。

• 
  

清理阶段：

• 
  

• 当第一条网络布线完成之后，为了确保未来的网络不会尝试使用同一条路径，需要将这条从源点到目标点的网络路径标记为障碍物。

• 这样，当其他网络进行布线时，就不会考虑已经占用过的路径，从而避免了资源冲突。

• 
  

通过回溯和清理，迷宫布线器为每个网络逐一找到并确定了最佳的布线路径，并为后续网络的布线做好了准备。这个过程需要重复进行，直到所有的网络都完成了布线。

在迷宫布线中，处理障碍物（blockages）的方法就是简单地“绕过”它们。具体来说，当布线算法在扩展（Expand）阶段遇到障碍物时，它会忽略障碍物占据的单元格，继续在其余可用的单元格中寻找路径。这样做可以确保布线不会穿过障碍物，而是围绕它们进行。

总结一下处理障碍物的方法：

扩展（Expand）阶段：使用广度优先搜索（Breadth-First Search, BFS）来按路径长度顺序找出从源点（S）到目标点（T）的所有路径。在这个过程中，障碍物被视为不可通过的单元格，布线算法会自动避开它们。

回溯（Backtrace）阶段：一旦找到目标点，算法会沿着最短路径回溯到源点。这个过程会标记出一条避开所有障碍物的最佳路径。

清理（Cleanup）阶段：在确认了布线路径之后，将这条路径标记为障碍物，以防止后续网络使用相同的资源。同时，擦除在扩展阶段留下的距离标记，为下一次布线做准备。

通过这种方式，迷宫布线算法能够有效地处理集成电路布线中的障碍物问题，确保每个网络都能找到一条合适的路径，并且不会与其他网络发生干扰。

对于具有多个目标点的网络（Multi-Point Nets）进行布线时，处理方式相对直接。以下是解决多目标点网络布线的步骤：

初始布线：使用常规的迷宫布线算法（maze routing algorithm）找到从源点到最近目标点的路径。在这个阶段，我们只关注一个目标点，并找到到达它的最短路径。

重新标记：一旦找到了到达第一个目标点的路径，我们将路径上所有的单元格重新标记为源点（sources）。为什么可以这么做呢？因为这时候这几个单元格从电路上来讲，是等电位的，我们认为其电气信息是一样的。这样做的目的是为了将已经布线的路径转换为新的布线起点，以便于为其他目标点布线。

重复布线过程：使用所有新的源点同时作为起点，再次运行迷宫布线器。这一次，布线器会尝试找到从这些新的源点到剩余目标点的路径。这个过程可能会重复多次，直到所有的目标点都通过路径与源点相连。

通过这种方式，多目标点网络的每个目标点都会通过一条独立的路径与源点相连，而这些路径之间不会相互干扰。这种方法确保了每个目标点都能够有效地连接到源点，同时保持了布线的效率和合理性。

下面是上述方法的一个具体流程，解释的很清楚。

上述方法找到的并不是最优路径，而是基于启发式算法的一个局部最优解，全局最优路径有一个名称叫做Steiner Tree。找到这个路径是一个NP-hard问题。

我们已经讨论了单个Layer的布线问题，对于Multi-layer呢？首先我们看几个Multi-layer的图片。

怎么解决？此时我们要定义新的扩展方向，up/down。通过通孔去连接。

下图是涉及到两层的Source到Target。

对于通孔而言，其电阻相对较高，按理说我们应该尽可能的在同一层布线。我们也倾向于使用曼哈顿布线，对于每一层的导线将只沿一个方向布置，比如某一层只进行水平布线，而另一层只进行垂直布线。这种方式有助于减少导线之间的交叉和干扰。在布线过程中，如果需要改变方向，通常需要通过通孔到另一层进行，或者在同一层内进行曲折（jog）布线。由于这两种情况都会增加布线的复杂性和电阻，因此算法会对此类操作进行惩罚，以鼓励更直接的布线方式。

基于non uniform grid costs惩罚机制，有助于实现上述的要求。

比如下图中，对于Metal1，我们只希望水平布线，如果竖直布线成本将是10。而Metal2与之相反，经过Via，也会有额外的成本为10的开销。这样我们可以基于Non uniform grid cost的方式找到想要的路径。

实现这样的布线算法需要高效的算法和数据结构。对于如此巨大的网格（例如一个1cm x 1cm的芯片，100纳米的轨迹，10个布线层，总共1000亿个网格单元），我们需要一种低成本的表现形式来处理这个问题。以下是如何实现这个算法的步骤：

1. 低成本的表示法：由于网格巨大，我们不能存储每一个网格单元的详细信息。相反，我们只存储波前，即当前正在处理的边界区域。这样可以大大减少内存的使用。

2. 记录已到达的单元格：我们需要记录哪些单元格已经被访问过，以及到达这些单元格的成本和来自哪个方向。这样可以帮助算法避免重复访问单元格，并确保找到最便宜的路径。

3. 使用Dijkstra算法：Dijkstra算法是一种图搜索算法，用于找到从起点到其他所有点的最短路径。在这个场景中，我们可以使用Dijkstra算法来找到成本最低的单元格。

4. 数据存储在堆中：堆是一种特殊的数据结构，可以有效地找到最小元素。在这个算法中，我们可以使用最小堆来存储和检索到达每个单元格的成本，以便我们可以快速找到下一个成本最低的单元格。

具体实现步骤如下：

• 初始化一个最小堆，用来存储所有可访问的单元格及其对应的成本。

• 将起点添加到堆中，其成本为0。

• 当堆不为空时，执行以下步骤：

• 从堆中移除成本最低的单元格。

• 对于该单元格的每个邻居，计算到达该邻居的成本。

• 如果邻居未被访问过，或者找到了一条更cheap的路径，则更新该邻居的成本和方向，并将其添加到堆中。

• 当算法到达终点时，回溯已记录的方向，以找到从起点到终点的最优路径。

在实际的EDA布线中，还需要考虑其他因素，如布线层的方向性限制、通孔的成本、布线层的容量限制等。这些因素需要在算法的成本计算和决策过程中被考虑进去。

对于大芯片，常常采用分治策略，先Global Routing再Detailed Routing。我们将一个芯片分成一个个的大格子，这个大格子我们叫做GBOX。Global Routing基于大格子先粗略确定每个格子到每个格子的入口和出口。其内部的细节先不管。

完成以后再对格子内部的连线确定细节，这一步叫做Detailed Routing。

就比如我们有了第一个Box内部的source和target。我们的Detailed Routing就是确定这个一个个Box内部的连线。

3、Routing in Practice

在上面的介绍中，我们用了很EDA的视角去看布线，接下来我们从更加电路的视角去看布线。

我们可以看到随着工艺节点的提升，Layer的层数也在增加。对于早期的工艺，我们可以看到其尽管有很多层，但是每一层都是一样的，因此DRC规则中，最小间距和最小宽度将会保持一致。

随着工艺的推进，我们需要厚度更加厚的金属层，从而减少RC值并提高更好的电源布线。较低的金属层主要用于局部互连，中间层可能用于时钟或者更长的全局布线，顶层主要用于电源连接。

右边是两个实际的例子，我们可以看到UMC的六层金属堆叠和英特尔的8层金属堆叠明显不一样。可以看到8层金属堆叠明显有几种不同厚度的metal layer，不同厚度的metal layer用于做不同的事情。

我们接着探讨一下EDA工具内部的实际路由过程是如何进行的。正是由于上述的金属层变化的问题，会让我们的布线问题变得更加困难。文章上面讲过的布线算法也会变得复杂起来。

我们从全局布线开始考虑，全局布线将整个芯片的布局划分为多个GCell（Global Cell），每个GCell代表了芯片上的一块区域。全局布线的目标是为芯片上的各个连接提供初步的路径，这些路径将在后续的详细布线（Detailed Routing）阶段被细化。以下是全局布线的一些关键特点：

将floorplan划分为GCells：全局布线首先将芯片的布局（floorplan）划分为一系列的GCell。每个GCell包含了一定数量的布线资源，如导线轨道。在每个布线层上，每个GCell大约包含10个导线轨道。这些轨道用于连接芯片上的不同模块。轨道有Minimum Width和Minimum Spacing属性，具体的可以看图。这个是用于满足DRC约束的。

全局布线的目的是执行快速的网格布线：全局布线使用一种快速的网格布线方法，这种方法在GCell网格上为信号提供路径。

• 
  

• 最小化线长：全局布线试图找到连接各个模块的最短线路，以减少信号的延迟和功耗。

• 平衡拥堵：布线时需要考虑不同区域布线资源的利用率，避免某些区域过度拥堵，而其他区域则空闲。

• 时序驱动：全局布线考虑信号的时序要求，确保信号能够在规定的时间内到达目的地。

• 噪声/信号完整性驱动：布线时还需要考虑信号完整性和噪声的影响，避免由于布线不当导致的信号退化。

• 保持总线在一起：对于总线（一组并行信号线），全局布线会尽量将它们保持在一起，以便于后续的详细布线和信号完整性分析。

全局布线完成后，将生成一个布线图，该图显示了芯片上各个连接的大致路径。这些路径将在详细布线阶段被进一步优化和实现，以满足电路的性能和制造要求。

比如在下图的右上角，我们在完成Global Routing以后，就可以知道哪些地方是Congested Area了。

通常在完成全局布线的时候，我们将使用congestion map展示较高拥塞的区域。然后就要进行布局规划的迭代过程，针对这些区域进行修正。如果存在这些大规模的拥塞区域，最好不要继续进行detailed routing，而是返回去修正布局规划，否则对后续的布线非常困难。

完成了全局布线的迭代以后，就可以进行Detailed Routing。我们将逐个的处理Gbox。之前的Global Routing是非常粗略的GBOX和GBOX之间的连接。

我们不是已经对每个GBOX都设置好相应的轨道了吗？我们现在就是确定GBOX内部之间，是怎么根据这个轨道连接的。这个内部的Routing，我们也要考虑下面这几个因素。

我们再来看看时间驱动布线，这是什么意思呢。其主要是尝试对关键路径进行优化，如果系统仍然存在时序问题，通过布线的方式可以进行一定的优化，对关键路径采用最短的路径，以减少延迟。

我们需要采用权重的方式，给不同的Net分配不同的权重，比如说这个Net比其它Net更加重要，工具要有限对其进行布线，尽可能不要经过Via，不要拐弯。

我们接着看看信号完整性问题。布线之所以会导致信号完整性问题，主要是串扰问题。一个信号的切换可能会影响附近的net，导致其上出现毛刺或其它信号问题。我们称切换信号的net为Aggressor，被影响的net为Victim。

有两个主要的影响，当攻击者上升的时候，Victim正在下降，这个串扰问题导致其下降变缓慢了，我们看图可以看出来，它又重新升了一会，才下降。这导致了信号变化的Slow Down，与之类似的还有信号变化的Speed Up。

这实际上是由互耦电容引起的，我们要保证电容值不会过大，以避免串扰引起的毛刺或其它问题。

在比较旧的工艺中，会采用无限噪声窗的方式分析这个互耦电容产生的影响。但随着工艺的提升，导线之间的间距日益缩小，交叉覆盖面积增大，侧壁电容增加，导致了极端情况的出现。比如Net B在考虑最大延迟的时候显著减速，最小延迟的时候显著加速。（其实到这里我就看不懂了，有懂的大佬可以详细解释一下）

为此一种新型时序分析方法被提出并被整合进了EDA工具，称为传播噪声分析。传播噪声分析是一种更为精确的方法，它考虑了实际信号波形的变化。在这种分析中，会使用设计中的最小和最大信号向量来模拟干扰源和受害线之间的相互作用。通过这些向量，可以为每个干扰源相对于受害线创建一个时间上的过渡窗口。这个窗口代表了干扰源可能对受害线产生影响的时刻。噪声只在干扰源的过渡窗口和受害线的敏感窗口重叠时才被考虑，这样可以更准确地确定由多个干扰源引起的最坏情况下的噪声尖峰。

我们看一下怎么解决信号完整性问题，防止串扰的首要措施是限制平行net的长度，如果由两条net平行，通常应该增大它们之间的间距。还要考虑屏蔽特殊net，如果有特殊net，可以在中间放置一个屏蔽层，这样可以大大减少net之间的交叉耦合。对于Victim，可以扩大其Size，这样平均下来交叉耦合效应的影响就会降低。

我们看几个例子，下面的四个例子分别采用了增加空间，调换顺序，添加屏蔽层，重新排序形成隔离屏障的方式优化串扰问题。

另一个问题就是所谓的可制造型涉及，即DFM问题。我们通过添加额外的方法以提高良率，降低特定芯片出现缺陷的风险。方法包括但不限于：

Via reduction：目的：减少过孔（Via）的数量可以降低制造复杂性，减少潜在的缺陷点，提高良率。方法：通过优化布线策略，比如使用更有效的层间连接方式，或者合并多个相邻的过孔，来减少过孔的总数。

Redundant via insertion：目的：插入冗余过孔可以提高电路的可靠性，因为在制造过程中某些过孔可能会失败。方法：在关键信号线上添加额外的过孔，确保即使某些过孔出现问题，信号仍然可以通过其他过孔正常传输。

Wire straightening：目的：直线的布线可以提高制造的准确性，减少布线错误，降低信号完整性问题。方法：尽可能使用直线的布线方式，减少不必要的弯曲，这样可以降低布线的电阻和电容，提高信号质量。

Wire spreading：目的：线展开可以减少布线之间的相互干扰，降低串扰，提高信号完整性。方法：在布线时，尽量增加线与线之间的距离，特别是在高速信号线上，这样可以减少电磁干扰，提高电路的性能。

我们看下面这个图，Wire straightening把本来是拐弯了几次的线给他拉直了。另外一个例子是，我们有一个晶体管，有两个彼此对称的接触点，但不是完全对称，这可能导致较高的制造缺陷风险。通过增加两个额外的接触点，让其变得更加对称。

我们直接看两个例子：

我们看一下Innovus中Routing怎么做（Encounter就是之前的名字，现在已经改名Innovus了）。可以看到使用工具比知道工具细节简单的多，这就是抽象的力量。

系列文章入口——