基于忆阻强化学习的双层规划布局优化方法，结合神经动态估计策略

《Journal of Computational and Applied Mathematics》：Bilevel programming optimization of floorplanning layout based on memristive reinforcement learning with strategy of neurodynamic estimate

　　**摘要**
随着摩尔定律的终结，集成电路设计自动化将有助于在硬件与人工智能之间建立一种共生关系。作为多层次、多目标的NP难问题，平面布局优化受到了许多学者的重视。传统的数值方法容易陷入局部最优解。作为一种非易失性存储器器件，忆阻器在断电后仍能保留存储的信息。利用这一特性，我们首先探讨了忆阻器克服优化方法（如交替方向乘子法ADMM）常见缺陷的潜力，并证明了其在这一应用场景中的有效性。随后，基于中央处理单元架构，本文创造性地引入了一种神经动态优化变异技术，并结合忆阻器的非易失性原理，设计了一种基于忆阻强化学习的芯片布局优化算法——MRL-NE。

**引言**
芯片布局问题和机场选址问题都属于运筹学与规划领域中的位置决策问题，但两者之间存在显著差异：机场的容量相对较小，可被视为一个“质量点”；而在芯片布局问题中，宏观模块是各种功能单元的集成体，不能被视为独立粒子。实际上，芯片布局优化是芯片设计过程中最为复杂且耗时的环节之一，其目标是在芯片平面上（2D网格）布置网表，以最小化功耗、性能和面积（PPA），同时还要考虑密度和布线拥挤限制。通常情况下，布局要求将集成电路单元放置在固定区域内，并在单元不相互重叠的条件下优化相关指标。在先进工艺的设计规则下，布局阶段需要考虑众多物理设计规则。如何快速有效地设计模型和算法来处理芯片布局问题，是当前乃至未来很长时间内面临的关键挑战[1]。目前的芯片布局算法可分为三类[2][3]：基于模拟退火的算法[3]、基于划分的算法[4][5]以及基于分析的方法[6]。1) 基于模拟退火的算法利用模拟退火机制调整单元位置以优化布局，但效率较低且缺乏扩展性；2) 基于划分的布局算法通过自顶向下递归划分电路和布局区域，并将子电路分配到子区域内，直至子电路足够小，该算法有效且易于扩展，但子问题之间的信息缺失会限制解决方案的质量；3) 基于分析的布局方法将布局问题转化为包含芯片面积、线性长度目标函数和元素互不重叠约束的数学规划问题，通过不同平滑技术处理目标与约束，并构建多种优化算法或启发式方法来求解布局优化模型，这类算法可以获得更好的解决方案质量。
近期，强化学习[7]在自动设计、推荐系统等多个领域引起了广泛关注[8][9][10][11][12]。对于宏观模块的布局，除了考虑不同模块组合对最终芯片面积的影响外，还需考虑模块的排列顺序、角度和位置等因素。由于传统数学优化方法在这一领域的进展有限，基于强化学习的芯片布局优化方案极具前景。
本文的贡献可归纳为：1) 创新地将忆阻器模型引入强化学习中，使智能体能够根据历史经验做出决策并强化学习行为；2) 首次将布局与路由问题转化为双层优化问题，并用强化学习策略解决该问题；3) 将传统机器学习算法与忆阻器模型相结合，验证了基于忆阻器的非易失性学习策略相较于重启、混沌和随机化方法的优越性。

**总体而言**，所提出的MRL-NE算法为现代集成电路设计工作流程带来了潜在优势，尤其是在应对日益复杂的物理设计优化方面。通过结合忆阻器驱动的学习与神经动态优化，我们的方法为处理平面布局问题的多目标特性提供了新的途径。双层优化框架以结构化方式优先考虑面积优化，同时兼顾线长减少，这与工业实践中的设计优先级一致。从实现角度来看，使用忆阻器模型为未来开发更高效EDA工具指明了方向。这项工作标志着探索新兴存储技术在芯片设计自动化中应用的可能性的初步尝试，尽管仍需进一步研究以全面评估其在多种设计场景和技术节点中的实际适用性。

本文余下部分的组织结构如下：第2节回顾了 ridge回归和具有时变系数的固定时间梯度动态的基本概念，这些内容为MRL算法中确定宏观模块旋转状态提供了理论基础；第3节从点质量设施选址问题出发，扩展到具有物理范围的芯片宏观模块布局问题；第4节详细介绍了基于神经动态估计策略（MRL-NE）的忆阻强化学习算法在芯片布局优化中的应用；第5节验证了基于忆阻器机制的点质量设施选址问题的有效性，证明了这种非易失性存储策略相较于随机化、聚类和混沌方法的优越性；第6节通过与其他十种算法的比较，展示了MRL-NE方法在芯片宏观模块布局问题中的优越性；第7节对本文进行了总结并探讨了未来研究方向。

**节选内容**
**Ridge回归**
假设函数 hβ(x1, x2, ?, xn) = β0 + β1x1 + ? + βnxn 的矩阵表示为：
hβ(x) = Xβ
其中 m 表示样本数量，n 表示样本特征的数量，X ∈ Rm×n，hβ(?) 是 m×1 向量，β 是 m×1 向量，X 是 m×n 矩阵。定义损失函数为：
Jβ(β) = 1/2(Xβ ? Y)T(Xβ ? Y)
其中 Y 是样本的 m×1 输出向量。对变量 β 求偏导数得：
?J(β)/?β =XT(Xβ ? Y) = 0
**基于位置的服务（LBS）**
作为当前信息获取的重要技术手段，无线定位技术在航空航天、导航、电子信息等领域具有广泛的应用前景[14][15][16]，包括卫星定位、移动通信系统定位、雷达定位等，这些技术可实现距离等关键信息获取。

**基于神经动态估计（MRL-NE）的芯片布局优化**
在本节中，我们重点关注芯片布局问题的解决。对于芯片布局优化，需要综合考虑芯片宏观模块的放置顺序、角度和位置。当芯片整体面积较小时，如何调整布局以最小化布线长度是一个重要的挑战，这归结为双层规划问题。

**基于忆阻器机制的点质量设施选址问题**
LAAA算法对设施的初始位置敏感。在本节中，我们提出了一种新的脉冲忆阻横条阵列算法来搜索CMSWP问题的全局最优解（见图2）。对于单个忆阻器，纳米器件中带电漂移粒子的位置决定了其电阻状态；实际上，为突破传统非冯·诺依曼架构的瓶颈，忆阻横条阵列已被用于优化。

**基于MRL-NE的芯片布局优化测试**
在本节中，我们将MRL-NE算法应用于CPU芯片布局问题，获得了最优的放置与布线结果 (Lbest, Sbest) = (400, 280.3754)（见图9）。

**结论**
本文提出了MRL-NE算法用于芯片布局优化，展示了其在应对复杂布局挑战方面的潜力。忆阻器驱动的非易失性学习机制实现了优化经验的跨迭代保留，而神经动态估计提供了数学上可靠的收敛保证。从实际应用角度来看，该方法有效解决了面积与线长之间的权衡问题，符合行业设计的实际需求。