谷歌AI布局论文解读1：翻译部分

作者: 邱奕杭 | 来源:发表于2020-05-13 21:49 被阅读0次

标题:Chip Placement with Deep Reinforcement Learning

用深度强化学习进行芯片布局。对深度强化学习的理解是：强化学习有agent、environment、reward、action等组成部分，就是一个智能体（agent）在一个未知的环境（environment）中，不断摸索，将动作（action）作用于环境，环境反馈奖励（reward）给智能体，然后智能体根据奖励来更新这个产生动作的决策函数。当环境越来越复杂，这个决策函数进行决策和实现起来就越来越困难，而深度神经网络正好具有强大的拟合能力，所以可以将这个决策函数用深度神经网络来代替，这样就形成了深度强化学习。

摘要

概述：基于学习的方法来进行芯片布局
特点：可以从过去的经验中学习，并随着时间不断改善。接受训练的芯片块数量越多，对之前没见过的芯片块进行布局优化时速度越快。
方法概述：将芯片布局问题转化为强化学习问题，通过训练agent往芯片画布上放置芯片网表的节点。
关键步骤：
1.为了可以推广到对之前没见过的芯片块的优化，选取有代表性的学习加入到预测布局效果的监督任务中
2.通过设计一个神经网络，可以准确预测各种芯片网表和其布局的奖励，从而可以生成输入网表的丰富特征嵌入。
3.借助这个架构将策略网络和值网络用到迁移学习中。
结果：最小化PPA（功耗性能面积），6个小时完成的设计将优于或媲美于专家花几周完成的设计。

1.引言

计算机系统和硬件性能的提升促进了AI技术的飞速发展，但是在后摩尔定律和Dennard缩放比例定律的作用下，为了满足AI算力的指数级增长，硬件逐渐趋于专用化。一般芯片设计周期需要几年，减少芯片设计的时间才能使得硬件更好地适应AI的飞速发展。我们认为AI可以用于缩短芯片设计周期，从而让硬件和AI建立共生关系，彼此互相推动。

我们提出了基于学习的芯片布局方法。目标是将宏（例如SRAMs）和标准单元（即逻辑门）的网表图放置到芯片画布上，在考虑布局密度和布线拥塞的约束下优化芯片的功耗性能和面积。尽管在这个问题上已经有很多年的研究，但是始终离不开专家用现有的布局工具对此进行几周的迭代设计工作，以得到满足多重约束的芯片设计方案。问题的复杂性来自网表图的大小(数百万到数十亿个节点)、用于放置这些图的网格粒度、以及用EDA工具评估和计算相关指标的成本。尽管将问题分解为更易于管理的子问题（例如将节点分组为几千个集群并减小网格的粒度），状态空间仍比目前已成功应用的基于学习的方法要大几个数量级。

为了解决这个难题，我们将芯片布局转化为强化学习问题，通过训练一个agent（例如RL 策略网络）来优化布局。在每次训练迭代中，芯片块的所有宏均由agent顺序放置，然后通过力导向方法放置标准单元。训练以agent 每一次芯片布局得到的reward作为指导。

据我们所知，上述的方法是目前第一种具有泛化能力的布局方法，这意味着它可以利用之前放置网表所学到的知识来为新的网表生成布局方案。随着芯片数量和种类的增多，agent可以更高效地为新的芯片块生成优化布局方案，这使未来的芯片设计工程师可以借助具有丰富布局经验的agent进行芯片布局工作。

我们的方法具有从经验中学习并随着时间的推移而改进的能力，这为芯片设计人员开辟了新的可能性。与最新的基准相比，我们的方法可以在真正的AI加速器芯片（Google TPU）上实现出色的PPA。此外，我们的方法可在6小时内产生优于或媲美于专家人工设计的布局，而以往性能最高的方案则需要人类专家耗费几周时间才能获得。尽管我们主要借助AI加速器芯片进行方法评估，但这个方法可以推广应用于任何芯片的布局优化。

2.相关工作

全局布局是芯片设计中的长期挑战，需要对日益复杂的电路进行多目标优化。自1960年以来，提出了很多方法，可以分为三大类：1）基于分区的方法，2）随机/爬山方法，以及3）解析求解器的方法。

