《超大规模集成电路物理设计：从图分割到时序收敛》学习笔记

第一章 - 绪论

电子设计自动化（EDA）

VLSI 设计流程

各个步骤做的事情：

系统规范：定义系统的总体目标和高级需求，包括功能、性能、物理尺寸和生产技术。
架构设计：在满足系统规范的情况下选择各种实现。
功能和逻辑设计：使用硬件描述语言（HDL）定义芯片的功能和时序行为。使用逻辑综合工具将 HDL 与工艺库结合起来。
电路设计：一些关键的低端的单元必须在晶体管级来进行设计。包括静态 RAM 模块、I/O、模拟电路、高速函数（乘法器）以及静电放电（ESD）保护电路。电路级仿真工具可以验证电路级设计的正确性。
物理设计：布局、布线。物理设计影响电路性能、面积、可靠性、工具和制造产量。
- 划分：将电路分解成功效的子电路或者模块，使之能够单独设计或者分析。
- 布图规划：决定子电路或者模块的形状和布置，以及外部端口、IP 或者宏模块的位置。
- 电源和地网布线：经常在布图规划中，分布电源（VDD）和地（GND）线网在芯片各处。
- 布局：确定在每个模块中的所有单元的空间位置。
- 时钟网综合：决定了时钟信号的缓冲、门控（例如电源管理）和布线，以满足规定的偏移和延迟需求。
- 总体布线：分配布线资源用于连接。
- 详细布线：分配布线到指定的金属层，以及在总体布线资源中指定布线轨道。
- 时序收敛：通过专门的布局和布线技术来优化电路性能。
物理验证：
- 设计规则检查（DRC）
- 版图与原理图一致性检验（LVS）
- 寄生参数提取、验证电气特性
- 天线规则检查
- 电气规则检查（ERC）
制造：流片
封装和测试

VLSI 设计模式

VLSI 设计模式分为两类：全定制和半定制。

常用的半定制标准设计模式：

基于单元：通常采用标准单元和宏单元
基于阵列：包含若干预先制备好的元件

单元上（OCT）布线，临近的标准单元行不会被布线通道分离，还可以共享电源轨道或者地轨道。

宏单元是典型的较大块逻辑，执行可重用的功能。

基于门阵列的设计优点是设计便宜和快速。

现场可编程门阵列（FPGA）中，逻辑单元和互连都是预先制造好，但是用户可以通过开关来配置。

结构化 ASIC（无通道门阵列）类似于 FPGA，不过它的单元通常不能配置。

版图层和设计规则

集成电路主要由几个不同的材料构成，其中主要的是：

单晶硅沉底掺杂构建 n 和 p 沟道晶体管；
二氧化硅，用来作为绝缘体；
多晶硅，形成晶体管栅极和作为互连材料；
铝和铜，用于金属互联。

使用多晶硅来做栅极是因为铝承受不了掺杂带来的高温。

线电阻通常定义为片电阻，用每平方欧姆表示（ ${\Omega \over \square}$ ）。

单元之间布线是完全在金属层进行的。不同层有不同的片电阻，这对时序特性的影响很大。

多金属层的布线需要过孔。

设计规则大致可以分为三类：

尺寸规则
间距规则
覆盖规则

物理设计优化

物理设计是一个复杂的优化问题，它有几个不同的目标，例如最小芯片面积、最小线长和最少过孔。

在版图优化中，三类约束必须满足：

工艺约束，用于指导特定工艺节点的生产制造，是从工艺限制中提取出来的。
电气约束，保证设计达到预期的电气行为。
几何（设计方法）约束，减小设计过程的整体复杂度。

优化版图时可能遇到的困难如下：

优化目标可能相互冲突。
约束常导致间断，即使目标函数保持连续，也会定性影响。
由于集成电路规模的提升以及互连要求的不断增加，各种约束将更加严厉，而且各个工艺节点也相应增加了一些新的约束类型。

解决这些问题可以使用以下的经验法则：

