Digital VLSI Design Lecture 4 Logic Synthesis Part 2

课程主页：

http://www.eng.biu.ac.il/temanad/digital-vlsi-design/

课程视频：

https://www.youtube.com/watch?reload=9&v=RbZ3BXbd6_k&list=PLZU5hLL_713x0_AV_rVbay0pWmED7992G

https://www.bilibili.com/video/BV1EA411n7VQ?from=search&seid=14545899898143497364

这次回顾第四讲，这一讲继续介绍了逻辑综合。

布尔最小化

细化与绑定

在逻辑综合的下一步骤中，工具：
- 将RTL编译为布尔数据结构（细化）
- 将非开关量模块绑定到叶子单元（绑定）
- 优化布尔逻辑（最小化）
最终的设计被映射到通用的、与技术无关的逻辑门
这是综合的核心，自八十年代以来一直是计算机科学中一个非常核心的研究课题

细化例子

两级逻辑

在细化过程中，定义主要输入和输出（端口），并推导时序元素（触发器，锁存器）
这导致一组组合逻辑云：
- 输入端口和寄存器输出为逻辑的输入
- 输出端口和寄存器输入是逻辑的输出
- 输出可描述为输入的开关的函数
- 布尔最小化的目的是减少输出函数中的因子数
许多不同的数据结构用于表示布尔函数：
- 真值表、立方体、BDD、方程等
- 大部分研究都是在SOP或POS表示法上发展起来的，这两者通常称为“二级逻辑”

二级逻辑最小化

卡诺图，但是难以自动化(NP-complete)
Quine-McCluskey方法，易于在软件中实现，但是计算复杂度太高

Espresso启发式最小化

ESPRESSO(F){
	do {
		reduce(F);
		expand(F);
		irredundant(F);
	}while (fewer terms in F);
	verify(F);
}

从SOP开始
- Expand
  - 使每个立方体尽可能大而不覆盖OFF集中的一个点。
  - 增加因子数量（更糟糕的解决方案）。
- Irredundant
  - 扔掉多余的立方体。
  - 删除被较大立方体覆盖的小立方体。
- Reduce
  - 覆盖中的立方体大小减少了。
- 一般而言，新覆盖与最初的覆盖不同
  - expand和irredundant的步骤可能会找到一种覆盖ON集合中的点的新方法。
  - 希望新的覆盖会更小一些。

Espresso例子

$\begin{array}{l} f=\bar{A} \bar{C}+\bar{C} D+A C+C \bar{D} \\ f=\bar{A} \bar{C}+A \bar{C} D+A C+\bar{A} C \bar{D} \end{array}$

$\begin{array}{l} f=\bar{A} \bar{C}+A D+A C+C \bar{D} \\ f=\bar{A} \bar{C}+A D+C \bar{D} \end{array}$

多级逻辑最小化

两级逻辑最小化已经得到广泛的研究，并由此产生了许多著名的方法。
- 然而，通常使用许多层次的逻辑是更好和/或更实用。
因此，提出了一个全新的优化方案，即多级逻辑最小化。
- 在本课程中，我们将不讨论多级最小化问题，但是，您应该知道逻辑最小化通常输出多级，而不是两级。

例子：

BDD

BDD是表示给定函数真值表的DAG。

函数的香农展开将函数与其辅因子相关联：
- 给定一个布尔函数：$f\left(x_{1}, x_{2}, \ldots, x_{i}, \ldots, x_{n}\right)$
- 正辅因子：$f_{i}^{1}=f\left(x_{1}, x_{2}, \ldots, 1, \ldots, x_{n}\right)$
- 负辅助因子：$f_{i}^{0}=f\left(x_{1}, x_{2}, \ldots, 0, \ldots, x_{n}\right)$
香农展开定理指出
- $f=x_{i}^{\prime}f_{i}^{0}+x_{i} f_{i}^{1}$
- $f=\left(x_{i}+f_{i}^{0}\right)\left(x_{i}^{\prime}+f_{i}^{1}\right)$
这导致BDD的形成：
- $\begin{aligned} f &=a c+b c+a^{\prime} b^{\prime} c^{\prime} \\ &=a^{\prime}\left(b^{\prime} c^{\prime}+b c\right)+a(c+b c) \\ &=a^{\prime}\left(b^{\prime} c^{\prime}+b c\right)+a(c) \end{aligned}$
BDD的一些优点：
- 检查tautology是微不足道的
  - tautology是指BDD为常数1
- 取反
  - 给定函数$f$的BDD，可以通过交换终止节点获得$f’$的BDD。
- 等价性检查。
  - 如果函数$f$和$g$的BDD（在相同的变量顺序下）相同，则这两个函数是等价的。
