谷歌论文:使用深度强化学习的芯片布局

摘 要

在本项目中,我们提出了一种基于学习的芯片布局方法,这是芯片设计过程中最复杂,最耗时的阶段之一。与以前的方法不同,我们的方法具有从过去的经验中学习并随着时间的推移而不断改进的能力。特别是,当我们训练更多的芯片模块时,我们的方法变得更擅长为先前未见的芯片快速生成优化的布局。为了获得这些结果,我们将布局作为强化学习(RL)问题提出,并训练代理将芯片网表的节点放置到芯片蓝图上。为了使我们的强化学习策略能够泛化到未见的芯片模块,我们在预测布局质量的监督任务中放置了表征学习。通过设计一种可以准确预测各种网表及其布局上的奖励的神经体系结构,我们能够对输入网表生成丰富的特征嵌入。我们将此架构用作我们的策略和价值网络的编码器,以实现迁移学习。我们的目标是使PPA(功率,性能和面积)最小化,在不到6小时的时间内,我们的方法可以生成具有媲美或超过人工的现代加速器网表上的布局,而在同样条件下,现有人类专家可能需要几个星期来完成同样的工作。

一、介绍

随着计算机系统和硬件的显着进步,人工智能的快速进步得以实现. 但是随着摩尔定律和Dennard缩放技术的终结,世界正朝着专用硬件发展,以满足AI对计算的需求呈指数增长。然而,当今的芯片需要花费数年的时间进行设计,这使我们不得不为从现在起2-5年的机器学习(ML)模型进行优化而进行的推测性任务。大量缩短芯片设计周期将使硬件更好地适应AI迅速发展的领域。我们认为正是AI本身将提供缩短芯片设计周期的方法,从而在硬件和AI之间建立起共生关系,而两者之间又相互促进。

在本文中,我们提出了一种基于学习的芯片布局方法,这是芯片设计过程中最复杂,最耗时的阶段之一。目的是将宏(例如SRAM)和标准单元(逻辑门,例如NAND,NOR和XOR)的网表图布局在芯片画布上,以优化功耗,性能和面积(PPA),同时遵守对布局密度和布线拥塞的限制。尽管对此问题进行了数十年的研究,人类专家仍然有必要使用现有的放置工具进行数周的迭代,以产生满足多方面设计标准的解决方案。问题的复杂性来自网表图(graph)的大小(数百万到数十亿个节点),放置这些表图的网格的粒度以及计算真实目标指标所需的高昂成本(以使用行业标准的电子设计自动化(EDA)工具评估单个设计, 也需要从几小时到几天)。即使在将问题分解为更易于管理的子问题(例如,将节点分组为几千个群集并减少网格的粒度)之后,状态空间仍比最近成功的基于学习的方法所能处理的问题大几个数量级。

为了解决该挑战,我们将芯片布局作为强化学习(RL)问题,在此我们训练代理(例如RL策略网络)以优化布局。在每次训练迭代中,芯片块的所有宏都由RL代理顺序放置,然后通过力导向方法(force-directed method)放置标准单元(Hanan & Kurtzberg, 1972; Tao Luo & Pan, 2008; Bo Hu & Marek-Sadowska, 2005; Obermeier et al., 2005; Spindler et al., 2008; Viswanathan et al., 2007b;a). 训练由针对每个代理的芯片布局的快速但近似的奖励信号指导。

据我们所知,此次提出的方法是具有首个具有泛化能力的布局方法,这意味着它可以利用从以前的网表布局中学到的知识为新的从未见的网表生成布局。我们证明,尤其随着我们的代理接触到更大数量和更多种类的芯片,它在为新的芯片块生成优化的布局方面变得既快又好,这使我们更接近能为芯片设计者提供具有丰富的芯片布局经验帮助的人工智能的未来。

我们相信,我们的方法能够从以往经验中学习并随着时间的推移而改进,从而为芯片设计人员开辟了新的可能性。我们证明,与最新的基准相比,我们可以在真正的AI加速器芯片(Google TPU)上实现出色的PPA。此外,我们的方法可以在6小时内生成优于或媲美人类专家芯片设计人员的布局. 而现代芯片中数十个区块的每个区块的替代方案都需要人类专家花费数周的时间来获得新能最高的替代方案 。尽管我们主要在AI加速器芯片上进行评估,但我们提出的方法可广泛应用于任何芯片布局优化。

二、相关工作

全局布局是芯片设计中的长期挑战,需要对不断增长的复杂性进行多目标优化。自1960年代以来,已经提出了许多方法,迄今为止分为三大类:1)基于分区的方法,2)随机/爬山方法,以及3)解析求解器(analytic solver)。

从1960年代开始,工业和学术实验室对全局布局问题采用了基于分区的方法,提出了(Breuer,1977; Kernighan,1985; Fiduccia&Mattheyses,1982),以及基于电阻网络的方法(Chung -Kuan Cheng和Kuh,1984;Ren-Song Tsay等人,1988)。这些方法的特点是分而治之。递归地划分网表和芯片画布,直到出现足够小的子问题为止,此时,使用最佳求解器将子网表放置到子区域上。这样的方法执行起来非常快,并且它们的层次结构性质允许它们扩展到任意大的网表。但是,通过隔离地优化每个子问题,基于分区的方法牺牲了全局解决方案的质量,尤其是路由拥塞问题。此外,较差的早期分隔可能导致无法挽回的最终布局。