自1960年以来，工业界和学术界采用了基于分区的方法来进行芯片的全局布局，此外还采用了基于电阻网络的方法。这些方法的特点是分而治之；即递归划分网表和芯片画布，直到子问题足够小为止，此时使用最佳求解器将子网表放置到子区域中。这类方法执行起来非常快，并且它们的层次结构也允许它们被划分为任意大的网表。但是，通过孤立地优化每个子问题，这类方法牺牲了全局优化的质量，尤其是布线拥塞。此外，一个较差的早期分区可能导致最终无法调整的芯片布局。
在1980年代，出现了分析方法，但很快被随机/爬山算法取代，特别是模拟退火算法。可以用冶金的过程来解释模拟退火，即在冶金时先加热金属，然后逐渐冷却，诱导其退火到能量最佳的晶体表面。模拟退火将随机的扰动应用于一个给定的芯片布局（例如宏的移位，交换或旋转），然后测量其对目标函数的影响（例如半周线长）。如果扰动是一种改善，则将其应用；如果不是，它仍然以一定的概率被继续应用，称之为温度。温度初始化为一个特定值，然后逐渐退火至较低值。尽管模拟退火算法可以产生高质量的布局方案，但是运行速度非常缓慢且难以并行化，因此无法推广应用到1990年代及以后日益大型和复杂的电路。
1990年至2000年代芯片布局有三个典型方法，分别是多层划分的方法、解析技术例如力导向方法、以及非线性优化器的方法。二次方法的再次成功，部分原因是算法的进步，但也归功于现代电路的大尺寸（1000万-1亿个节点），这证明了将放置问题近似为放置零面积节点的合理性。但是，尽管二次方法具有较高的计算效率，但是与非线性方法相比，它们往往较不可靠，并且产生的布局质量较低。
非线性优化使用平滑的数学函数来估算成本，例如线长的对数和表达式、加权平均模型，以及布局密度的高斯模型和Helmholtz密度模型。将这些函数通过拉格朗日惩罚或松弛组合为单目标函数。由于这些模型的复杂性较高，因此有必要采用分层方法，放置的是集群而不是单个节点，然而这会降低布局的质量。
过去十年见证了现代解析技术的兴起，包括更高级的二次方法，以及最近的基于静电的方法，如ePlace和RePlAce。将网表布局建模为一个静电系统，ePlace提出了密度损失的新公式，其中网表的每个节点（宏或标准单元）类似于带正电荷的粒子，节点面积对应于粒子的电荷量。在这种设定下，节点之间相互排斥的力与其电荷量（节点面积）成正比，密度函数和梯度对应于系统的势能。可以对这种基于静电的方法进行改进，以解决标准单元放置和混合尺寸放置的问题。RePlAce是一种最新的混合尺寸放置技术，它通过引入局部密度函数进一步优化了ePlace的密度函数，该函数根据每个容器的大小调整惩罚因子。第5节对最新的RePlAce算法的性能与我们的方法进行了比较。
最近的工作提出一种方法，即通过训练模型来预测给定宏的布局违反DRC的次数。DRC是确保所放置和连线的网表符合输出要求的规则。未来生成具有较少DRC的宏布局，有相关工作使用了上述训练模型的预测作为模拟退火中的评估函数。尽管这项工作代表了一个有趣的方向，但它报告的网表结果不超过6个宏，远远少于任何现在的芯片块，而且该方法未对布局和布线进行任何优化。因此在后续的优化过程中，布局和布线可能会发生巨大变化，实际DRC也会发生相应变化，从而使模型预测无效。另外，尽管芯片布局必须遵守DRC标准，但是宏放置的首要目标还是对线长、时序（例如最坏的负松弛（WNS）和总的负松弛（TNS））、功耗和面积进行优化。上述工作没有考虑到这些首要的指标。
为了解决这个经典问题，我们提出了一类新的方法：端到端基于学习的方法。这种方法与解析求解器（尤其是非线性求解器）最为相似，因为它们都是通过梯度更新来优化目标函数的。但是，我们的方法与以往的方法不同之处在于它可以从过去的经验中学习，以在新的芯片上生成更高质量的布局方案。与现有的从头开始优化每个芯片的布局的方法不同，我们的方法利用了先前芯片布局获得的知识，使得随着时间推移芯片的布局变得更好。此外，我们的方法可以直接对指标进行优化，例如线长、布局密度和布线拥塞，而无需像其他方法一样定义对应指标函数的凸近似。我们的公式不仅易于整合新的代价函数，而且能够根据给定芯片块的需求（例如，关键时序或功耗约束）来权衡它们的相对重要性。
域适应是训练策略的问题，该策略可以跨多种经验学习并迁移所获得的知识，从而在新的未见过的情形下表现更好。对于芯片布局，域适应包括在一组芯片网表中训练策略，并将该策略应用于新的网表。近来，用于组合优化的域适应已经成为趋势。尽管先前工作的重点在于使用从优化问题先例中学到的域知识来加快对新问题的策略训练，但我们提出了一种方法，该方法首次可以通过利用过去的经验来生成更高质量的结果。与从头开始训练策略相比，我们使用的域适应方法不仅可以得到更好的结果，而且还将训练时间减少了8倍。

