【芯片设计】从RTL到GDS（七）：布局

阅读模式 · 发表于 2024-10-9 12:02:00

本篇文章将继续讨论芯片的Physical Domain，在完成Floorplanning以后，我们需要将视野放在Placement上。
接下来正式进入课程内容：

本节课的课程大纲如下所示：

1、Introduction

我们之前就已经完成了逻辑综合，在逻辑综合之后，我们有了映射在具体工艺上的网表即netlist。

在Floorplanning之后，大概确定了各个大的Block放在哪里，芯片大致的布局。

我们的Placement实际上就是在Floorplanning的地基之上更进一步的布局，把我们剩下的Standard Cell全部摆放好。

在开始进行Placement之前，我们先考虑一下芯片的大小问题。比如说一个1亿门的芯片到底有多大？在实际的芯片设计中，small cells才真正占据面积的主导。对于大的hard macro，我们将其视为很多很多的小门。
因此通常我们将芯片的大小看成等效的门数量，并且是最简单的二输入与非门的大小。也就是可以简单认为绝对面积/与非门的面积=门的数量。这里还需要搞清楚Gates和Instances两个不同的概念。Instances是实际被Placed的东西，包括但不限于1-bit加法器，D-flip flop，稍微复杂一点的门，最基本的门等等。Instances的数量大概是Gates数量除以4到除以5这个范围区间。

通过下图，我们可以看到Placement的输入输出，以及其想达到的目标。其本质就是在不违例，尽可能优化的情况下，给gate找个地方放下来！听上去很简单，实际上很难。不好的Placement会导致有非常多的连线，连线过多会导致阻塞问题，寄生参数问题，芯片面积问题，时序问题等等。布局不好的话会让下一步的时钟树综合以及布线也非常困难。所以布局作为承上启下的一个阶段，其非常重要。

通常来说，大部分EDA工具会将Placement任务划分为两个阶段：Global Placement这个阶段的目的是快速地将设计中的所有单元分配到芯片上的各个区域或“箱子”中，目标是尽量减少不同区域之间的连接数量，同时考虑到整体的布局密度和平衡；全局布局通常不会关注每个单元的精确位置，而是关注于整体布局的框架和结构；这个过程中，主要的元器件的位置是“浮动”的，可以“平滑”地在版图上移动；Detailed Placement在全局布局的基础上，详细布局的任务是为每个单元实例提供一个合法的位置；这个阶段会尽量减少连线长度，优化电路的性能，如减少信号延迟和功耗；同时，详细布局还会尝试确保布局后的设计不会出现过度的拥挤，即避免出现布线拥塞问题，这会影响最终的布线质量和信号完整性。根据下图我们可以看到一个好的Placement和一个不好的Placement的差别有多大。其互连线长度差距非常大。

为什么我们需要在Placement阶段重点关注wire的长度呢？这就有点像综合重点会关注时序，明明后续有静态时序分析工具。布局也是类似的，其需要为后续的router服务，其一般内部有一个简化版的router估计工具，其目的最核心的在于没有违反电路规则的情况下，最小化互连线的长度。这也是Placer最核心的出发点，其基于这个出发点进行布局。并且这种涉及方法学和逻辑综合的静态时序分析方法一样，都是将一个复杂的电路玄学问题，转换为有迹可循的数学优化问题，通过合理的抽象，我们能把非常难分析的问题变成相对容易解决的数学问题。这也是很多EDA工具的核心理念。

2、Random Placement

随机布局（Random Placement）是一种在芯片设计中进行初始布局的简单方法。在这种方法中，设计中的各个单元（如标准单元、宏单元等）被随机地放置在芯片的可用区域上，而不考虑它们之间的任何特定关系或连接。在此基础上进行随机的交换，从而最小化wire长度。

来看一个非常简单的例子，通过这个例子我们大概了解Placement到底在做什么。假设我们有一个非常简单的网格。所有的gate大小都相同，网格的每个格子可以放一个gate。实际的布局没有这么简单，但这个简化的例子有助于我们理解布局。

在具体布线（Routing）之前，我们在布局阶段就需要评估布线时的走线长度或者时序质量的。因此我们需要有这些指标的高效估计模型（总不能更新一下布局又完全重跑一次布线吧）。对于线长这个问题，我们需要分成两步骤进行分析：（1）首先，我们要猜这个线可能长什么样子；（2）然后，我们要可以在我们的问题模型中，数值化地反映出这个线长。我们先假设，所有的电路中的网线（net）都是只有一个驱动引脚，但可以有多个被驱动的fanout引脚，当然每个引脚有其所属的电路实例。其次有个前提，在VLSI中，走线都必须是XY两个方向的，也就是不能像散落的绳子一样，随意拐弯。这里还需要说明一下，Net到底是什么，在layout中，我们把线叫做net，这些线是netlist的一部分。netlist就是映射在具体工艺上的gates+wires。我们根据这些net连接了多少个东西，称其为“x-point net”。比如下图中的2-point net和4-point net。

针对第一个步骤，即猜线长什么样子。在布局中，我们会用一些布线模式去近似实际布线器的走线。如下图所示，同样是4-point net。其形式可以多种多样。

常见的近似布线模式有：半周线长（half-perimeter wirelength ，HPWL)，也叫做Bouding Box(BBOX)。HPWL只关心最上下左右的边长，主要特点是简单、评估快、和实际布线长度误差10%左右。其核心思想在于找一个最小的矩形框，把所有的point给包住，基于这个矩形框，我们就可以评估相应的net长度了。

我们看一下怎么通过HPWL参数估计wire length。第一个例子中总共只有两个gate，它们的△X=2，△Y=3。则HPWL等于2+3=5。同理，在右下角这个4个gate例子中，我们找最远的△X和△Y。则相应的HPWL为3+4=7。

