AI-EDA中的逻辑综合算法

johnsoncodehk · 发表于 2023-1-19 11:01

1.逻辑综合背景介绍

定义

  逻辑综合是将较高层次的描述(RTL级)自动地转换到较低抽象层次描述(门级网表)的一种方法。
  逻辑综合要求的输入除RTL描述的程序模块或者原理图文件或波形文件外，还需要工艺库以及约束条件。
  综合工具支持的工艺库(如TTL工艺库，MOS工艺库，CMOS工艺库)包含一些标准的单元。在综合时，综合工具会将RTL级代码描述的设计用工艺库中的标准单元转化为逻辑电路。
  约束条件，用于决定综合过程中的逻辑优化方法。约束条件中一般包含时间，面积，速度，功耗，负载要求和优化方法等，甚至还包含综合时需要注意的设计规则。
  逻辑综合输出的结果是门级网表。
逻辑综合步骤

第一步 (Translation)：
转换过程，将RTL描述转换成为未优化的门级布尔描述(如与门，或门，触发器，锁存器等)。
第二步 (Logic Optimization)：
布尔优化过程，将一个非优化的布尔描述转化成一个优化的布尔描述的过程。
第三步 (Mapping)：
门级映射过程，取出经优化的布尔描述，利用从工艺库中得到的逻辑和定时的信息生成门级网表，确保得到的门级网表能达到设计的性能和面积要求。

标准工艺库(Standard Cell Library)

数字电路逻辑设计，在逻辑综合与工艺映射中会被替换成一堆互相连接的标准单元（Standard Cell）
常见的标准单元有基本逻辑门（AND、OR、NOT、XOR...）、Flip-Flop寄存器、MUX多路选择器、加法器、时钟单元、延时缓冲（Delay Buffer）
标准单元库是一组相对完善的、符合某种生产或设计工艺标准的标准单元
通常由芯片制造厂商提供基本的标准单元库，而芯片设计厂商在其基础上进行一定的优化和改良，这些信息通常是会被打包在一个工艺设计工具包（Process Design Kit， PDK）中
标准单元库中包含了每一个标准单元的面积、引脚描述、功能、在特定工艺下的版图、相关RC/Delay模型或参数
组合逻辑优化（Combinational Logic Optimization）

在组合逻辑优化环节，其中一个重要部分是布尔表达式的最小化，即找到最简单门级电路实现给定的布尔表达式。这是一个NP完全问题，我们通常用启发式算法去求解，例如数字电路课堂上我们是利用卡诺图画图最小化SOP，而通常计算机内实现的算法是Quine-McCluskey算法。但是实际上还有许多表示形式如ESOP（E互斥或积之和表示式）和CDEC（条件解码器）。
我们常见的最小化是叫做二级最小化，但是一般电路表示形式则是更为灵活的多级形式。对于这些多级的直接优化，用与非图AIG来描述组合逻辑电路，利用AIG的有向无环图的特性，一系列高效算法可以用于平衡、重写和重构这些AIG，从而最小化电路。基于AIG有一个主要的好处是，现在大多是的ASIC设计与FPGA设计，都是基于标准单元或者LUT实现的，往往有特定的输入输出引脚数目限制，AIG可以很好把这个限制反映在算法之中。

LUT:(look up table) 查找表

任何一个组合逻辑都可以表示成真值表的形式（逻辑输入对应逻辑输出），也就是任意的真值表所反映的内容都能由组合逻辑实现，查找表（LUT）就能完成这个任务。具体的过程可以参照上面这张图，给出了一个 3 输入的查找表，可以实现任意 3 输入的逻辑函数。一般 k 输入的查找表由 2^{k} 个 SRAM 单元和一个2^{k}输入的数据选择器MUX组成，可以实现 2^{2^{k}} 种逻辑函数。
时序逻辑优化（Sequential Logic Optimization）