在1980年代,出现了分析方法,但很快被随机/爬山算法取代,特别是模拟退火(Simulated annealing)(Kirkpatrick等,1983; Sechen和Sangiovanni-Vincentelli,1986; Sarafzadeh等,2003)。模拟退火(SA)的名称类似于冶金,其中先加热金属,然后逐渐冷却以诱导或退火能量最佳的晶体表面。SA将随机扰动应用于给定的位置(例如,宏的移位,交换或旋转),然后测量其对目标功能的影响(例如,第3.3.1节中所述的半周线长)。如果微调是一种改善,则将其应用;如果不是,它仍然以某种可能性应用,称为温度。将温度初始化为特定值,然后逐渐退火至较低值。尽管SA产生了高质量的解决方案,但它非常缓慢且难以并行化,因此无法扩展到1990年代及以后日益大型和复杂的电路。

1990年代至2000年代的特征是采用多层划分(multi-level partitioning) 方法(Agnihotri等人,2005; Roy等人,2007),以及分析技术的复兴,如力导向(force-directed)方法(Tao Luo&Pan,2008); Bo Hu&Marek-Sadowska,2005; Obermeier等,2005; Spindler等,2008; Viswanathan等,2007b; a)和非线性优化器(non-linear optimizers)(Kahng等,2005; Chen等。,2006)。二次方法(quadratic methods)的更新成功部分归因于算法的进步,也归功于现代电路的大尺寸(10-1亿个节点),这证明了将放置问题近似为放置面积为零的节点是合理的。但是,尽管二次方法的计算效率很高,但与非线性方法相比,它们的可靠性通常较低,并且产生的质量较低的解决方案.

非线性优化使用平滑的数学函数来估算成本,例如线长的对数总和(William等,2001)和加权平均(Hsu等,2011)模型以及高斯(Chen)模型。等(2008)和Helmholtz密度模型。然后使用拉格朗日罚分或松弛将这些函数组合为单个目标函数。由于这些模型的较高复杂性,因此有必要采取分层的方法,放置簇而不是单个节点,这会降低布局质量。

过去十年见证了现代分析技术的兴起,包括更高级的二次方法(Kim等,2010;2012b;Kim&Markov,2012;Brenner等,2008;Lin等,2013),最近,基于静电的方法如ePlace(Lu等人,2015)和RePlAce(Cheng等人,2019)。ePlace(Lu等人,2015)将网表布局建模为静电系统,提出了密度损失的新公式,其中网表的每个节点(宏或标准单元)类似于带正电的粒子,其面积对应于它的电费。在这种情况下,节点之间相互排斥的力与它们的电荷(面积)成正比,密度函数和梯度对应于系统的势能。已经提出了这种基于静电的方法的变体,以解决标准单元布局(Lu等,2015)和混合尺寸布局(Lu等,2015;Lu等,2016)的问题。RePlAce(Cheng等人,2019)是一种最新的混合尺寸布局技术,通过引入局部密度函数进一步优化ePlace的密度函数,该函数为每个个体量身定制惩罚因子虚拟箱的大小。第5节将最新的RePlAce算法的性能与我们的方法进行了比较。

最近的工作(Huang et al.,2019)建议训练模型以预测给定宏布局的违反设计规则检查(Design Rule Check)的次数。DRC是确保所放置和路由的网表符合流片输出要求的规则。为了生成具有更少DRC的宏布局(Huang等人,2019),使用此训练模型的预测作为模拟退火中的评估函数。尽管这项工作代表了一个有趣的方向,但它报告的网表结果不超过6个宏,远远少于任何现代模块,而且该方法在布局和路线步骤中未进行任何优化。优化后的布局和布线可能会发生巨大变化,并且实际DRC也将发生相应变化,从而使模型预测无效。另外,尽管遵守DRC标准是必要条件,但是宏布局的主要目的是针对线长,时序(例如最坏的负松弛(WNS)和总的负松弛(TNS)),功率和面积进行优化。,而此工作甚至都没有考虑这些指标。

为了解决这个经典问题,我们提出了一种新的方法类别:基于端到端学习的方法。这种方法与解析求解器(尤其是非线性求解器)最密切相关,因为所有这些方法都通过梯度更新来优化目标函数。但是,我们的方法与以往的方法不同之处在于它可以从过去的经验中学习,以在新芯片上生成更高质量的布局。与现有的从零开始优化每个新芯片的布局的方法不同,我们的工作利用从布局先前芯片获得的知识来随着时间的推移变得更好。此外,我们的方法能够直接优化目标指标,例如线长,密度和拥塞,而不必像其他方法一样定义那些函数的凸近似值(convex approximations)(Cheng等,2019; Lu等。,2015)。我们的公式不仅使新的成本函数易于获得变得容易,而且还使我们能够根据给定芯片块的需求(例如,时序关键或功率受限)的需要来权衡它们的相对重要性。

域适应(Domain adaptation)是培训策略的问题,该策略可以横跨多种经验学习并迁移所获得的知识,从而在新的未见实例上表现更好。在芯片布局的情况下,域适应包括在一组芯片网表中训练策略,并将该策略应用于新的未见的网表。最近,用于组合优化的域适应已成为一种趋势(Zhou等,2019; Paliwal等,2019; Addanki等,2019)。尽管先前工作的重点是使用从优化问题的先前示例中学到的领域知识来加快对新问题的策略培训,但我们提出了一种方法,该方法首次使得利用过去的经验来生成更高质量的结果成为可能。与从零训练策略相比,我们新颖的域适应不仅可以产生更好的结果,而且还可以将训练时间减少8倍。