有一点需要提一下，HPWL是实际Wire length的下界，也就是我们至少要按照这个长度去估计。毕竟我们根据上面的图就可以看出来，你找不出比这个更加理想的连接方式了（只能沿着X和Y扩展，HPWL没有走任何多余的路）。

好了，我们已经有了基本的连线了，如何基于这个基础去优化呢？这就问的好了，我们先考虑一个简单的算法，随机的去优化。下图中的算法很简单，这里就不详细讲了。简单来说我们就是不断的更换Gate，使得整个的L变少。

我们来看一个具体的例子，两个Gate是怎么交换的。图片这里不是水平或者竖直方向的其实不太合理，大家简单理会其意思即可。

这种方法有什么缺点呢？我们可以看到其很容易陷入局部最优解。除非使用全局遍历的方法，但这样开销成本又太大，有什么好方法呢？

我们可以使用模拟退火算法（Simulated Annealing）优化上述过程，基于模拟退火算法，不断随机的更换gate的位置。有关模拟退火算法的细节，大家可以去找相关资料，这里就不讲了。

3、Analytic Placement基于模拟退火算法的优化思路比较古老了，目前比较先进的方案是基于解析模型（Analytic model）进行数值求解的。因为解析模型可以：（1）很清晰地把问题建模评估与扩展；（2）可以更好地跳出局部最优点；（3）可以充分利用数值求解工具的强大并行化计算能力，提高求解速度。

基于解析的布局方法具体思路如下所示。现代的布局器都是基于解析布局方法的。我们需要以数学上友好的方式写出成本函数，然后我们可以对其求导并令其等于0，从而找到最小值。简而言之，解析布局方法是将布局问题转化为一个数学优化问题，通过求解成本函数的最小值来确定电路元件的最佳位置。这种方法的关键在于将成本函数表达为电路元件坐标的函数，并利用数学工具（如微积分）来找到这个最小值。

由于HPWL的数学表达式是不可导的，在数学求解器里面，不可导通常是不利于求解的，因此我们需要用可导函数去近似这个真正的HPWL。比较典型的是二次（Quadratic）近似。对于两个point的“net"，非常容易计算。

但是当point大于2呢？此时将使用clique model。这种模式下实现了一对一的连接。最后一点假设是，假设门电路是没有维度的点。

此外为了补偿这种模型的偏差，我们可以通过将每个新网络的权重设为1/(k-1)来进行调整。

我们来看一个简单的例子。每个gate的坐标未知，每个net（线）有具体的权重，边缘PAD的位置固定。

可以看到x和y是没有互相运算的。我们分开计算。

如下图所示，我们利用导数，求得相应的局部最优解。

我们可以得到一个很直观的结果，使用二次线长模型进行布局时，电路元件（点）会被放置在一条直线上，这样的布局可以最小化弹簧权重，即权重较大的连接会有较短的线长。这种方法可以有效地减少总体的线长，从而优化电路的性能。

我们基于下面的说明，构建解析网络：

直接看个例子：

上述的方法其实存在一个问题，什么问题？所有的门电路都想要放在同一个地方！这种现象英文叫做Gate Clustering。上述现象这是很自然而然能看出来的，我们如何解决这个问题？通过递归Partitioning！递归Partitioning是一种层次化的布局方法，它将整个电路分成多个子部分，然后对每个子部分进行单独布局。这些子部分可以进一步划分，直到每个子部分的大小和复杂性适合进行有效的布局。这种方法可以避免所有门电路聚集在一起的问题，并且可以在不同的层次上优化布局，以减少总体的线长和提高电路的性能。

递归Partitioning思路如下所示，大家直接看图就行。更加细节的东西需要自己搜索相关资料，这里大家搞懂基本概念就行。

我们再讨论一下合法化的概念，在实际的布局中，我们需要各类实例都映射到实际板子上的离散的位置上。比如某个实例Q的XY坐标是(1.3, 5.2)，它就需要被映射/对齐到如(1，5)这些离散位置。在ASIC上，可能只有某个维度需要进行对齐，如对齐到行（Row）只需要变成（1.3,5）坐标就好了。

4、Placement in Practice之前我们讨论的都是基于wire-length最小化优化目标。布局实际上还要考虑时需优化和阻塞最小化。以及后续的时钟树和功耗优化。

我们看一下基于时间驱动的布局，其尝试将关键路径相关的Cell放的很久，从而减少相关的RC参数，其减少了，需要的充放电时间也会得到改善，可以优化时序。这里还涉及虚拟布线的概念，大家感兴趣的可以搜索相关资料。

我们看一下其前后的变化：

我们再把视角放回Congestion，中文一般叫做阻塞问题或者拥塞问题。之所以会出现这个问题，简单理解就是路径不够用了！因为某些实例它的连线太多太密集了，如果在它旁边摆满其他人，就没位置走线了。这就像一些旧城区改造，小楼太多了，中间马路穿来穿去经常堵车，因此通常就是拆迁，扩大楼距和路宽。

对于基于Congestion驱动的Placement，会尽可能减少wire length通道数的密度，比如下图中的例子，其交换了A和D两个Cell。这样交织的线就变少了（Wire length Channel Density从3变成了2）。但是整体的长度增加了，因此这也是一个需要权衡的问题。

我们来看一些修理Congestion的方法。

我们看一下Innovus工具中，怎么进行Placement，可以看到其非常人性化。很多时候我们不需要了解细节，也可以完成工作，这就是抽象的力量。

下篇文章讲时钟树综合。最近同时也在看EDA相关的资料，这个系列的文章可能整体会再补充的更加详细。

系列文章入口——

【芯片设计】SoC 101（一）：绪论