EDA中逻辑综合的算子序列优化问题

逻辑综合

逻辑综合（Logic Synthesis）是数字电路设计流程中的一个关键步骤，其目的是将高层次的设计描述（如硬件描述语言中的逻辑描述）转换为一个可以在实际硬件上实现的电路级别的表示。这个过程通常涉及对布尔网络的优化，以满足特定的设计目标，例如面积、功耗和速度等。

算子序列优化

为了优化电路的质量结果（Quality of Results，QoR），通常会使用一系列工具和方法来提升电路性能，例如：开源工具ABC因其包含众多优化算子而常被选择。然而，由于不同的算子往往会带来不同的优化效果，因此如果仅依赖简单的贪心策略选择当前提升最大的算子，很容易导致算法陷入局部最优解，无法获得整体优化。与此同时，算子的组合构成的搜索空间异常庞大，几乎不可能通过遍历找到最佳序列。因此，如何在有限的资源和时间内获取一个算子序列，使得电路经过这些序列后其QoR尽可能接近于全局最优，这是算子序列优化中的一个关键目标。

近年来对算子序列优化的工作大多集中于强化学习方面，将算子的选择建模为在给定状态下从动作集合中挑选动作，并组成轨迹，使得最后的电路指标尽可能优秀。下面将介绍两篇相关工作来进一步阐述算子序列优化。

AlphaSyn: Logic Synthesis Optimization with Efficient Monte Carlo Tree Search

AlphaSyn将蒙特卡洛树（MCTS）引入了逻辑综合的算子序列优化中，设计了一个合成特定的树上置信度上限（SynUCT）算法以均衡探索与利用的权衡，同时设计了相应的反向传播算法用于回溯和更新统计数据，以对搜索空间进行更有效的探索。其整体框架如上，当进入一个新的状态时，AlphaSyn主要分为三个阶段（1）选择、（2）扩展与评估、（3）反向传播。

选择阶段

在选择阶段，AlphaSyn通过MCTS做出决定，如图所示，每个节点代表网表当前的状态，每条边代表对网表执行算子进行一次变换。MCTS在每个节点通过已有的经验做决定，选择动作，并不断生成子节点，直到达到设定的深度（叶子节点）。

在做决定的过程中，需要对每个动作评估价值，AlphaSyn使用了长期奖励和短期奖励以及置信度作为动作的价值，和来自于与环境交互的经验，而则会给较少使用的动作“机会”，更好地权衡探索和利用。

扩展与评估

当选择过程到达叶节点后，AlphaSyn会机型扩展和评估。在选择阶段我们生成了一个新的轨迹，在扩展与评估阶段，我们开始实际上与综合工具交互，并得到执行变化后的网表，同时也可以通过综合工具获取网表的QoR，令为状态所对应的目标价值（例如网表中节点的数量），通过比较执行算子前后网表的价值，并使用一个参考值对其进行归一化，奖励为：

反向传播

一旦在叶节点计算出奖励，系统会进行回溯传播，递归更新从叶节点到根节点的所有节点信息。在获取了算子序列（即轨迹）和对应的回报后，需要更新MCTS的信息。首先会更新节点的访问次数，然后依据每个子节点的的最大值来更新当前节点的长期回报。这个过程通过一个折扣因子来调节，减弱了对访问频次较低的深层节点的影响，从而促进了根节点附近的探索，但仍然保留了对深层次高潜力转换的关注。这样，AlphaSyn的长期回报机制既鼓励在前期探索有潜力的路径，也确保对未来充分开拓深层决策树。

MCTS学习策略

AlphaSyn同时也提供基于神经网络训练策略的方式来提高模型的探索效率。当遇到一个新的节点时，没有节点的历史信息，此时需要估计在目前状态下动作的价值，确定MCTS扩展方向。AlphaSyn使用结合了图神经网络的PQnet预测后续状态预期的概率分布和回报，模型的输入为目前的状态和上一次使用的算子以及位置 ，这里是由GNN获取的当前网表的表征。

实验部分

AlphaSyn相比起之前的SOTA方案FlowTune在所有基准测试中表现出性能提升，在平均性能上提高了8.74%，在运行速度方面，AlphaSyn也提高了1.24倍，证明了其提出了基于MCTS的框架，在算子序列优化方面的有效性。