每个设计模式需要自己的定制流程。
当设计一个芯片时，使用几何约束可以简化设计难度，其代价是需要进行版图优化。
为了进一步降低复杂度，设计过程可以划分为若干顺序步骤。
当进行基本的优化时，可以选择 (1)电路性能允许简单计算的抽象模型，或者 (2)难以计算的真实模型。当没有有效的算法或者封闭形式的表达式来求取全局最优化解决方案时，使用启发式方法是一个正当、有效的选择。

算法和复杂性

布局问题和它们相关的计算复杂度包括：

放置 n 个单元在一个单独的行里并返回线的长度： $O(n)$
给定 n 个单元的单行布局，决定通过交换一堆单元能否提高线长： $O(n^2)$
给定 n 个单元的单行布局，决定通过一次置换一组三个单元是否提高线长： $O(n^3)$
在一行里面放置 n 个单元使线长最小：简单的算法 $O(n! \cdot n)$

许多物理设计问题，例如布线和布局，都是 NP 困难问题，用最优化、最坏情况下多项式时间算法来解决它们是不可能的。很多启发算法已经开发出来解决这些问题，基于 (1)运行时间和 (2)解的质量来评估算法质量，用次优解（和最优化解不同）来计量算法。
启发式算法可以分为：

确定性：算法所作的所有判断可重复，即不是随机的。一个确定性启发式算法的例子是 Dijkstra 最短路径算法。
随机性：算法所作的部分判断是随机的。一个随机算法的例子是模拟退火。

在构造化方面，启发式算法是：

构造：启发式算法开始于一个初始的、不完整的（部分）解，然后增加组件，知道获得完整的解。
迭代：启发式算法开始于一个完整的解，不断改进当前解，直到达到预设的终止标准。

使用构造性的启发式算法首先产生一个初始解，然后通过迭代算法来改善。

图结构的搜索和最优化算法可以另一种方式进行分类：

广度优先搜索（BFS）
深度优先搜索（DFS）
最佳优先搜索，例如 Dijkstra 算法

大多数物理设计算法在本质上是启发式的，其解的质量评估非常困难。如果最优解已知，那么启发式解可用它的相对于最优解的次优 $ε$ 来判定：

ε = {|cost(S_H)-cost(S_{opt})| \over cost(S_{opt})}

现代设计通常不易找到最优解，此时启发式解需要通过一套基准（Benchmarks）来测试。

图论术语

图 $G(V,E)$ 由两个集合组成——点或者顶点（元素）的集合，表示为 $V$ ；边的集合（两个元素之间的关系），表示为 $E$ 。节点的度是与它连接的边的数量。

超图由节点和超边组成，其中，超边是两个或者更多节点的子集。注意：如果一个图是超图，那么它的超边基数为2。超边通常用于表示电路超图中的多引脚网或者多点连接。例如下超图中含三条超边：

多重图是在两个给定节点之间不止一条边的图。多重图可以用来表示变化的线网权重，另一种方法就是用一个带权边图来表示，这样更加紧凑而且也支持非整数的权重。

两个节点之间的通路是从开始节点到终点的有序边序列。

回路（环）是一个开始节点和结束节点相同的闭合通路。

无向图是表示无序节点关系，且没有任何方向边的一种图。有向图是一种图，其边的方向表示两节点之间的特殊序关系。

如果一个有向图至少有一个方向环，那么该有向图含有回路，否则就不含回路。几个重要的 EDA 算法操作在有向无环图（DAG）上，它表示设计数据。

完全图是具有 $n$ 个节点的图，每对节点之间都有一条边相连，它的边是：

{n \over 2} = {n! \over 2!(n-2)!} = {n(n-1) \over 2}

连通图是每对节点之间至少有一条通路的图。

树是一种 $n$ 个节点有 $n-1$ 条边连接的图。有两种类型的树：无向树和有向树。

任何具有一条关联边的节点被称为叶子节点。在一个有向树里面，根节点没有入边，叶子节点没有出边。在有向树里面，存在一条唯一的从根节点到其他节点到通路。