3.方法

3.1 问题重述

我们围绕芯片布局优化问题，将网表的节点（网表就是描述芯片的图形）映射到芯片画布（芯片画布就是一个有界的2D空间）上，从而优化功耗、性能和面积（PPA）。在本节中，我们概述如何将问题表述为强化学习问题，然后详细描述奖励函数，动作和状态的表示，策略结构以及策略更新。

3.2 本文方法概述

我们采用深度强化学习（RL）的方法来解决布局问题，其中agent(策略网络)顺序放置宏；一旦放置了所有宏，就使用力导向法来对标准单元进行大致的布局，如图1所示。RL问题可以表示为马尔可夫决策过程(MDPs)，由四个关键元素组成：

state：所有可能状态的集合（在我们的例子中，状态就是网表在芯片画布上每一个可能的放置情况）。
action：agent所有可能采取的行动的集合（例如，给定当前要放置的宏，可能的动作就是在不违反密度或拥塞等约束下所有可能放置该宏的位置的集合。
state transfer：给定一个state和一个action，下一个state可能的概率分布。
reward：在一个state中采取某个action时得到的奖励。（在我们的示例中，除最后一个action之外的所有action的reward都是0，其中reward是agent的线长和拥塞的负加权和，它需要满足第3.3节中描述的密度约束。）

图1 工作概述图

在初始state，记为 s₀，我们有一个空的芯片画布和一个未放置的网表。最后的状态 s_T 对应于一个完全放置的网表（包括宏和标准单元）。在每一步中，放置一个宏。因此，T 等于网表中宏的总数。在每个时间步 t 中，agent从状态 s_t 开始，执行一个动作 a_t ，然后到达一个新的状态即 s_{t +1}，并从环境中获得一个奖励 r_t （当 t < T 时，reward为0；当 t = T 时，reward 为负代理成本。）

我们把s_t 定义为时间 t 时可用于表征状态的特征串联，包括网表的图形嵌入（包括放置和未放置的节点），当前要放置的宏的节点嵌入，关于网表的元数据（第4节），以及代表将当前节点放置到任一个网格单元的可行性的掩码（第3.3.6节）。

动作空间是第 t^th 个宏的所有可能的放置位置，是第3.3.6节描述的密度掩模的函数。动作 a_t 是由RL策略网络选择的第 t 个宏的单元格位置。

s_{t +1} 是下一个状态，它包含新放置的宏的信息、一个更新的密度掩码，以及对下一个要放置的节点的嵌入。

在我们的公式中，除了最后的 r_T 外，每个时间步的 r_t 都为0，其中 r_T 近似为线长和拥塞的加权和，如3.3节所述。

通过重复地执行这些事件（state、action和reward的序列），策略网络学会采取将累积奖励最大化的行动。当给出每次布局后的累积奖励，我们就可以使用近端策略优化算法（Proximal Policy Optimization, PPO）来更新策略网络的参数。

在这一节中，我们定义奖励为 r，状态为 s ，动作为 a ，以 $\theta$ 为参数的策略网络为 $\pi_{\theta}(a | s)$ ，最后介绍了我们用这些参数来进行优化的方法。

3.3 奖励

我们的目标是在布线拥塞和布局密度的约束下，使功耗、性能和面积最小化。我们真正的reward是EDA的输出，包括线长、布线拥塞、布局密度、功耗、时序和面积。然而，RL策略需要100000个示例才能有效地学习，因此reward函数的快速评估非常重要，理想情况下在几毫秒内就能运行完成。为了有效，这些近似的reward函数也必须与真正的reward正相关。因此，成本应该包含线长，因为它不仅评估成本较低，而且与功耗和性能（时序）相关。我们为线长和布线拥塞定义了近似的代价函数，如第3.3.1节和第3.3.5节所述。

为了将多目标组合成一个单目标的reward函数，我们对agent的线长和拥塞进行加权求和，其中权重可用于权衡两个指标的影响。

我们将布线拥塞视为一种软约束（即较低的拥塞可以改善reward函数）。我们将布局密度作为硬约束，即采取密度不能超过最大密度的action（将节点放置到网格单元上），如第3.3.6节所述。

为了让每次迭代的时间较小，我们对reward函数的计算做了以下近似：