三、方法

1.问题陈述

在本项目中,我们针对芯片布局优化问题,目标是将网表的节点(描述芯片的图形)映射到芯片画布(有界的2D空间)上,从而获得最终优化的功耗,性能和 面积(PPA)。在本节中,我们概述如何将问题表述为强化学习(RL)问题,然后详细描述奖励函数,动作和状态表达,策略架构以及策略更新.

2.我们的方法概述

我们采用深度强化学习方法来解决布局问题,其中一个RL代理(策略网络)顺序放置宏;一旦放置了所有宏,就使用力导向方法来生成标准单元的粗略放置,如图1所示。RL问题可以表述为马尔可夫决策过程(MDP),包括四个关键要素:
  • 状态:世界上可能的状态集(例如,在我们的情况下,是网表在芯片画布上的每个可能的部分布局)。

  • 动作:代理可以采取的一组动作(例如,给定要放置的当前宏,可用的动作是离散画布空间(网格单元)中所有位置的集合) 可以放置宏,而不会违反对密度或阻塞的任何严格限制)。

  • 状态转换:给定一个状态和一个动作,这是下一个状态的概率分布

  • 奖励:在某种状态下采取行动的奖励。(例如,在我们的案例中,除最后一个动作(奖励为代理线长和拥塞的负加权总和)之外,所有其他动作的奖励均为0,具体取决于第3.3节中所述的密度约束

在我们的设置中,在初始状态下,我们有一个空的芯片画布和一个未布局的网表。最终状态ST对应于完全放置的网表。在每一步中,放置一个宏。因此,T等于网表中宏的总数。在每个时间步骤t,代理开始处于状态(st),采取行动(at),到达新状态(st+i),并从环境中获得奖励(rt)(0表示t<T和t的负代理费用t=T)。

我们将st定义为表示时间t处状态的特征的串联,包括网表的图形嵌入(包括放置和未放置的节点),要放置的当前宏的节点嵌入,关于网表的元数据(部分 4),以及表示将当前节点放置到网格的每个单元上的可行性的掩码。

动作空间是第t个宏的所有有效位置,这是下文中描述的密度掩码的函数。在处执行的操作是RL策略网络选择的第t个宏的单元格位置。

st+i是下一个状态,它包括包含有关新放置的宏的信息的更新表示,更新的密度掩码以及要放置的下一个节点的嵌入。

在我们的公式中,除了最终的rT以外,每个时间步长rt均为0,这是文中所述的近似导线长度和拥塞的加权总和。

通过重复的情节(状态,动作和奖励的顺序),策略网络将学习采取可最大化累积奖励的动作。给定每个位置的累积奖励,我们使用近端策略优化(PPO)(Schulman et al。,2017)更新政策网络的参数

在本节中,我们定义奖励r,状态s,操作a,参数化为0的策略网络架构 πθ(a|s),最后定义用于训练这些参数的优化方法.

3.奖励

我们在这项工作中的目标是在限制路由拥塞和密度的前提下,最大程度地减少功耗,性能和面积。我们真正的回报是商业EDA工具的输出,包括线长,布线拥塞,密度,功率,时序和面积。但是,强化学习策略需要100,000个样本才能有效学习,因此至关重要的是要快速评估奖励功能,理想情况下可以在几毫秒内运行。为了更有效,这些近似的奖励功能还必须与真实奖励正相关。因此,成本的一个组成部分就是线长,因为它不仅评估更便宜,而且与功率和性能(时序)相关。我们分别针对线长和拥塞定义了近似成本函数。

为了将多个目标组合为一个奖励函数,我们采用代理线长和拥塞的加权总和,其中权重可用于探索两个指标之间的权衡。

尽管我们将拥塞视为软约束(即,较低的拥塞改善了奖励功能),但我们将密度视为硬约束,掩盖了密度超过目标密度的动作(网格单元以将节点放置到其上),如本节中进一步所述。

为了使每次迭代的运行时间保持较小,我们对奖励函数的计算应用了几种近似方法:
  • 我们使用hMETIS(Karypis&Kumar,1998),一种基于标准化最小切割目标的分割技术,将数百万个标准细胞分组为几千个簇。放置所有宏后,我们将使用力控制方法放置标准单元簇。这样做使我们能够实现近似但快速的标准单元布局,从而促进策略网络优化。

  • 我们将网格离散化为数千个网格单元,然后将宏和标准单元簇的中心放到网格单元的中心。

  • 在计算线长时,我们做一个简化的假设,即所有离开标准单元簇的线都起源于簇的中心。

  • 为了计算路由选择的拥塞成本,我们仅考虑最拥挤的前10%网格单元的平均拥塞。

(1)线长

根据文献(Shahookar和Mazumder,1991),我们采用半周线长(HPWL),这是最常用的线长近似值。HPWL定义为网表中所有节点的边界框的半周长。下式显示了给定网(边)i的HPWL:
这里的xbyb表示网络i端点的x和y坐标。然后,通过取所有半周边界框的归一化总和来计算总HPWL成本,如方程式2所示。随着节点数量的增加,Nnetust是网络的数量.

直观上,给定布局的HPWL大约是其Steiner树的长度(Gilbert&Pollak,1968),这是路由成本的下限.
线长还具有与其他重要指标(例如功率和时序)关联的优势。尽管我们没有直接针对这些其他指标进行优化,但我们在功耗和时序方面均保持了高性能(如表2所示。

(2)网格行和列的选择

给定芯片画布的尺寸,有很多选择可以将2D画布离散化为网格单元。该决定影响优化的难度和最终布局的质量。我们将最大行数和列数限制为128。我们将选择最佳行数和列数视为一个装箱问题,并根据它们所浪费的空间量对行列的不同组合进行排序。在第5节中描述的实验中,我们平均使用30行和列.

(3)宏顺序的选择

为了选择宏的放置顺序,我们按大小降序对宏进行排序,并使用拓扑排序打破平局。通过首先放置较大的宏,我们减少了以后的宏没有可行放置的可能性。拓扑排序可以帮助策略网络学习将连接的节点放置在彼此附近。另一种可能的方法是学习共同优化宏的顺序及其放置,从而选择放置哪个节点来放置活动空间的下一部分。但是,这种扩大的行动空间将极大地增加问题的复杂性,并且我们发现这种启发式方法在实践中有效.

(4)标准单元布局

为了放置标准单元簇,我们使用与经典的力导向方法相似的方法(Shahookar&Mazumder,1991)。我们将网表表示为一个弹簧系统,该弹簧根据权重x距离公式对每个节点施加力,从而使紧密连接的节点彼此吸引。我们还引入了重叠节点之间的排斥力以降低布局密度。施加所有力之后,我们沿力矢量的方向移动节点。为了减少振荡,我们为每次移动设置了最大距离.

(5)路由拥塞

我们还根据惯例采用了基于驱动程序位置和网络负载的简单确定性路由来计算代理拥塞(Kim等,2012a)。路由网络为其通过的每个网格单元占用一定数量的可用路由资源(由底层的半导体制造技术确定)。我们分别跟踪每个网格单元中的垂直和水平分配。为了平滑拥塞估计,我们在垂直和水平方向上都运行5x1卷积滤波器。路由完所有网络后,我们取最高10%的拥塞值的平均值,从MAPLE中的ABA10度量中汲取灵感(Kim等人,2012a)。公式4中的拥塞成本是此过程计算出的最高10%的平均拥塞.

(6)密度

我们将密度视为严格的约束条件,不允许策略网络将宏放置在会导致密度超过目标(最大密度)或导致不可行的宏重叠的位置。这种方法有两个好处:
  • 减少了策略网络生成的无效放置的数量;

  • 减少了优化问题的搜索空间,使其在计算上更易于处理.

可行的标准单元簇放置应满足以下条件:每个网格单元中放置的物品的密度不应超过给定的目标密度阈值(最大密度)。在我们的实验中,我们将该阈值设置为0.6。为了满足此约束,在每个RL步骤中,我们将计算当前密度掩码,即一个表示网格单元的m×n二进制矩阵,我们可以在该网格单元上放置当前节点的中心而不会违反密度阈值标准。在从策略网络输出中选择动作之前,我们首先获取掩码与策略网络输出的点积,然后在可行位置上取argmax。这种方法可防止策略网络生成具有重叠宏或密集标准单元格区域的布局.

我们还可以通过将受阻区域的密度功能设置为1来启用可感知阻塞的位置(例如时钟带).

(7)后处理

为了准备用于商业EDA工具评估的布局,我们执行一个贪心合法化步骤,以便在遵守最小间距限制的同时将宏捕捉到最近的合法位置。然后,我们修复宏布局,并使用EDA工具放置标准单元并评估布局.

4.动作表达

为了优化策略,我们将画布转换为m x n的网格。因此,对于任何给定状态,动作空间(或策略网络的输出)是当前宏在m x n网格上的布局概率分布。动作是该概率分布的argmax.

5.状态表达

我们的状态包含有关网表图(邻接矩阵),其节点特征(宽度,高度,类型等),边缘特征(连接数),要放置的当前节点(宏)以及网络元数据的信息。网表和底层技术(例如,路由分配,线路总数,宏和标准单元簇等)。在下一节中,我们讨论如何处理这些功能以有效学习的芯片布局问题.

四、域迁移:从经验中学习更好的芯片布局

我们的目标是开发RL代理,这些代理在通过获得更多芯片布局经验可以产生更高质量的结果。我们可以将布局目标函数正式定义如下:
在此,J(θ,G)是成本函数。代理由θ参数化。大小为K的网表图的数据集由G表示,数据集中的每个单独的网表都写为g。Rp,g是从应用于网络列表g的策略网络得出的布局p的情节奖励。
方程式4显示了我们用于策略网络优化的奖励,它是受密度约束的电线长度和拥塞的负加权平均。在我们的实验中,将拥塞权重设置为0.01,将最大密度阈值设置为0.6。

1.用有监督的方法来实现迁移学习

我们提出了一种新颖的神经体系结构,使我们能够训练用于芯片布局的域自适应策略。训练这样的策略网络是一项具有挑战性的任务,因为包含所有可能芯片的所有可能布局的状态空间是巨大的。此外,不同的网表和网格大小可以具有非常不同的属性,包括不同数量的节点,宏大小,图形拓扑以及画布宽度和高度。为了应对这一挑战,我们首先专注于学习状态空间的丰富表示形式。我们的直觉是,能够在芯片之间传输布局优化的策略网络体系结构也应该能够在推理时将与新的未见芯片相关联的状态编码为有意义的信号。因此,我们提出了一种训练神经网络架构的方法,该结构能够预测新网表上的奖励,其最终目标是使用这种架构作为我们策略网络的编码器层。要训练这种监督模型,我们需要一个大型的芯片布局及其相应奖励标签的数据集。因此,我们创建了一个10,000个芯片位置的数据集,其中输入是与给定位置相关的状态,而标签是该位置(线长和拥塞)的奖励。我们通过首先选择5个不同的加速器网表,然后为每个网表生成2,000个布局来构建此数据集。为了为每个网表创建不同的布局位置,我们在各种拥塞权重(从0到1)和随机种子下训练了一个香草策略(vanilla policy)网络,并在策略训练过程中收集了每个布局位置的快照。未经训练的策略网络以随机权重开始,并且生成的位置质量较低,但是随着策略网络的训练,生成的位置的质量提高了,这使我们能够收集具有变化质量的位置的多样化数据集.

为了训练可以准确预测线长和拥塞标签并泛化到未见的数据的监督模型,我们开发了一种新颖的图神经网络架构,该架构嵌入了有关网表的信息。图神经网络的作用是将有关大图内节点类型和连通性的信息提炼成可用于下游任务的低维向量表示。此类下游任务的一些示例是节点分类(Nazi等人,2019),设备放置(Zhou等人,2019),链接预测(Zhang&Chen,2018)和设计规则冲突(DRC) 预测(Zhiyao Xie Duke Univeristy,2018).

我们通过串联节点特征来创建每个节点的矢量表示。节点特征包括节点类型,宽度,高度以及x和y坐标。我们还将节点邻接信息作为输入传递给我们的算法。然后,我们重复执行以下更新:1)每个边缘通过将完全连接的网络应用于中间节点嵌入的聚合表示来更新其表示,以及2)每个节点通过获取相邻边缘嵌入的均值来更新其表示。节点和边缘更新如公式5所示。
节点嵌入用1<=i<=N表示,其中N是宏和标准单元簇的总数。连接节点和Vj的矢量化边缘表示为边缘(e)和节点(v)的嵌入都是随机初始化的,是32维的,fco是32x32,fcr是65x32前馈网络,并且权重为1x1对应于边缘。N(vi)显示化的邻居。算法的输出是节点和边缘嵌入.

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

