面向逻辑综合的检索引导式强化学习：ABC-RL 方法及其在布尔电路最小化中的应用
一、 主要作者、机构与发表信息
本研究的主要作者包括：Animesh Basak Chowdhury（第一作者，工作完成于纽约大学，现就职于 Qualcomm Incorporated）、Benjamin Tan（卡尔加里大学）、Marco Romanelli、Ramesh Karri 和 Siddharth Garg（后三者均来自纽约大学电气与计算机工程系）。该研究以论文形式发表于 ICLR 2024（International Conference on Learning Representations 2024）会议。
二、 学术背景与动机
本研究的核心科学领域是电子设计自动化（Electronic Design Automation, EDA），具体聚焦于其中的逻辑综合（Logic Synthesis）阶段。逻辑综合是芯片设计流程中的关键前端步骤，其任务是将用硬件描述语言（如 Verilog）编写的芯片功能规格，通过一系列功能保持的逻辑最小化启发式操作（称为“综合配方”，Synthesis Recipe），优化为使用布尔逻辑门（如与门、非门）实现的高效电路网表（Netlist）。综合配方的具体序列（即应用哪些优化操作以及应用的顺序）对最终芯片的面积、延迟等关键指标有着决定性影响。
传统的逻辑综合高度依赖设计人员的经验和直觉来选择和调整综合配方，这个过程对于现代复杂的芯片设计而言既耗时又成本高昂。近年来，利用机器学习，特别是强化学习（Reinforcement Learning, RL）自动搜索高质量综合配方成为一个新兴研究方向。现有工作主要分为两类：1) 纯搜索方法，如基于蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）的解决方案，为每个新设计从头开始搜索，不利用历史数据；2) 学习增强方法，例如利用历史数据训练一个预测模型来指导搜索。
然而，本研究通过初步实验揭示了一个关键问题：当面对与训练数据分布差异较大的新颖电路设计时，基于历史数据预训练的 RL 智能体可能会将搜索引向次优路径，导致其性能甚至不如纯搜索方法（如 MCTS）。这一现象源于硬件设计的多样性：芯片设计既包含对过去组件的复用，也经常需要创建全新的功能模块，导致训练和测试数据之间存在显著的分布偏移。
因此，本研究的目标是开发一种能够自适应地利用历史经验的新方法，使其在面对熟悉设计时能有效利用预训练知识加速优化，在面对全新设计时又能避免被误导，保持甚至超越纯搜索的性能。基于此，研究者提出了 ABC-RL，一种检索引导的强化学习方法，用于布尔电路最小化。
三、 研究详细工作流程
ABC-RL 方法的核心在于，在利用预训练 RL 智能体引导 MCTS 搜索的基础上，引入了一个基于检索的机制来自适应地调节智能体建议的权重。整个工作流程可分为离线训练、超参数设定和在线推理三个阶段。
1. 问题形式化与基线方法构建 研究以开源逻辑综合工具 ABC 为实验平台。问题被定义为：给定一个初始的与-非图（And-Inverter Graph, AIG）G0，从一组有限的转换操作（如 rewrite, refactor, balance 等，共7种）中，寻找一个长度为 L（研究中 L=10）的操作序列（即综合配方），使得应用该序列后得到的最终优化 AIG 的质量结果（Quality of Result， QoR， 此处为面积-延迟积的倒数，越大越好）最大化。
首先，研究者构建了一个基线方法，称为 MCTS+Learning。该方法借鉴了 AlphaGo 等工作的思想： * 状态表示：将搜索状态 s 编码为一个二元组：输入的原始 AIG (G0) 和迄今为止已应用的部分操作序列。 * 策略网络架构：设计了一个双分支的神经网络来编码状态。 * AIG 编码分支：使用一个 3 层的图卷积网络（Graph Convolutional Network, GCN）来处理 AIG 图结构，生成图嵌入向量。 * 配方编码分支：使用一个基于 BERT 的单层 Transformer 编码器来处理可变长度的部分操作序列，生成序列嵌入向量。选择 Transformer 是为了更好地捕捉操作序列中的上下文依赖关系（例如，某些操作在序列开头比在末尾更有效）。 * 将两个分支的嵌入向量拼接后，通过全连接层输出一个在 7 种操作上的概率分布，即预训练的 RL 策略 πθ(s， a)。 * 训练与搜索结合：在由历史电路（训练集）构成的离线数据集上，通过最小化交叉熵损失来训练策略网络，使其逼近在这些电路上运行纯 MCTS 得到的最优策略。在在线搜索阶段，将训练好的策略 πθ(s, a) 作为一个偏置项，乘以 MCTS 原有的探索项（UCT），形成新的搜索策略，目的是利用历史知识引导搜索走向更优区域。
2. ABC-RL 核心创新：检索引导的自适应调节 针对 MCTS+Learning 基线在面对新颖电路时可能失效的问题，ABC-RL 引入了关键的改进——一个可调参数 α。 * 相似度计算与 α 参数：对于一个新的待综合电路（测试 AIG，G0），ABC-RL 首先计算其与训练集中所有电路的相似度。为了高效，相似度是基于策略网络中 GCN 分支学习到的图嵌入向量（h_g）来计算的，具体采用余弦距离。取与训练集中最近邻的距离作为该测试电路的相似度得分 δ_g0。 * α 的计算：通过一个以阈值 δ_th 和温度 t 为参数的 Sigmoid 函数，将相似度得分 δg0 映射到 [0， 1] 区间内的 α 值：α = σ{δ_th，t}(δ_g0)。当测试电路与训练数据极其相似时（δ_g0 很小），α 趋近于 0；当电路完全新颖时（δ_g0 很大），α 趋近于 1。 * 自适应调节搜索策略：在在线 MCTS 搜索中，ABC-RL 使用调整后的公式来结合预训练策略：u*_mcts(s， a) = πθ(s, a)^{(1-α)} * u_mcts(s, a)。这里的 α 起到了调制作用： * α ≈ 0（电路熟悉）：预训练策略的权重很高（πθ(s, a)^1），搜索严重依赖历史经验。 * α ≈ 1（电路新颖）：预训练策略的权重被降至很低（πθ(s, a)^0 ≈ 1），搜索几乎退化为纯 MCTS，避免被可能不相关的历史知识误导。 * 0 < α < 1（中间情况）：根据新颖程度，平滑地调整预训练策略和纯探索之间的平衡。 * 超参数设定流程：使用一个独立的验证集电路，通过网格搜索来确定最佳的 δ_th 和 t 值，目标是使 ABC-RL 在该验证集上的表现优于 MCTS 和 MCTS+Learning 基线。
3. 实验设计与评估流程 * 数据集与划分：研究使用了三个业界常用的逻辑综合基准测试套件：MCNC、EPFL 算术电路和 EPFL 随机控制电路，共 56 个网表。将其按比例随机划分为：23 个用于训练，13 个用于验证，20 个用于最终测试。 * 优化目标与评估指标：主要优化目标是面积-延迟积（Area-Delay Product, ADP），值越小越好（报告中常使用相对于基准配方 resyn2 的 ADP 降低百分比来衡量，降低越多越好）。同时，报告了在达到相同 QoR（等质量结果，iso-QoR）时，ABC-RL 相比其他方法所能减少的运行时（加速比）。 * 对比基线：与五种前沿方法进行了全面对比，包括纯 MCTS 搜索、基于模拟退火与预测器的方法（SA+Pred）、两种在线 RL 方法（DRiLLS 和 Online-RL），以及作者自己实现的 MCTS+Learning 基线。此外，还对比了一种从芯片布局领域迁移过来并进行了在线微调（Fine-Tuning）的方法（MCTS+L+FT），以检验 ABC-RL 与持续微调策略的优劣。 * 训练与搜索细节：RL 智能体训练了 50 个周期。在线搜索时，每个测试电路给定 100 次综合运行的预算（即最多尝试 100 个不同的配方）。
四、 主要研究结果
1. ABC-RL 与现有最佳方法的全面对比 实验结果表明，ABC-RL 在绝大多数测试电路上取得了最优或接近最优的性能。 * QoR 提升：在全部 20 个测试电路上，ABC-RL 取得了最高的几何平均 ADP 降低率，达到 25.3%（相对于基准 resyn2）。这显著超越了此前的最佳方法 SA+Pred（19.7%）和纯 MCTS（19.8%），也优于没有检索机制的 MCTS+Learning 基线（20.7%）。具体到不同基准套件，在 MCNC、EPFL 算术和 EPFL 控制电路上，ABC-RL 均展现出稳定的优势。 * 收敛速度与运行时优势：ABC-RL 通常能以更少的搜索迭代次数达到更高的 ADP 降低水平。在 iso-QoR 条件下，ABC-RL 取得了高达 9 倍的运行加速比（几何平均加速比为 3.8倍），这意味着设计师可以用更短的时间获得相同质量的电路，大幅提升了设计效率。 * 解决基线失效问题：研究重点分析了 MCTS+Learning 基线表现不佳的电路（如 square， cavlc）。结果显示，在这些电路上，ABC-RL 通过计算得到较高的 α 值，显著降低了预训练策略的权重，从而成功避免了搜索轨迹的恶化，其性能恢复并超越了纯 MCTS。这直接验证了 α 调节机制的有效性。
2. 专项分析与消融实验 * 面向特定基准训练的智能体：为了探究数据分布的影响，研究者还训练了专门针对单个基准套件（如仅用 MCNC 数据训练）的 ABC-RL 智能体。结果表明，这些“专精”智能体在自己所属的基准类型上表现有时能略优于通用智能体，但在面对其他类型电路时性能会下降，不过仍能普遍优于纯 MCTS。这进一步说明了电路多样性带来的挑战，以及 ABC-RL 通用机制的必要性。 * 与在线微调策略的对比：与从芯片布局领域借鉴的在线微调方法（MCTS+L+FT）相比，ABC-RL 在大多数电路上表现更优。研究表明，在逻辑综合场景下，每个综合步骤（动作）耗时很长（可达数分钟），有限的在线搜索预算限制了微调的效果。而 ABC-RL 轻量级的检索和调制机制，在不进行昂贵微调的情况下，就能更高效地适应新电路。 * 架构选择的影响：消融实验证实了使用 BERT Transformer 编码操作序列的重要性。与使用简单编码或 LSTM 的变体相比，基于 BERT 的编码器能更好地捕捉序列上下文，带来了明显的 QoR 提升（几何平均 ADP 降低从 21.2% 提升至 25.3%）。
五、 研究结论与价值
本研究提出了 ABC-RL，一种创新的、检索引导的强化学习框架，用于解决逻辑综合中自动化高质量综合配方搜索的难题。其核心贡献在于识别并解决了该领域一个关键问题：由于硬件设计的多样性导致的训练-测试分布偏移，这使得简单的“预训练+搜索”模式可能失效。
ABC-RL 通过一个轻量级的最近邻检索机制，量化测试电路的新颖性，并据此动态调节一个调制参数 α，从而在在线 MCTS 搜索中自适应地平衡预训练历史经验与纯探索。该方法确保了在面对熟悉设计时能充分利用历史数据加速优化，在面对全新设计时又能避免被误导，保障了搜索的鲁棒性。
实验证明，ABC-RL 在多个标准基准测试上，在结果质量（QoR）和优化速度（Runtime） 方面均显著超越了当前最先进的方法。这不仅为逻辑综合这一具体 EDA 问题提供了强大的新工具，其轻量级、应对分布偏移的检索引导思想，也可能适用于其他在线成本高昂、且存在训练测试分布偏移的强化学习与组合优化问题。
六、 研究亮点
七、 其他有价值内容
研究附录提供了丰富的补充材料，包括：逻辑综合与 ABC 工具更详细的背景介绍；MCTS 算法的详细伪代码；ABC-RL 策略网络预训练过程的完整算法描述；网络架构（特别是 GCN 部分）的详细设计理由与参数；奖励函数归一化等实验细节；所有测试电路的详细特征（输入/输出/节点数/层级）；以及大量额外的实验结果图表，全面展示了 ABC-RL 在各电路上的收敛曲线、与对比方法的详细对比等，确保了研究的可复现性。这些内容为其他研究者深入理解和复现本工作提供了坚实基础。