我们使用 hMETIS 将数百万个标准单元分组成数千个集群，这是一种基于归一化最小割目标的分区技术。一旦所有宏被放置，我们使用力导向法来放置标准单元集群，如3.3.4节所述。这样做可以使我们较快地得到一个大致的标准单元布局方案，从而促进策略网络的优化。
我们将网格离散为几千个网格单元，并将宏和标准单元集群的中心放在网格单元的中心。
在计算线长时，我们假设标准单元集群的所有连接都起源于集群的中心。
为了计算布线拥塞成本，我们只考虑前10%最拥塞的网格单元的平均拥塞，如3.3.5节所述。

3.3.1. 线长

我们采用半周线长（HPWL），这常用于对线长的近似。HPWL定义为网表中包含所有节点的边框的半周长。给定边为 i 的HPWL如下式所示：
$\begin{aligned} H P W L(i) &=\left(M A X_{b \in i}\left\{x_{b}\right\}-M I N_{b \in i}\left\{x_{b}\right\}+1\right)(1) \\ &+\left(M A X_{b \in i}\left\{y_{b}\right\}-M I N_{b \in i}\left\{y_{b}\right\}+1\right) \end{aligned}$
其中，x_b 和 y_b 表示网络 i 的 x 和 y 坐标。然后对所有半周长的归一化求和，计算出HPWL的总代价，如式（2）所示。q(i) 是归一化因子，可以通过增加节点数量带来线长成本的增加来提高估计的准确性。N_netlist 是线网的数量。
$H P W L(\text {netlist})=\sum_{i=1}^{N_{n e t t i s t}} q(i) * H P W L(i）(2)$
直观地说，对于给定布局的HPWL大致是其Steiner树的长度，这是布线成本的最低值。

线长还具有关联其他重要指标（例如功耗和时序）的优势。尽管我们没有直接对这些其他指标进行优化，但是我们在表2中可以观察到这些指标例如功耗和时序的高性能（如表2所示）。

3.3.2. 网格行数和列数的选择

给定芯片画布的尺寸，有很多方法可以将2D画布离散化为网格单元。这将影响优化的难度和最终放置的质量。我们把最大行数和列数限制为128，将确定最佳行数和列数视为装箱问题，并根据行和列的浪费空间大小对不同的行数和列数进行排序。在第5节描述的实验中，我们平均使用30行和30列。

3.3.3. 宏放置顺序的选择

为了选择宏的放置顺序，我们对宏从大到小排序，并使用拓扑排序中断连接。通过先放置较大的宏，可以减少后续宏没有放置空间的可能。拓扑排序可以帮助策略网络学习如何将互连的节点放得相互靠近。另一种可能的方法是学习联合优化宏的顺序和它们的位置，选择将action空间的下一步放置在哪个节点上。然而，这种扩大动作空间的方法会显著增加问题的复杂性，我们发现这种启发式方法在实践中是有效的。

3.3.4. 标准单元的布局

为了放置标准单元集群，我们使用了一种类似于经典力导向算法的方法。我们将网表表示为一个弹簧系统，该系统根据 $weight$ x $distance$ 公式，对每个节点施加力，从而使紧密连接的节点相互吸引。我们还引入了重叠节点之间的斥力，以减少布局密度。在施加所有的力后，我们将节点往力矢量的方向移动。为了减少振荡，我们为每一步限制了最大距离。

3.3.5. 布线拥塞

我们在计算agent 拥塞时使用了传统的方法，即使用了基于驱动位置和网络负载的简单确定的布线。布线网络经过每个网格单元时，占用一定数量的布线资源。我们分别跟踪每个网格单元的垂直和水平分配。为了平滑布线拥塞的估计值，我们在垂直和水平方向上运行 $5$ x $1$ 的卷积滤波器。当所有网表的布线完成后，我们取前10%拥塞值的平均值，这个灵感来自MAPLE中的ABA10度量。公式（4）表示的是布线拥塞成本，表示前10%拥塞值的平均值，就是通过这个过程计算得到的。

3.3.6.布局密度

我们将密度视为硬约束，不允许策略网络将宏放置在会导致密度超过目标密度最大值或导致宏重叠的位置。该方法有两个优点：（1）减少了策略网络产生的无效放置的数量；（2）减少了优化问题的搜索空间，使其更易于计算。

标准单元集群的布局应满足以下标准：每个网格单元放置的密度不应超过给定的目标密度阈值。我们在实验中将这个阈值设置为0.6。为了满足这个约束，在每个RL步骤中，我们计算当前的密度掩码，这是一个表示网格单元的二进制 m x n 矩阵，我们可以在不违反密度阈值的情况下将当前节点的中心放置到该掩码上。在从策略网络的输出中选择action之前，我们首先取掩码和策略网络输出的点积，然后取可行位置上的 argmax。这种方法可以防止策略网络生成具有重叠宏或密集的标准单元布局。

我们还可以通过将布局拥塞区域的密度函数设置为1，从而来使放置时能考虑到拥塞（例如时钟带）。

3.3.7. 后处理

为了用EDA工具对放置的效果进行评估，我们基于贪婪思想将宏放置到最近且合理的位置，同时满足最小间距约束。然后，我们确定宏的放置，使用EDA工具放置标准单元并评估放置情况。

3.4. 动作的表示

为了优化策略，我们将画布转换为一个 m x n 的网格。因此，对于任何给定的state，action空间(或策略网络的输出)是当前宏在 m x n 网格上位置的概率分布。这个action就是这个概率分布的 argmax 。

3.5. 状态的表示

我们的state包含了网表图(邻接矩阵)、它的节点特征(宽度、高度、类型等)、边特征(连接数)、当前要放置的节点(宏)、网表和底层技术的元数据(例如布线分配、总连接数、宏、标准单元集群等)。在接下来的小节中，我们将讨论如何处理这些特性来学习芯片布局的有效表示。

4.域迁移：从经验中学到更好的芯片布局

我们的目标是训练RL agent，当他们获得芯片布局的经验时，可以产生更高质量的结果。我们定义布局的目标函数如下：
$J(\theta, G)=\frac{1}{K} \sum_{g \sim G} E_{g, p \sim \pi_{\theta}}\left[R_{p, g}\right] (3)$
这里 $J(\theta, G)$ 是成本函数。agent 由 $\theta$ 参数化的。大小为 $K$ 的网表图数据集用 $G$ 表示，数据集中每个单独的网表写为 $g$ 。 $R_{p, g}$ 指在网表 $g$ 的策略网络中放置 $p$ 时的奖励。
$\begin{array}{r} R_{p, g}=-\text {Wirelength}(p, g)-\lambda \text { Congestion}(p, g) \\ \text {S.t. density}(p, g) \leq \text {max}_{\text {density}} \end{array}(4)$
公式（4）表示我们用于策略网络优化的reward，即在密度约束下的线长和布线拥塞的负加权平均值。reward在3.3节中有详细解释。在我们的实验中，拥塞权重 $\lambda$ 设置为0.01，最大密度阈值设置为0.6。

4.1. 使能迁移学习的监督方法

我们提出一种新的神经架构，使我们能够训练领域自适应策略来进行芯片布局。训练这样一个策略网络是一项具有挑战性的任务，因为包含所有芯片的所有可能放置的状态空间是巨大的。此外，不同的网表和网格大小具有不同的属性，包括节点数量、宏大小、图形拓扑以及画布的宽度和高度。为了解决这个挑战，我们首先关注于学习状态空间的丰富表示。我们的直觉是，能够跨芯片迁移布局优化的策略网络架构也应该能够在推断时将与新的芯片相关的状态编码为有意义的信号。因此，我们提出训练一个能够预测新网表reward的神经网络架构，最终目标是使用这个架构作为我们策略网络的编码层。

为了训练这个监督模型，我们需要一个大的芯片布局数据集和相应的奖励标签。因此，我们创建了一个包含10000个芯片布局的数据集，其中输入是与给定放置相关联的状态，而标签是对该放置的奖励（线长和拥塞）。我们首先选择5个不同的加速器网表，然后为每个网表生成2000个布局，从而构建这个数据集。为了给每个网表创建不同的布局，我们在不同的拥塞权重（从0到1）和随机种子（seeds）下训练了一个香草策略网络（vanilla policy network），并在策略训练过程中收集每种布局的情形。一个未经训练的策略网络从随机权重开始，生成的布局质量较低差，但随着策略网络的训练，生成的布局质量不断提高，这让我们可以收集到具有不同布局质量的数据集。

为了训练一个能准确预测线长和拥塞标签的监督模型，并推广应用到未知的数据，我们开发了一种新的嵌入网表信息的图神经网络结构。图神经网络的作用是在一个大图中提取关于节点类型和连接的信息，并将其转换为低维向量的表示形式，从而可用于后续任务。后续任务例如节点分类、器件放置、连线预测和DRC预测。

我们通过串联节点特征来对每个节点进行向量表示。节点特征包括节点类型、宽度、高度以及 x 和 y 坐标。我们还将节点邻接信息作为输入传递给算法。然后，我们重复执行以下更新：1) 每条边通过将全连接网络应用于中间节点嵌入的聚合表示来更新其表示，2) 每个节点通过取嵌入的相邻边的平均值来更新其表示。节点和边的更新如公式（5）所示。
$\begin{aligned} e_{i j} &=f c_{1}\left(\operatorname{concat}\left(f c_{0}\left(v_{i}\right)\left|f c_{0}\left(v_{j}\right)\right| w_{i j}^{e}\right)\right) (5)\\ v_{i} &=\operatorname{mean}_{j \in \mathcal{N}\left(v_{i}\right)}\left(e_{i j}\right) \end{aligned}$