要点：
- 如果变量被扩展的顺序被改变，BDD的大小会发生很大变化。
- BDD中的节点数可以是变量数的指数

ROBDD

BDD会变得很大。
- 所以，让我们看看我们是否可以提供一个化简的表达。
化简规则1：合并等价叶子节点
化简规则2：合并同构节点
化简规则2：消除冗余测试

约束定义

在细化之后，设计被加载到综合工具中，并存储在数据结构中。
分级端口（输入/输出）和寄存器可以按名称访问。
```
set in_ports [get_ports IN*]
set regs [get_cells -hier *_reg]
```
此时，我们可以以SDC格式加载设计约束，我们将在第5节课中学习
```
read sdc -verbose sdc/constraints.sdc
```
- 例如，要创建时钟并定义目标频率：
```
create_clock -period $PERIOD -name $CLK_NAME [get_ports $CLK_PORT]
```
仔细检查工具是否接受所有约束！

技术映射

技术映射是从技术库中选择门实现电路的逻辑合成阶段。
为什么要做技术映射？
- 直接实现可能不太好。
- 例如，$F= abcdef$作为$6$输入与门，会造成较长的延迟。
- 库的门是预先设计的，通常在面积、延迟、功率等方面进行优化。
可以应用最小代价树覆盖算法来解决这个问题。

技术映射算法

使用递归树覆盖算法，我们可以很容易地并且几乎是最佳地将逻辑网络映射到技术库。
这个过程包括三个步骤：
- 将网表和技术库映射到简单门
  - 用NAND2和NOT门描述网表
  - 用NAND2和NOT门的描述SC库，并将成本与每个门相关联
- 将输入网表树形化
  - 树覆盖只能用于树
  - 将扇出$>2$的地方划分树
- 最小成本树匹配
  - 对于树中的每个节点，递归地在该节点上找到最小成本目标模式。
让我们简单地介绍一下这些步骤

1.简单门映射

将De Morgan定律应用到布尔函数中，使其成为NAND2和NOT门的集合。
- 以多级逻辑最小化为例：
然后，给定一组具有成本度量（面积/延迟/功率）的门（标准单元库）：

我们需要用相同的NAND2/NOT集合来定义门：

2.树形化

要应用树覆盖算法，我们必须在树上工作！
- 任何给定的逻辑网络都是树形的吗？
- 不！
- 我们必须在扇出$>2$的任意节点划分树

3.最小树覆盖

现在，我们可以应用递归算法来达到最小覆盖：
- 从图的输出开始。
- 对于每个节点，找到所有匹配的目标模式。
- 节点$i$使用门$g$的代价为：
  - 其中$k_i$是$g$门的输入：
为简化起见，我们将重新绘制图表并显示一个示例：
- 每个NOT只是一个空圆：
- 每个NAND只是一个完整的圆：
- 每一个输入只是一个方框：

完整例子：

综合Verilog

我们可能忽略的部分

既然我们已经看到了综合是如何工作的，让我们重温一下我们可能跳过或只是简单地提到过的一些事情…
以一个简单的$4\to 2$编码器为例：
- 取独热码向量，输出$1$的位置。
- 一种可能性是用嵌套的if else块来描述这个逻辑：
- 这个结果称为“优先逻辑”
  - 即，有些比特优先于其他比特。
最好使用case构造：
- 所有情形并行匹配
- 更好的是，综合可以优化常数和其他布尔等式：
在前面的示例中，如果编码错误（即不是独热码），我们将在逻辑模拟中传播$x$。
- 但是如果我们保证输入是一个独热码呢？
- 然后我们可以用不同的方式编写代码：
- 事实上，我们已经实现了“优先级译码器”。

运算符的几点内容

逻辑运算符映射到基本逻辑门
算术运算符映射到加法器、减法器
关系运算符生成比较器
固定数量的移位只是电线连接
- 不涉及逻辑
可变的移位量$\to$移位器
条件表达式生成逻辑或MUX

数据路径综合

复杂运算符（加法器、乘法器等）以特殊方式实现：
预先写好的说明可在Synopsys DesignWare或Cadence ChipWare IP库中找到。

时钟门控

如你所知，由于时钟是不断摆动的，它是一个主要的能力消耗者。
- 因此，为了节省电力，我们将尽量关闭不使用的闸门的时钟。
块级（Global）时钟门控
- 如果某些工作模式不使用整个模块/组件，则应在RTL中定义时钟门。
寄存器级（Local）时钟门控配置寄存器。
- 但是，即使在寄存器级别，如果触发器不改变其输出，由于时钟振荡，内部电源仍然耗散。
- 这在启用的信号采样中非常常见，因此，综合工具可以自动检测和门控。