图 $G(V, E)$ 中到生成树是连通的、无回路的子图 $G'$ ， $G'$ 包含在 $G$ 中，即 $G$ 包括（生成） $G'$ 中每个节点 $v∈V$ 。

最小生成树（MST）是具有最小可能的边代价和的生成树。

矩形最小生成树（RMST）是一个所有边长都符合曼哈顿（矩形）距离度量的 MST。

斯坦纳树，以 J. Steiner(1796-1863) 命名，是泛化的生成树。除了原始节点，斯坦纳树还有斯坦纳点。这些点可以用边连接起来，包括原始节点。使用斯坦纳节点可以减少树的边代价总和。如果在曼哈顿平面只采用水平和垂直的线段，那么 SMT 就是举行斯坦纳最小树（RSMT）。

EDA 常用术语

逻辑设计是将 HDL 描述映射到电路门和门在网表级的连接的过程。结果通常是单元或其他基本电路元件和连接的网表。
物理设计是决定单元和它们的连接在集成电路版图中如何布置的过程。单元的电气和物理性能从库文件和技术信息里面获取。连接拓扑是从网表中得到的。物理设计的结果是从几何和功能都正确的表示，用标准文件格式，例如 GDSII 流。
物理验证检查版图设计的正确性。这包括下述的版图验证：
- 遵守所有的技术需求——设计规则检查（DRC）；
- 是否和原始网表一致——版图和原理图一致性检查（LVS）；
- 没有天线效应——天线规则检验；
- 遵守所有的电气需求——电气规则检验（ERC）。
组件是有基本功能的电路元件。例如晶体管、电阻和电容。
模块是一个电路划分或者一部分构件的集合。
块是具有形状的组件，也就说一个有固定尺寸的电路划分。
单元是用不同构件建立的逻辑或者功能单位。在数字电路中，单元通常指门。总的来说，这个术语常用来指标准单元或者宏单元。
标准单元是一种预先决定功能的单元。它的高度是特定库中固定尺寸的倍数。在标准单元方法里，逻辑设计是将标准单元排列在行里来实现的。
宏单元是一种没有预先定义尺寸的单元。这个术语也可以指大型物理版图，可能包含数百万晶体管。
引脚是一个电子终端，用于连接给定的构件到它的外部环境。
层是制造工艺等级，在这个等级中，设计构件在芯片上成型。在物理设计中电路构件分配到不同层。
接触层是硅（多晶硅层或者其他活动层）和金属层（典型的 Metal1）之间的直接连接。接触层经常在单元内。
过孔是金属层之间的连接，通常用来连接不同层的布线结构。
线网或信号是必须在相同电势下连接的引脚或者终端的集合。
供电网是提供电流给单元的电源（VDD）和地（GND）网。
网表是在设计中连接的所有信号网和构件的集合，或者是所有网和分段设计的连接引脚的列表。也就是说，网表可以组成 (1)面向引脚——每个设计构件都有一个相关线网的列表，或者 (2)面向线网——每个线网都有一个相关构件的列表。网表在逻辑综合中创建，是物理设计的关键输入。
线网权重 $w(net)$ 是一个数（典型的整数）值，用来表示线网的重要性或关键性。
在无权重线网中，单元 $i$ 和单元 $j$ 之间的连接度或者连接代价 $c(i, j)$ 是单元 $i$ 和 $j$ 之间的连接数。在权重网中， $c(i, j)$ 是单元 $i$ 和 $j$ 之间的单独连接权值总和。
单元 $cell_i$ 的连通性 $c(i)$ 定义如下式，其中， $|V|$ 是网表中单元数量； $c(i, j)$ 是单元 $i$ 和 $j$ 之间的连接度。

c(i) = \sum_{j=1}^{|V|}c(i, j)