节点嵌入表示为 $v_{i}$ ，其中 $1<=i<=N$ ， $N$ 是宏和标准单元集群的总数。连接节点 $v_{i}$ 和 $v_{j}$ 的矢量边表示为 $e_{i j}$ 。边 $\left(e_{i j}\right)$ 和节点嵌入 $\left(v_{i}\right)$ 都被随机初始化，并且都是32维矩阵。 $f c_{0}$ 维度是 $32 \times 32, f c_{1}$ 维度是 $65 \times 32$ ，表示前馈网络。 $w_{i j}^{e}$ 是对应边的可学习的 $1 x 1$ 权重值。 $\mathcal{N}\left(v_{i}\right)$ 是 $v_{i}$ 的邻节点。算法的输出是节点和边的嵌入。

我们的监督模型包括：(1) 上述的图数据神经网络，它嵌入了节点类型和网表邻接矩阵的信息。(2) 一个全连接的前馈网络，该网络嵌入元数据，包括底层半导体技术(水平和垂直连线容量)、网络的总数量(边)、宏和标准单元集群、画布大小和网格中的行和列数。(3) 一个全连接的前馈网络(预测层)，其输入是网表图与元数据嵌入的串联，输出是奖励预测。网表图的嵌入是通过在边嵌入上应用简化均值函数来创建的。通过回归训练监督模型，以最小化线长和拥塞的均方根损失的加权和。