而考虑时序问题，逻辑综合中主要需要处理与寄存器、状态机、时钟相关的问题。时序电路会有时钟频率限制，对组合逻辑的整体延时有最大最小值限制。重定时算法会移动寄存器在DAG网表的位置，将整个网表拆分成符合设计限制，合适的Retiming将有利于实现更加高频率的数字电路。有的Retiming算法侧重于缩短时钟周期，有的则侧重减少寄存器数目，如果变换寄存器的位置，会影响到部分控制逻辑，所以其实有一些约束条件的，这些约束条件大多可以转化为SAT（布尔可满足性）问题并且利用SAT专用求解器求解。

工艺映射（Technology Mapping）

考虑到布局布线、生产工艺、设计最优化，目前通常的集成电路的实际实现是基于标准工艺库与宏单元的组合、布局、连接。经过这个过程，设计的逻辑行为网表最终变成门级网表。因此逻辑综合还需要把网表中的各个部分，映射成一个个逻辑器件。这样映射的目标通常是优化面积、延迟指标，实现这一目标通常是把问题转化为有向无环图覆盖问题。对于复杂的设计网表，这个问题同样是NP-hard。不过如果模板和设计网表都是树，则该问题可以通过动态规划高效解决，所以一种解决方案就是把图动态划分成森林、同时结合基于树的算法，来解决相对复杂图的映射。

开源EDA工具-Yosys

Yosys是Verilog RTL合成的综合，用作三个VTR前端之一，用于执行逻辑综合、细化和将Verilog硬件描述语言（HDL）的子集转换为BLIF网表。Yosys的设计是可扩展的，因此是实现专门任务的定制综合工具的良好基础。

Benchmark-EPFL

EDA社区严重依赖公共基准来评估学术和商业设计工具的性能。逻辑优化和综合是EDA的核心应用，其中基准测试对于开发有效的方法至关重要。为了给逻辑优化和综合社区定义一个新的比较标准，引入了EPFL组合基准套件。它由23个组合电路组成，分为算术、随机/控制和MtM部分。
2.逻辑综合相关算法

DRiLLS:Deep Reinforcement Learning for Logic Synthesis

作者：Abdelrahman Hosny,et al.
单位：Brown University, American University in Cairo
相关链接：https://ieeexplore.ieee.org/document/9045559
研究背景
逻辑综合优化通过初等变换(如rewriting,balancing)的序列完成优化，需要大量专业人员的设计经验，流程的复杂性主要来自于指数级增长的电路变换搜索空间。由于变换的可能性很多，变换的不同递归和排列可以显著影响最终设计的面积与时延，QoR(Quality of Results)。
与此同时，机器学习(ML)的进步，特别是强化学习(RL)，能够提高代理在复杂环境中参数搜索的能力。
rewriting通过迭代地选择一个节点上的AIG子图，预先计算其所有NPN结果并保存子图，用子图中效果更佳的子图来替换当前AIG子图，以此来达到最小化节点数量的目的。balancing采用拓扑排序，选择每个多输入与门的最小延迟树分解，在不增加节点数的基础上去优化深度

研究方法
Drills(基于深度强化学习的逻辑综合)有效地将设计空间探索问题映射到强化学习环境中，任务涉及给定电路设计的组合优化。这使得定义环境的状态和代理探索设计空间而不落入局部最小值的长期激励具有挑战性。
状态空间：[primary I/O,nodes,edges,levels,latches,ANDs,NOTs]
优化空间：[resub, resub -z, rewrite, rewrite -z,refactor, refactor -z, balance]

奖励函数：多目标奖励函数

A2C(优势Actor-Critic)：通过减去一个基线函数来标准化评论家的打分，更多指导信息，降低较差动作概率，提高较优动作概率，进一步降低方差
优势函数（Advantage Function）
A(s, a) = Q(s, a)  V (s)
Q(s, a) = r + γV (s’)