连接图是网表的一种图表示。单元、模块和压焊块对应于节点，它们之间的连接对应于边。一个 $p-pin$ 网用 $\left( \begin{array}{c} p \\ 2 \end{array} \right)$ 表示节点之间的所有连接。两个节点之间的多条边意味着一个更强（有权重的）的连接。
连接矩阵 $C$ 是一个 $n×n$ 矩阵，表示电路中 $n$ 个单元的电路连接。
两个点之间的欧几里得距离相当于两个点之间的线段长度。在坐标平面里，欧几里得距离为：

d_E(P_1, P_2) = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2}

两个点之间的曼哈顿距离等于两点之间水平和垂直位移的和。在平面坐标系中，曼哈顿距离是：

d_M(P_1, P_2) = |x_2-x_1| + |y_2-y_1|

第二章 - 网表和系统划分

第三章 - 芯片规划

第四章 - 全局和详细布局

全局布局
详细布局
合法化

在布局阶段，详细布线信息是不可知的，布局器通过对加权总线长、割边数、线拥挤度（密度）或最大信号时延等的估算，来优化布线质量。

对给定布局的线长估算

两端线网采用曼哈顿距离进行线长估算。

多端线网常常使用半周长线长（HPWL）模型来估算，准确度好计算效率高。具体如下：
当点数小于4时，用包含所有引脚位置的最小矩形边界框的半周长来估算线长，恰好与直线斯坦纳最小树（RSMT）的代价一样。
当点数大于等于4时，因为 $p$ 个引脚的线网 $net$ 的完全图模型有 ${p(p-1) \over 2}$ 条边，但其生成树只有 $p-1$ 条边，所以用 ${2 \over p}$ 来修正。于是这个线网 $net$ 的总边长为：

L(net) = {2 \over p} \sum_{e ∈ clique}d_M(e)

其中， $e$ 是最大子图中的一条边； $d_M(e)$ 是 $e$ 的两端点之间的曼哈顿距离。

单链模型用一个链状拓扑结构连接一个线网的所有引脚，两个终端引脚的度为 1；每个中间引脚的度都为 2.找出一条连接引脚位置的最小长度路径相当于 NP 困难问题的 Hamiltonian 路径问题。所以一般的方法是从左到右或从上到下连。缺点是线长估算超出实际长度，以及布局改变链状拓扑结构也会改变。

星形模型将一个引脚作为源点，而把其他引脚作为汇点。对时序优化相当有用；由于其稀疏性对建立多引脚数线网很有益；同样会对线长估算超过实际长度。

直线最小生成树（RMST）模型将 $p$ 个引脚的线网分解成两段引脚的连接，连接 $p$ 个引脚需要 $p-1$ 个连线。算法例如 Kruskal 算法。RMST 算法寻找曼哈顿几何结构需要用的时间复杂度为 O(p log p)。

直线 Steiner 最小树（RSMT）模型连接线网中的所有 $p$ 个引脚，最多要增加 $p-2$ 个 Steiner（分支）点。在任意一个点的集合中，要找出一个最优的 Steiner 点集合是 NP 困难问题。对于引脚数有界限的线网，计算一个 RMST 需要的时间是不变的。如果 Steiner 点是知道的，可以通过在原点集和增加的 Steiner 点集上构造一个 RMST 来找到 RSMT。

直线 Steiner 吸收（RSA）模型，是 $p$ 个引脚的线网的一棵 RSA 树，其中单源点 $s_0$ 连接到 $p-1$ 个汇点。对于所有汇点 $s_i$ ，有

L(s_0, s_i) = d_M(s_0, s_i)

其中， $L(s_0, s_i)$ 是在树中，从 $s_0$ 到 $s_i$ 的路径长度。
计算一个最小长度的 RSA 是 NP 困难问题。

单树干 Steiner 树（STST）模型由一个垂直（水平）线段组成，即树干，用水平（垂直）线段（相当于分支）连接所有引脚到这个树干。由于构造 STST 很容易，因此常用它来进行线长估计。RSA 与时序更相关，但是在结构上多少比 STST 复杂。对实际应用，构造 RSA 和 STST 的时间为 O(p log p)。