这个监督任务使我们可以找到泛化网络列表的奖励预测所必须的特征和架构。为了将此体系结构合并到策略网络中，我们移除了预测层，然后将其用作策略网络的编码组件，如图2所示。

图2 策略和值网络架构图

行和列的不同选择会带来网格大小的不同，为了解决这个问题，我们将网格大小设置为128 x 128，并为小于128行和列的网格大小屏蔽未使用的“L形”部分。

在推理时，为了放置一个新的测试网表，我们加载策略网络的预训练权重，并将其应用于新网表。我们将未进行微调的预训练的策略网络所产生的布局称为“zero-shot”布局。这样的布局可以在不到一秒的时间内生成，因为它只需要预训练策略网络的一个推理步骤。通过微调策略网络，我们可以进一步优化布局质量。这样的方法给了我们极大的灵活性，既可以使用预训练的权值（已经学习了输入状态的丰富表示），又可以进一步调整这些权值以优化特定芯片网表的属性。

4.2. 策略网络架构

图2概述了策略网络（借由公式3中的 $\pi_{\theta}$ 建模）和我们为芯片布局建立的值网络架构。这些网络的输入是网表图（图邻接矩阵和节点特征）、当前要放置的节点ID，以及网表和半导体技术的元数据。如前所述，网表图通过我们提出的图神经网络架构。该图神经网络生成（1）部分布局的图嵌入和（2）当前节点嵌入。我们使用一个简单的前馈网络来嵌入（3）元数据。将这三个嵌入向量连接起来以形成状态嵌入，然后将其传递到前馈神经网络。将前馈网络的输出馈送到策略网络（由5个反卷积层和Batch归一化层组成），以生成动作的概率分布，并传递到价值网络（由前馈网络组成）以预测输入状态的值。注意到，反卷积层的核大小为3x3，步进为2，分别有16、8、4、2和1个滤波通道。

4.3. 策略网络更新：训练参数 $\theta$

在方程3中，目标是训练策略网络的 $\pi_{\theta}$ ，使其在策略网络的布局分布上reward( $R_{p, g}$ )的期望值( $E$ )最大化。为了优化这个参数，我们使用了近端策略优化算法(PPO)，其目标如下:
$L^{C L I P}(\theta)=\hat{E}_{t}\left[\min \left(r_{t}(\theta) \hat{A}_{t}, \operatorname{clip}\left(r_{t}(\theta), 1-\epsilon, 1+\epsilon\right) \hat{A}_{t}\right)\right]$
其中 $\hat{E}_{t}$ 代表每一时步 $t$ 的期望值， $r_{t}$ 代表新策略和旧策略的比率， $A_{t}$ 是每一时步 $t$ 的估计优势。

5. 结果