这项有监督的任务使我们能够找到必要的功能和架构,以概括跨网表的奖励预测。为了将此架构整合到我们的策略网络中,我们删除了预测层,然后将其用作策略网络的编码器组件,如图2所示。

为了处理与不同的行和列选择相对应的不同网格大小,我们将网格大小设置为128x128,并对小于128行和列的网格大小遮盖未使用的L形部分。

为了在推理时布局一个新的测试网表,我们加载了策略网络的预先训练的权重,并将其应用于新的网表。我们将没有经过微调的经过预先训练的策略网络生成的布局位置称为零击布局。这样的布局可以在不到一秒钟的时间内生成,因为它只需要预先训练的策略网络的单个推理步骤即可。我们可以通过优化策略网络来进一步优化布局质量。这样做使我们可以灵活地使用预先训练的权重(已经学会了输入状态的丰富表达)或进一步微调这些权重以针对特定芯片网表的属性进行优化。

2.策略网络架构

图2描绘了策略网络(在方程式3中由n表示)和我们为芯片布局开发的价值网络架构的概述。这些网络的输入是网表图(图形邻接矩阵和节点特征),要布局的当前节点的id以及网表和半导体技术的元数据。如先前所述,网表图通过我们提出的图神经网络架构。该图神经网络生成(1)部分布局的图和(2)当前节点的嵌入。我们使用一个简单的前馈网络来嵌入(3)元数据。然后将这三个嵌入向量连接起来以形成状态嵌入,该状态嵌入被传递到前馈神经网络。然后将前馈网络的输出馈送到策略网络(由5个反卷积1和批标准层(Batch Normalization layers)组成),以生成动作上的概率分布,并传递到价值网络(由前馈网络组成)以进行预测输入状态的值。