EasySO: Exploration-enhanced Reinforcement Learning for Logic Synthesis Sequence Optimization and a Comprehensive RL Environment

EasySO开发了一个更全面的RL框架，扩展了动作的空间，除了传统LO算子，还加入了技术映射(TM)和后映射(PM)算子，并在EPFL数据集中，达到了26个设计的LUT-6节点SOTA。

EasySo的框架

EasySO提出了用于离散/连续动作空间的混合策略梯度算法PPO，在模型结构上，它由三个部分组成：一个用于状态价值评估的价值网络，一个用于选择动作的策略网络，以及一个决定参数的策略网络。这些部分共享相同的状态表示。

在状态表示上，EasySO将当前状态拆分为三个部分：

• 描述并量化目前电路信息的表征，并通过MLP编码。
• 描述网表结构信息的表征，通过GCN编码。
• 描述历史动作信息的表征，通过序列模型Transformer编码。

为了在探索和利用之间找到平衡，作者提出了一种考虑预算的探索模块。在模型的早期训练阶段，加强对运算符的探索，因为其选择对模型性能有更大的影响。随着训练的进行，适当减少对运算符的探索，并增加参数的探索，以改善模型的表现和收敛性。

参数策略网络

EasySO发现算子的参数对网表的优化有较大影响，然而算子的参数空间非常庞大，如何快速寻找较为优秀的参数是一个问题。因此，EasySO的策略网络不仅包含了选择动作的策略网络，还包括参数策略网络

再参数的选择阶段，EasySO的参数策略网络读入当前状态的表示，使用高斯分布表示参数空间的概率分布。对于每一个参数，参数策略网络输出两个向量，均值向量和方差向量，之后根据这两个向量在参数空间中采样，获取参数向量，并和动作选择的向量拼接，形成混合动作。

梯度裁减

为了保证PPO训练的稳定，EasySO采用了梯度裁剪的方法，梯度裁剪通过设定梯度的最大范数，从而避免梯度过大导致的梯度爆炸现象。如果梯度的范数超过了一个预先定义的阈值 ，则对梯度进行缩放，使其保持在该阈值以内。在EasySO中，使用了clip的方式限制策略的更新范围。

预算探索模块

为了在探索与利用之间取得平衡，EasySO框架引入了预算探索模块，该模块负责动态调整算子策略和参数策略的探索预算，以提高样本利用效率和模型性能。在训练的初期，探索不同的算子比参数更有价值，因为算子的选择对电路综合的效果有更大的整体影响。一个好的算子（如不同的逻辑综合操作）可以显著影响整个设计优化管道。因此，在早期阶段，应该对算子选择进行更多的探索。随着训练的不断推进，算子选择会逐渐收敛到一个较为理想的策略。这时，进一步的性能提升可以通过更细致地探索参数空间来实现。因此，在后期阶段应减少对算子的探索，而加大对参数的探索。

为了动态调整算子和参数的探索预算，EasySO引入了探索预算调节网络，（Budget Tuner）。该网络通过监控动作序列 (算子和参数) 与奖励变化，来判断应当增加还是减少算子的探索预算和参数的探索预算，EasySO通过一个专门的探索损失项来控制探索的强度。

实验部分

实验中，EasySO在EPFL数据集中与最优结果相比具有显著的竞争力，展示了 EasySO 在处理大规模搜索空间和高复杂度电路设计任务中通过混合策略优化、梯度裁剪、以及预算探索模块等技术所取得的显著优势。

总结

近年来，逻辑综合中的算子序列优化问题成为了提升电路性能的关键研究领域。不同的算子组合会直接影响电路的优化效果，但是优化过程中面临的搜索空间过于庞大，贪心策略容易陷入局部最优。因此，强化学习方法为这一难题提供了较为有效的解决方案。本文详细分析了两种先进的方法：AlphaSyn和EasySO。AlphaSyn采用了蒙特卡洛树搜索（MCTS）策略，通过SynUCT算法在探索与利用之间取得了有效平衡，提高了算子选择的优化效果。EasySO则开发了一个包含混合策略梯度算法PPO的综合框架，在扩展动作空间的同时，通过梯度裁剪和预算探索机制提升了模型处理复杂电路的能力。这些创新为算子序列优化提供了新的技术路径和研究方向。