VLSI记录

物理设计流程

布局规划是物理设计的基础，它决定了布局和布线的结果。集成电路的布图模式按照模块的定义可以分为标准单元设计模式（Standard Cell Design Style）、门阵列设计模式（Gate Array Design Style）、门海设计模式（Sea-of-Gates Design Style）、现场可编程门阵列（Field Programmable Gate Array，FPGA）和全定制模式（Full-customDesign Style）。全定制模式中主要有交互图形编辑、符号版图设计方法和积木自动块布图（Block Building Layout，BBL），BBL 模式如图2.4 所示。在BBL 模式中，模块可以以任意形状放置在需要的位置，对布线区域的限制较少，更接近人工设计方法，可以应用在自动化设计中。

布局规划的目的是确定模块在芯片上的最佳位置和最小化芯片总面积，并保证模块之间的连接满足约束，优化标准主要是导线长度、时间延迟、功耗和温度。

布线问题可以分为全局布线和详细布线两个阶段，首先在全局布线阶段为每个区域生成粗略的布线，然后在详细布线阶段为指定的布线区域建立实际的几何布局。

全局布线

全局布线的目标是给出线网的大致走向而不会给出具体的走线结果，它是详细布线的基础。全局布线的质量影响芯片的时序、功率和密度，因此全局布线是物理设计中非常关键的阶段。

为了避免线网排序问题并使解决方案可以预测，以整数规划模型形式的基于并发的全局布线算法被开发出来，此类算法可以同时对所有线网布线。在数学规划的方法中，全局布线被公式化为0-1 整数规划问题，将它与斯坦纳树问题相结合，解决问题的目标是从斯坦纳树集合中找到一个既满足布线要求又最小化布线成本的斯坦纳树。

详细布线

在BBL 布图模式中，详细布线需要对布线区域进行划分和排序。详细布线可以看作一个规划问题，总体目标是实现所有线网的连接，子目标是连接每个线网的所有引脚。这些子目标相互依赖，相互竞争资源。子目标的顺序可以由线网重要性和区域内线网数量确定。

布线模型

布线问题使用的模型一般分为有网格模型和无网格模型。有网格模型：

无网格模型没有网格作为路径搜索的依托，它需要先通过一些方法预先找到布线区域可以使用的节点。

对单层布线来说，设布线平面为𝑅，布线区域的障碍为𝑂，则𝑂 = {𝑂1, 𝑂2, ..., 𝑂𝑘}组成了非布线区域，𝐺 = 𝑅 − 𝑂 为可布线区域。设𝑠 为布线起点，𝑡 为布线终点，线网端点集合为𝑉 = (𝑠, 𝑡)，如果可布线区域𝐺 中存在子集𝑆，满足𝑠 和𝑡 可以在𝑆 中连通，即𝑆 中存在至少一条𝑠 到𝑡 的路径，则称𝑆 为𝑉 的连接图（Connection Graph）。在𝑆 中找到𝑠 到𝑡 的最短路径，那么𝑆 为𝑉 在𝐺 中的强连接图𝑆𝐶（Strong Connection Graph）。在曼哈顿架构中，两个点(𝑥𝑖, 𝑦𝑖) 和(𝑥𝑗, 𝑦𝑗) 之间的距离是用曼哈顿距离𝑀𝐷 描述的，即𝑀𝐷 = |𝑥𝑖 − 𝑥𝑗| + |𝑦𝑖 − 𝑦𝑗|。如果知道两点的坐标，那么两个点的距离就可以计算出来。如果布线区域没有障碍的话，两点间的最短路径就等于两点间的曼哈顿距离；如果布线区域有障碍的话，可以用障碍和线网端点构造布线的路径图，以此实现简化问题、节省存储空间和提高布线速度的目的。

在一个布线区域中，给定线网端点集合𝑉 = (𝑠, 𝑡) 和障碍𝑂 = {𝑂1, 𝑂2, ..., 𝑂𝑘}，其中障碍不会相互重叠且障碍的边由水平和垂直线段组成。双端布线问题可以看作是在一定约束条件下寻找两点之间最优路径的问题，约束条件可以是路径长度最短、拐点数最少或者距离和拐点数目组成的成本函数的值最小。如果只约束路径长度，则称为最短路径问题（Shortest Path，SP）; 如果只约束成本函数的值，则称为最小费用路径问题（Minimum-Cost Path，MCP）

G的形成：并不按照传统的网格方法，会加大空间搜索并且生成的结果会很奇怪，如果减少网格的边长则会使距离搜索空间变得很大。因此采用如下方法，基于图中所有障碍物（已确定布局的子系统矩形模块或其他障碍）生成对应的网格线。

此外，如果是BHS的设计，s和t会位于矩形子系统的四周边上，对于这种起点或终点则直接做垂直于该点所在边的射线作为其外连接线入口。

布线问题的目标是使总路径代价最小，路径的总成本由路径长度和路径中拐点的代价构成：

𝑓_𝑘 = 𝛼×𝑙_𝑘 + 𝛽×𝑣_𝑘

其中，𝑓𝑘 为线网𝑘 的成本函数，𝑙𝑘 为线网𝑘 的路径长度，𝑣𝑘 为线网𝑘 的拐点代价函数，𝛼和𝛽 分别为路径长度和拐点代价函数的权重且𝛼𝑙, 𝛽𝑣 ⩾ 0。解决布线问题的目标就是使𝑓𝑘 的值最小。

双端布线

在VLSI中，双端布线是指在设计芯片时需要将电路网格化，并将芯片布线分配给两个端口（输入和输出）。因为芯片中的电路连接非常复杂，由于硅片有限的空间和阈值电压的限制，因此对于大型芯片，必须将电路划分为几个电路板或模块。在每个板或模块上，需要将电路分配到设计的输入和输出端口。优化双端布线问题的目标如上所示。

多端布线

多端布线问题需要连接两个以上的节点，它不能简单分解为多个双端布线的组合，多端布线的优化目标不再是两点间线路最优而是整个线网保证多点连接情况下的总线路最优。在搜素过程中，可以从不同端点出发，比较不同路径找出最优解。当布线空间已经存在导线时，其线宽和线距占据的空间会影响到其他端点的连接过程。

在曼哈顿架构下，多端线网布线可以转化为寻找该线网的MRST 问题。解决多端布线问题时可以在已布好的线路当中选中一点作为源节点，在未布端点集合中选择一点作为目的节点，多端布线的每一步都由双端布线来实现。

多组布线

在多组布线中，每组线网端点数目可能是两个也可能是多个，根据每组线网端点数目的不同，可以用双端布线或者多端布线实现。在多组布线问题中，线网的先后顺序是很重要的。各组线网布线的优先级顺序对布通率以及全局布线路径的影响作用是相当大的，在实际操作中可以通过动态调整优先级来保证100%布通率。

对于不同类型的线网，线宽和线距的要求可能会不同。在双端布线问题中，因为仅有两个端点，只需要一次布线即可完成，所以线宽和线距并不会影响布线过程；在多端布线中，有些端点布线前布线空间已经存在一部分导线，这些导线的存在会挤占布线空间，从而影响后续的布线工作；多组布线不仅会出现多端布线的问题，每一组线网也都会占用更大的布线空间，对其他组的布线造成困难。

多层布线