3.略网络更新:训练参数θ

在方程式3中,目标是训练一个策略网络n,该策略网络n在策略网络的位置分布上最大化奖励(Rp,g)的期望值(E)。为了优化策略网络参数,我们使用具有限制目标的近端策略优化(PPO)(Schulman等人,2017),如下所示:

其中Et代表时间步长t的期望值,rt是新策略和旧策略的比率,At是时间步长t的估计优势.

五、结果

在本节中,我们评估我们的方法并回答以下问题:我们的方法是否支持域迁移和从经验中学习?使用预先训练的政策对结果质量有何影响?生成的布局的质量与最新的基线相比如何?我们还将检查生成的布局的外观,并提供一些有关我们的策略网络为何做出这些决策的解读.

1.迁移学习结果

图3将使用预训练策略生成的布局质量与通过从零训练策略网络生成的布局质量进行了比较。零击意味着我们将经过预训练的策略网络应用于新的网表,而不会进行微调,从而在不到一秒钟的时间内产生了布局。我们还将显示结果,其中我们将根据特定设计的细节对经过预训练的策略网络进行2到12个小时的微调。从头开始训练的策略网络需要花费更长的时间才能收敛,即使在24小时之后,结果也要比经过精调的策略网络在12小时之后达到的结果更差,这表明所学的权重和对许多不同设计的了解正在帮助我们实现在较短的时间内为新设计提供高质量的布局的目标.