本节将对我们的方法进行评估，并回答以下问题：我们的方法是否支持域迁移和从经验中学习？使用预训练策略对结果的质量有什么影响？与最先进的基准相比，我们方法生成的布局质量如何？我们还仔细分析了生成的布局的外观，并对策略网络作出相关决定的原因进行分析。

5.1. 迁移学习的结果

图3对比了预训练和从零开始训练这两个策略网络所产生的布局质量。Zero-shot指我们将预训练的策略网络应用到一个没有微调的新网表上，结果可以在不到一秒的时间内得到一个布局。我们还展示了在2小时和12小时内针对一个设计的预训练策略网络进行微调的结果。从零开始训练的策略网络需要花更长的时间才能达到收敛，训练24小时后得到的结果比微调的策略网络训练12小时后的结果还要差。这证明了经过学习得到的权重和接触多种不同类型的设计，可以帮助我们在更短的时间内对一个新的设计实现更高质量的布局。

图3 不同训练策略的结果对比

图4显示了对Ariane RISC-V CPU分别采取从零开始训练和预训练的策略网络的收敛图。预训练的策略网络在微调开始时具有较低的布局成本。随后，预训练的策略网络收敛到更低的布局成本。当收敛到相同的值时，从零开始训练的策略网络要多花30个小时。

图4 预训练和从零开始训练收敛时间的对比

5.2. 从较大的数据集中学习

随着我们在更多芯片块上训练，我们能够加快训练过程并更快地产生更高质量的结果。图5（左）显示了更大的训练数据集对性能的影响。训练数据集是从内部TPU块创建的。训练数据由各种模块组成，包括内存子系统、计算单元和控制逻辑。当我们将训练数据集的块数从2增加到5，最后增加到20时，zero-shot和微调相同小时的这两种策略网络均会产生更好的布局。图5（右）显示了在对策略网络进行训练时测试数据的布局成本。我们可以看到，对于较小的训练数据集，策略网络快速产生过拟合，并且测试数据的性能下降，而对于最大的数据集，策略网络产生过拟合的时间更长些。在较大的数据集上预训练策略网络在测试数据上会产生更好的结果。该图表明，随着我们在更多不同种类的芯片块中训练策略网络，尽管预训练时间会更长，但策略网络变得不容易产生过拟合，并且可以更好地为新的芯片块找到优化的位置。

图5 训练集的大小对布局成本和训练时间的影响

5.3. 可视化分析

图6显示了Ariane RISCV CPU的布局结果。左图是zero-shot策略网络的布局，右侧是经过微调的策略网络的布局。zero-shot可以对未见过的芯片生成布局。zero-shot策略网络将标准单元放在由宏包围的画布中心，这非常接近最优布局。微调后，宏的放置变得更规则，并且中心的标准单元区域变得更不拥塞。

图6 芯片布局可视化

图7给出了布局的可视化：左图是手动布局的结果，右图是我们方法得到的结果。白色区域是宏的布局，绿色区域是标准单元的布局。我们的方法是在标准单元周围创建宏的环状布局，从而减少了总线长。

图7 两种方式的布局可视化

5.4. 与基准方法的比较

在本节中，我们将我们的方法与3种基准方法进行比较，分别是：模拟退火、RePlAce和人类专家基准。我们的方法在最大的数据集（包含20个TPU块）上使用预训练的策略，然后在5个未见过的目标块上进行微调，分别记为块1到块5。数据集包括各种模块，包括内存子系统、计算单元以及控制逻辑。出于保密，我们无法透露这些块的详细信息，但给出块的规模，即每个块最多包含数百个宏和数百万个标准单元。

和模拟退火的比较：模拟退火（SA）是一种功能强大但缓慢的优化方法。但是，像RL一样，模拟退火能够优化任意不可微的成本函数。为了了解RL的相对样本效率，我们进行了实验，将RL替换为基于模拟退火的优化器。在这些实验中，我们使用与以前相同的输入和成本函数，但是在每个事件中，模拟退火优化器都会放置所有宏，然后执行FD步骤放置标准单元集群。根据SA更新规则，使用指数衰减退火进度表接受每个宏的布局。SA需要花费18个小时才能收敛，而我们的方法花费不超过6个小时。

为了公平比较，我们通过扫描不同的超参数进行了多次SA实验，包括最小和最大温度、种子和最大SA集，以使得SA和RL在模拟中花费相同的CPU时间并搜索相同数量的状态。表1列出了实验的最低成本结果。由表可知，与我们的方法相比，即使有更多的时间，SA也很难产生高质量布局，并且产生的布局平均线长比我们的方法高14.4%，平均拥塞高24.1%。