在状态s下根据策略采取动作a。代理具有基于策略和基于价值的混合网络，分别称为演员和评论家。Q(s,a)是动作a在状态s下的Q值，V(s)是给定状态的平均值，R是当前回报函数，通常智能体需要预测和估算未来的奖励，γ是0~1的折扣因子，在强化学习中用来调节近远期影响，即agent做决策时考虑多长远，取值范围(0,1]。γ越大agent往前考虑的步数越多，但训练难度也越高；γ越小agent越注重眼前利益，训练难度也越小。训练开始首先迭代优势奖励函数，演员网络输出可能变换序列的概率分布，将奖励传递给评论家网络进行训练，评论家将一个折扣奖励传递回演员网络，使用基于梯度的优化器训练演员和评论员网络最小化损失函数。
实验结果
如图显示了代理搜索最小化面积并满足延迟约束的优化设计的痕迹，在面积和延迟约束之间寻求平衡。代理执行某些优化序列满足了时延，但增加了设计面积，如Log2中的迭代30和Max中的迭代26。在某些迭代中曲线会趋于饱和，显示了A2C网络平衡强化学习中探索利用行为。贪心算法只有一个优化目标(区域)。由于算法在前几次迭代中满足停止条件，因此无法减少受时延约束的区域，平均面积改善最小。专家综合脚本并没有改善面积，但很好地满足时延的约束。EPFL的最佳结果显示，在3个设计中有相当大的改进，其中4个满足延迟约束。它们的优化技术没有针对标准的单元库映射设计。Drills满足了所有设计的延迟约束，同时平均提高了13.19%的设计面积。证明了之前定义的奖励函数是一种有效的训练agent的奖励函数

代理在变换操作空间中搜索，在满足延迟约束的同时找到面积最小的设计

逻辑综合优化结果的面积时延比较

BOiLS: Bayesian Optimisation for Logic Synthesis

作者：Antoine Grosnit,et al.
单位：Huawei Noah’s Ark Lab,University College London,University of Oxford
相关链接：https://ieeexplore.ieee.org/abstrat/document/9774632
研究背景
组合逻辑优化采用反相器图(AIG)表示电路的逻辑功能，目标是通过应用一系列初等变换(如rewriting,balancing)简化AIG图，找到产生最高QoR的变换序列。
深度学习和强化学习技术在组合逻辑优化表现出很高的样本复杂性，高的数据需求意味在给定的电路中进行大量的计算，如利用CNN时，每个电路有10000个序列，或在RL中超过数千个代理环境交互次数。
本文是第一个采用现代贝叶斯优化来探索综合操作空间的算法，贝叶斯优化的特点是不需要人工经验，不需要对损失函数求梯度，搜索组合逻辑空间效率高，能够权衡探索和开发。这张图像表现了贝叶斯优化的全部基本元素，我们的目标就是在采集函数指导下，让f 尽量接近f(x)，在这个过程当中，我们其实在不断地优化我们对目标函数f(x)的估计，随着观测的点越来越多，对函数的估计是越来越准确的，因此也有越来越大的可能性可以估计出f(x)真正的最小值
引入当前超参数优化领域最高效的贝叶斯优化：
1 定义需要估计的函数f(x)及x定义域
2 取出有限的n个x上的值，求解出这些x对应观测值
3 根据有限的观测值，利用概率代理模型（Probability Surrogate model）对函数进行估计，概率代理模型自带先验知识，得出该估计函数f 上的目标值和对应的置信度
4 定义采集函数（Aquisition Function），采集函数衡量观测点对估计函数f 所产生的影响，并选取影响最大的点执行下一步观测

逻辑综合的高斯核函数
方法分两步进行。首先，利用面向AIG优化序列的核函数，对QoR数据拟合代理高斯过程。该高斯过程能够提高采样效率，同时实现函数不确定性估计。
QoR数据：

假设

将电路优化序列表示为操作字符串，每个字符都是来自AIG的算法
使用字符串子序列内核（sub-sequence string kernel，SSK）通过公共子串的数量来度量字符串之间的相似性
字符串seq和seq’的第 l 阶SSK：

子序列u对seq的贡献:

匹配和间隙衰减(match and gap decays):

投影梯度:

通过最小化负对数边界似然确定超参数θ：

最大化信赖域采集函数：
在第二步中利用高斯过程构造新的综合流进行评估,为了有效处理高维搜索问题而利用局部搜索最大化信赖域采集函数。
将高斯过程与上一步的核函数拟合，利用局部搜索(local search)最大化信赖域采集函数:

		自动登录	找回密码
密码			立即注册

AI-EDA中的逻辑综合算法

本帖子中包含更多资源