图4显示了针对Ariane RISC-V CPU从零开始训练与从预训练策略网络进行训练的收敛图。经过预训练的策略网络在优化过程开始时以较低的放置成本开始。此外,经过预训练的策略网络可以收敛到更低的部署成本,并且比从零开始训练的策略网络快30个小时以上.

2.从更大的数据集中学习

图3.域适应结果。对于每个块,将显示零击结果以及训练2和6个小时后的微调结果。我们还包括从头开始训练的策略的结果。从表中可以看出,预先训练的策略网络始终优于从零开始训练的策略网络,这表明从离线训练数据中学习的有效性。

随着我们在更多芯片上进行训练,我们能够加快训练过程并更快地产生更高质量的结果。图4(左)显示了更大的培训对绩效的影响。训练数据集是从内部
图4.从零开始训练策略网络与微调针对一个Ariane 块的预训练策略网络收敛图.

训练数据由各种模块组成,包括内存子系统,计算单元和控制逻辑。当我们将训练集从2个块增加到5个块,最后增加到20个块时,策略网络会在零击(zero-shot)和经过微调相同小时数的情况下生成更好的布局。图5(右)显示了在对策略网络进行(预)培训时测试数据的布局成本。我们可以看到,对于较小的训练数据集,策略网络会快速过度拟合训练数据,而测试数据的性能会下降,而对于最大的数据集,策略网络可能会花费较长的时间,而预先训练的策略网络会花费较长的时间这个更大的数据集会在测试数据上产生更好的结果。该图表明,当我们将策略网络暴露于更多种类的不同区块时,虽然策略网络可能需要更长的时间进行预训练,但策略网络变得不太容易过度拟合,并且对新的未见的块更容易找到优化的布局.

3.可视化解读

图6显示了Ariane RISC-V CPU的布局结果。左侧显示了零击策略网络的展示位置,右侧显示了经过微调的策略网络的布局。零击布局是推理时在未见的芯片上生成的。零击策略网络将标准单元放在由宏包围的画布中心,这已经非常接近最佳安排。在微调之后,宏的布局变得更规则,并且中心的标准单元区域变得不太拥挤.

图7显示了可视化的布局:左侧是手动布局的结果,右侧是我们方法的结果。白色区域显示宏位置,绿色区域显示标准单元格位置。我们的方法在标准单元周围创建了圆环形状的宏布局,从而减少了总线长。
图5.我们在三个不同的训练数据集上对策略网络进行了预训练(小数据集是中等数据集的一个子集,而中等数据集是大数据集的一个子集)。然后,我们在相同的测试块上微调此预训练的策略网络,并报告不同训练持续时间的成本(如图左侧所示)。随着数据集大小的增加,生成的布局的质量和在测试块上收敛的时间都将提高。右图显示了在每个数据集上训练的策略的评估曲线(右图中的每个点显示了由训练中的策略生成的布局的成本)
图6.布局的可视化。左侧显示了经过预训练的策略的零击位置,右侧显示了经过微调的策略的布局。零击策略放置是在推理时在未见的芯片上生成的。经过预先训练的策略网络(无微调)将标准单元放在由宏包围的画布中心, 这已经非常接近最佳安排,并且符合物理设计专家的直觉。

4.与基线方法的比较

在本节中,我们将我们的方法与3种基线方法进行比较:模拟退火,RePl Ace和人类正常基线。对于我们的方法,我们在最大的数据集(20个TPU块)上使用了预训练的策略,然后在由块1到5表示的5个目标看不见的块上对其进行了微调。我们的数据集包括各种块,包括内存子系统, 计算单元和控制逻辑。由于机密性,我们无法透露这些块的详细信息,但是要给出规模的概念,每个块最多包含数百个宏和数百万个标准单元.

与模拟退火的比较:模拟退火(SA)是一种功能强大但速度缓慢的优化方法。但是,像RL一样,模拟退火能够优化任意不可微的成本函数。为了显示RL的相对样本效率,我们进行了实验,其中我们将其替换为基于模拟退火的优化器。在这些实验中,我们使用与以前相同的输入和成本函数,但是在每个情节中,模拟的退火优化器都会放置所有宏,然后执行FD步骤放置标准单元簇。根据SA更新规则,使用指数衰减退火进度表接受每个宏位置(Kirkpatrick等,1983)。SA花费18个小时才能收敛,而我们的方法花费不超过6个小时。

为了使比较公平,我们进行了多次SA实验,扫描了不同的超参数,包括最低和最高温度,种子和最大SA情节,以便SA和RL在仿真中花费相同的CPU小时数并搜索状态相似。表1中报告了以最低成本得到的实验结果。如表中所示,与我们的方法相比,即使花费额外的时间,SA仍难以生产出高质量的布局,并且生产的布局导致偏高的14.4%线长和24.1 %平均拥塞率.
图7.人类专家的布局在左侧,而我们的方法的结果在右侧。白色区域代表宏,绿色区域代表标准单元。由于设计是专有的,因此图片特意被模糊.
表1.评估深度强化学习与模拟退火(SA)相比样品效率的实验。我们用SA替换了RL策略网络,并为每个块运行了128个不同的SA实验,扫描了不同的超参数,包括最低和最高温度,种子和最大步长。报告运行成本最低的结果。结果显示每个块的代理线长和拥塞值。请注意,由于这些代理指标是相对的,因此比较仅对同一块的不同布局有效.