表1 SA和RL结果对比
与RePIAce和人工布局的比较：表 2 将我们的结果与最先进的RePlIAce 和人工布局进行了比较。人工布局是由一个芯片设计团队生成的，涉及许多布局优化的迭代，由商业EDA工具在几周内提供反馈指导。

关于RePlAce，我们有相同的优化目标，即优化芯片布局，但是我们使用不同的目标函数。因此，我们没有比较不同成本函数的结果，而是着眼于商业EDA工具的输出结果。为了进行比较，我们调整了我们的方法和RePlAce方法生成的宏布局，并允许EDA工具按照默认设置来进一步优化标准单元的布局。然后，得到总线长、时序（最差（WNS）和总（TNS）负松弛）、面积和功率指标的输出报告。如表2所示，在满足设计要求下，我们的方法得到的布局结果优于RePLAce。给定底层半导体技术相关约束，如果WNS明显高于100 ps时，或者水平和垂直的任一拥塞超过1％导致一些RePLAce（块1、2、3）布局不可用时，则在设计后期这些块的布局无法满足时序约束。这些结果表明，我们这个考虑到拥塞的方法可以有效生成符合设计标准的高质量布局。

表2 我们的方法与RePLAce方法、专家布局方法的对比
RePIAce比我们的方法更快，因为它收敛时间为1到3.5小时，而我们的方法收敛时间为3到6小时。可是，我们的方法具有一些很基本的优点：1) 我们的方法可以轻松对各种不可微的成本函数进行优化，而无需建立这些成本函数的可微分等价方程。例如，虽然很容易将线长建模为凸函数，但对于布线拥塞或时序却不是这样。 2) 随着策略学习到更多的芯片块，我们的方法能够随着时间的推移而不断改进；3) 我们的方法能够满足各种设计约束，例如不同形状的块。

表2还显示了由人工专家设计的结果。我们的方法和人类专家一样，都可以生成可行的布局，即都满足时间和拥塞设计标准。在WNS、面积、功耗和线长方面，我们的方法得到的结果胜过或者可以与专家设计的结果相媲美。此外，我们的端到端基于学习的方法只需要不到6个小时，而手工基线的方法则需要专家多次参与缓慢的迭代优化工作，这可能需要数周时间。

5.5. 讨论

进一步优化我们方法的可能：有多种机会可以进一步提高我们方法的布局质量，例如标准单元的分区、行数和列数的选择、以及放置宏的顺序等。我们的方法还可以从其他标准单元布局算法得到进一步优化。目前，考虑到标准单元较快的运行速度，我们使用力导向法对其进行布局。可是，我们相信有更好的方法对标准单元进行布局，例如RePlAce和DREAMPlace，这些方法可以生成更准确的标准单元布局，以指导训练策略网络。这将会很有用，因为如果策略网络在宏布局如何影响标准单元布局和最终指标方面有更清晰的信号，则它可以学习做出更优化的宏布局决策。
方法的推广和应用：本文的工作只是域适应策略应用于优化问题的一个例子，可以扩展应用到芯片设计的其他阶段，例如架构和逻辑设计、逻辑综合和验证，其共同目标是训练机器学习的模型并让模型随着学习实例增加而不断改善。基于学习的方法还可以在芯片设计的流程中执行关于设计空间探索和协同优化的工作。

6. 总结

本文针对复杂且重要的芯片布局问题，提出了一种基于强化学习的方法，使迁移学习成为可能。由于RL agent在大量的芯片网表上学习布局经验，因此芯片布局的质量将变得更快更好。实验证明了我们的方法优于最先进的基准，在现代加速器布局方面优于或媲美于人类专家设计。我们的方法是端到端的，可在6小时内完成布局，而最好的基准需要人类专家花几周时间进行多次迭代优化工作。

拓展学习链接

[RL]https://zh.wikipedia.org/wiki/%E5%BC%BA%E5%8C%96%E5%AD%A6%E4%B9%A0
[Dennard缩放比例定律]https://www.jiqizhixin.com/articles/2019-10-23-13
[什么是baseline]https://blog.csdn.net/Lison_Zhu/article/details/97554928
[初窥模拟退火]https://zhuanlan.zhihu.com/p/47628209
[迁移学习的全面概述]https://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650724800&idx=2&sn=0d5e47e071c346eb4a485980deee5744&chksm=871b1dbeb06c94a81b74afcde32d759b7118d60e60b710570a2d6cf53fbe2a9badaed44c5f05#rd
[力导向布局算法]https://www.jianshu.com/p/d3c64a39535a
[拓扑排序]https://www.jianshu.com/p/b59db381561a