与RePlAce(Cheng等,2019)和手动基准的比较:表2将我们的结果与最新方法RePlAce(Cheng等,2019)和手动基准进行了比较。手动基准由生产芯片设计团队生成,并涉及布局优化的许多迭代,并在数周的时间内得到了商用EDA工具的反馈指导.

类似于RePlAce,我们有相同的优化目标,即优化芯片设计中的全局布局,但是我们使用不同的目标函数。因此,我们没有比较来自不同成本函数的结果,而是将商业EDA工具的输出视为基本事实。为了进行这种比较,我们修复了由我们的方法和RePlAce生成的宏布局,并允许商用EDA工具使用该工具的默认设置来进一步优化标准单元布局。然后,我们报告总线长,时序(最差(WNS)和总(TNS)负松弛),面积和功率指标。如表2所示,我们的方法在生成满足设计要求的展示位置方面胜过RePLAce。给定底层半导体技术所施加的约束,如果WNS明显高于100 ps或水平或垂直,则这些块的布局将无法在设计流程的后期阶段满足时序约束。拥堵超过1%,导致某些RePlAce布局(1、2、3块)无法使用。这些结果表明,我们的拥塞感知方法可有效地生成符合设计标准的高质量布局.

RePlAce在1至3.5小时内收敛,比我们的方法快,而我们的结果在3至6小时内达到。但是,我们方法的一些基本优点是:1)我们的方法可以轻松地针对各种不可微调的成本函数进行优化,而无需构建这些成本函数的封闭形式或可微分的等价形式。例如,虽然很容易将线长建模为凸函数,但对于布线拥塞或时序却并非如此。2)我们的方法有能力随着策略暴露于更多的芯片而随着时间的流逝而改进,并且3)我们的方法能够遵守各种设计约束,例如不同形状的阻塞。

表2还显示了人类专家芯片设计人员产生的结果。我们的方法和人类专家都一致地产生可行的布局,这意味着它们符合时序和拥挤设计标准。我们在WNS,面积,功率和线长方面也优于或匹配手动放置。此外,我们的端到端基于学习的方法花费了不到6个小时,而手动基准测试涉及一个缓慢的迭代优化过程,需要专家在回路中进行,并且可能需要花费数周的时间.

表2.将我们的方法与最新技术(RePlAce(Cheng等人,2019))和使用行业标准电子设计自动化(EDA)工具的手动专家放置位置进行比较。对于此表中的所有指标,越低越好。对于违反时间限制(WNS明显大于100 ps)或拥塞(水平或垂直拥塞大于1%)的布局,我们将其指标显示为灰色,以表明这些布局不可行。

5.讨论

进一步优化我们的方法的机会:还存在许多进一步改善我们方法质量的机会。例如,可以进一步优化标准单元划分,行和列的选择以及选择放置宏的顺序的过程。另外,我们还将受益于标准单元布局的更优化方法。当前,由于其运行时间快,我们使用力导向方法布局标准单元。但是,我们认为,用于Re-PlAce(Cheng等人,2019)和DREAMPlace(Lin等人,2019)的标准单元布局的更先进技术可以产生更多准确的标准单元布局用以指导策略网络培训。这很有用,因为如果策略网络在其宏布局如何影响标准单元格布局和最终指标方面具有更清晰的信号,它可以学习做出更优化的宏布局决策.

对更广泛类别问题的影响:这项工作只是域适应优化策略的一个示例,可以扩展到芯片设计过程的其他阶段,例如架构和逻辑设计,综合以及设计验证 ,目的是训练ML模型,使其在遇到更多问题实例时得到改善。基于学习的方法还可以促进在构成芯片设计过程的一系列任务中进一步进行设计空间探索和协同优化.

六、结论

在本项目中,我们针对芯片布局的复杂而有影响的问题, 我们提出了一种基于RL的方法,该方法支持迁移学习。,这意味着RL代理会在大量芯片网表上获得更多经验,从而在芯片布局方面变得更快,更好。我们证明了我们的方法优于最新的基准,并且可以产生媲美或优于使用现代现代加速器的人类专家产生的布局。我们的方法是端到端的,并会在6小时内生成芯片布局,而最强的基线需要人工干预,并且需要花费数周的时间.

鸣谢:
此项目是Google Research与Google芯片实施和基础架构(CI2)团队之间的合作。我们要感谢Cliff Young,Ed Chi,Chip Stratakos,Sudip Roy,Amir Yazdanbakhsh,Nathan Myung-Chul Kim,Sachin Agarwal,Bin Li,Martin Abadi,Amir Salek,Samy Bengio和David Patterson的帮助和支持。
半导体行业观察
半导体行业观察

最有深度的半导体新媒体,实时、专业、原创、深度,30万半导体精英关注!专注观察全球半导体最新资讯、技术前沿、发展趋势。

理论芯片深度强化学习论文谷歌
1
相关数据
深度强化学习技术

强化学习(Reinforcement Learning)是主体(agent)通过与周围环境的交互来进行学习。强化学习主体(RL agent)每采取一次动作(action)就会得到一个相应的数值奖励(numerical reward),这个奖励表示此次动作的好坏。通过与环境的交互,综合考虑过去的经验(exploitation)和未知的探索(exploration),强化学习主体通过试错的方式(trial and error)学会如何采取下一步的动作,而无需人类显性地告诉它该采取哪个动作。强化学习主体的目标是学习通过执行一系列的动作来最大化累积的奖励(accumulated reward)。 一般来说,真实世界中的强化学习问题包括巨大的状态空间(state spaces)和动作空间(action spaces),传统的强化学习方法会受限于维数灾难(curse of dimensionality)。借助于深度学习中的神经网络,强化学习主体可以直接从原始输入数据(如游戏图像)中提取和学习特征知识,然后根据提取出的特征信息再利用传统的强化学习算法(如TD Learning,SARSA,Q-Learnin)学习控制策略(如游戏策略),而无需人工提取或启发式学习特征。这种结合了深度学习的强化学习方法称为深度强化学习。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

人工智能技术

在学术研究领域,人工智能通常指能够感知周围环境并采取行动以实现最优的可能结果的智能体(intelligent agent)

基准技术

一种简单的模型或启发法,用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

超参数技术

在机器学习中,超参数是在学习过程开始之前设置其值的参数。 相反,其他参数的值是通过训练得出的。 不同的模型训练算法需要不同的超参数,一些简单的算法(如普通最小二乘回归)不需要。 给定这些超参数,训练算法从数据中学习参数。相同种类的机器学习模型可能需要不同的超参数来适应不同的数据模式,并且必须对其进行调整以便模型能够最优地解决机器学习问题。 在实际应用中一般需要对超参数进行优化,以找到一个超参数元组(tuple),由这些超参数元组形成一个最优化模型,该模型可以将在给定的独立数据上预定义的损失函数最小化。

表征学习技术

在机器学习领域,表征学习(或特征学习)是一种将原始数据转换成为能够被机器学习有效开发的一种技术的集合。在特征学习算法出现之前,机器学习研究人员需要利用手动特征工程(manual feature learning)等技术从原始数据的领域知识(domain knowledge)建立特征,然后再部署相关的机器学习算法。虽然手动特征工程对于应用机器学习很有效,但它同时也是很困难、很昂贵、很耗时、并依赖于强大专业知识。特征学习弥补了这一点,它使得机器不仅能学习到数据的特征,并能利用这些特征来完成一个具体的任务。

爬山算法技术

爬山算法是一种局部择优的方法,采用启发式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

策略网络技术

在强化学习中,策略网络指一组相对稳定的关系,这些关系具有非等级和相互依赖的性质,将各个行为者(actor)联系起来。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

迁移学习技术

迁移学习是一种机器学习方法,就是把为任务 A 开发的模型作为初始点,重新使用在为任务 B 开发模型的过程中。迁移学习是通过从已学习的相关任务中转移知识来改进学习的新任务,虽然大多数机器学习算法都是为了解决单个任务而设计的,但是促进迁移学习的算法的开发是机器学习社区持续关注的话题。 迁移学习对人类来说很常见,例如,我们可能会发现学习识别苹果可能有助于识别梨,或者学习弹奏电子琴可能有助于学习钢琴。

前馈神经网络技术

前馈神经网络(FNN)是人工智能领域中最早发明的简单人工神经网络类型。在它内部,参数从输入层经过隐含层向输出层单向传播。与递归神经网络不同,在它内部不会构成有向环。FNN由一个输入层、一个(浅层网络)或多个(深层网络,因此叫作深度学习)隐藏层,和一个输出层构成。每个层(除输出层以外)与下一层连接。这种连接是 FNN 架构的关键,具有两个主要特征:加权平均值和激活函数。

图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

马尔可夫决策过程技术

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型,为动态规划与强化学习的最优化问题提供了有效的数学工具,广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时,我们一般特指其在离散时间中的随机控制过程:即对于每个时间节点,当该过程处于某状态(s)时,决策者可采取在该状态下被允许的任意决策(a),此后下一步系统状态将随机产生,同时回馈给决策者相应的期望值,该状态转移具有马尔可夫性质。

摩尔定律技术

摩尔定律是由英特尔创始人之一戈登·摩尔提出来的。其内容为:积体电路上可容纳的电晶体数目,约每隔两年便会增加一倍;经常被引用的“18个月”,是由英特尔首席执行官大卫·豪斯所说:预计18个月会将芯片的性能提高一倍。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

优化器技术

优化器基类提供了计算梯度loss的方法,并可以将梯度应用于变量。优化器里包含了实现了经典的优化算法,如梯度下降和Adagrad。 优化器是提供了一个可以使用各种优化算法的接口,可以让用户直接调用一些经典的优化算法,如梯度下降法等等。优化器(optimizers)类的基类。这个类定义了在训练模型的时候添加一个操作的API。用户基本上不会直接使用这个类,但是你会用到他的子类比如GradientDescentOptimizer, AdagradOptimizer, MomentumOptimizer(tensorflow下的优化器包)等等这些算法。

多目标优化技术

多目标优化是多准则决策的一个领域,它是涉及多个目标函数同时优化的数学问题。多目标优化已经应用于许多科学领域,包括工程、经济和物流,其中需要在两个或多个相互冲突的目标之间进行权衡的情况下作出最优决策。分别涉及两个和三个目标的多目标优化问题的例子有:在购买汽车时降低成本,同时使舒适性最大化;在使车辆的燃料消耗和污染物排放最小化的同时将性能最大化。

节点分类技术

节点分类任务是算法必须通过查看其邻居的标签来确定样本的标记(表示为节点)的任务。

量化技术

深度学习中的量化是指,用低位宽数字的神经网络近似使用了浮点数的神经网络的过程。

合合信息机构
暂无评论
暂无评论~