1.本发明涉及电子设计自动化的技术领域，尤其涉及到基于深度强化学习的芯片全局自动布局方法。
背景技术：2.现如今，随着集成电路的快速发展，电子设计自动化(eda)技术所面临的问题愈加复杂,需要处理的电路规模和计算的数据量不断增大。eda技术的发展速度能否跟上设计和制造工艺的飞速进步成为了关键问题。在集成电路物理设计阶段,布局布线是一个重要且耗时的步骤。首先,布局过程中涉及大量的迭代和优化,所需时间会显著地影响集成电路设计周期。其次,在集成电路的物理设计中,各个步骤间存在着密切联系,布局的结果的会影响可布线性以及布线过程的运行时间、拥挤度和布通率等参数。近年来,除了以线长和时延为驱动外,以可布线性为驱动的布局算法也受到关注。尽管在过去的几十年中布局算法有了显著的进步,但是快速且高效的布局仍然是一个具有挑战性的问题。
3.全局自动布局是芯片设计中的一个长期挑战，需要对日益复杂的电路进行多目标优化。为了解决芯片中的布局问题，学者们提出了基于解析器求解的方法，包括了非线性优化器，还有现代分析技术兴起之后发展的更先进的二次方法，以及最近的基于静电学方法和替换的方法，这些方法基于梯度优化方案中更新单元的位置，并且通常可以通过使用分区在cpu上并行化来处理数百万个标准单元，以减少运行时间。谷歌也提出了第一个用于宏布局的端到端学习方法，该方法将芯片布局建模为一个顺序决策问题。日本幸村雄介在专利中使用了q学习的方法设计布局布线；在文献(郝睿,蔡懿慈,周强,王锐.drplace:基于深度学习的可布线性驱动布局算法[j].计算机辅助设计与图形学学报,2021,33(04):624-631)中也提出了基于深度学习的可布线性驱动布局算法。尽管先前的工作都在cpu上执行超大规模优化问题的繁重数值计算，但是布局质量和布局的速度均有优化提升的地方。
技术实现要素：[0004]
本发明的目的在于克服现有技术的不足，提供一种基于深度强化学习的芯片全局自动布局方法，旨在超大规模集成电路中运用深度强化学习实现芯片快速全局自动布局并得到近似最优的解决方案。
[0005]
为实现上述目的，本发明所提供的技术方案为：
[0006]
基于深度强化学习的芯片全局自动布局方法，包括以下步骤：
[0007]
s1、输入芯片布局信息；
[0008]
s2、对芯片布局信息进行预处理，其中包括设计规则；
[0009]
s3、进行芯片局部布局的强化学习，得到最优的芯片局部布局信息；
[0010]
s4、判断步骤s3得到的最优的芯片局部布局信息是否满足设计规则，若满足，则进入步骤s5，否则返回步骤s3再次进行芯片局部布局的强化学习；
[0011]
s5、结合最优的芯片局部布局信息进行芯片全局自动布局的深度强化学习，得到
最优的芯片全局自动布局信息；
[0012]
s6、依据步骤s5得到的最优的芯片全局自动布局信息进行填充布局，得到最优的芯片全局自动布局效果；
[0013]
s7、判断步骤s6得到的最优的芯片全局自动布局效果是否满足设计规则，若满足，则采用该最优的芯片全局自动布局信息进行芯片全局自动布局，否则返回步骤s5继续进行芯片全局自动布局的深度强化学习。
[0014]
进一步地，对布局信息进行预处理，包括：
[0015]
s2-1网格预处理：设置网格为正方形并建立直角坐标系，其横轴为x，纵轴为y，在网格中，边用e表示，边与边之间的布线容量用ce表示，记第i个格子g的中心点信息为gi＝{xi，yi，c
ei
}，设置网格数；
[0016]
s2-2、宏单元预处理：把每一个宏单元视为矩形，利用快速排序算法对宏单元进行大小排序，并以此排序的结果组成排序序列集合作为输入集：
[0017]
h＝{si，i＝1，...，n}
[0018]
其中，si＝(li，wi，pi)为元组，表示带有位置信息的宏单元的面积，li表示宏单元的长，wi表示宏单元的宽，pi表示宏单元的位置信息，即pi＝{xi，yi}，n表示宏单元的总数；
[0019]
s2-3、标准单元预处理：将标准单元分为两种单元簇：
[0020]
1)依附宏单元hi的标准单元为依附型标准单元簇，记作bi，则bi＝{b
i1
，，b
i2
，...，b
in
}；
[0021]
2)不依附宏单元的标准单元为散件型标准单元簇，记作b，则b＝{b1，b2，...，bn}；
[0022]
s2-4、设计规则。
[0023]
进一步地，强化学习局部布局，包括：
[0024]
s3-1、向布局区域输入宏单元序列h＝{si，i＝1，...，n}及其依附型标准单元簇bi＝{b
i1
，b
i2
，...，b
in
}，并以集合簇的形式随机散放；
[0025]
s3-2、针对每一个宏单元si及其随机放置的依附型标准单元簇bi利用静电系统局部布局模型初始布局，使依附型标准单元簇bi进行分散移动，使得宏单元si与依附型标准单元簇bi整体静电平衡，形成初始的局部布局信息序列状态s；
[0026]
s3-3、从静电系统局部布局模型初始布局后得到的初始布局信息状态s中提取特征信息，令该特征信息为φ(s)，输入到actor-critic强化学习网络中，经过网络训练，得到最优的布局策略，根据最优布局策略输出一个最优的初始局部布局，输出最优策略对应的actor网络参数θ和critic参数ω；
[0027]
s3-4、用矩形将该单元模块进行规范化得到宏单元模块，令其长为ln，宽为wn，面积为sn，输出的信息序列为：
[0028]hn
＝{s
n1
，s
n2
，..，s
nn
}
[0029]
其中，sn＝{ln，wn，pn}，ln为更新模块的长，wn为更新模块的宽，pn为该模块的位置信息。
[0030]
进一步地，所述步骤s3-3中，具体的设定和步骤如下：
[0031]
s3-3-1、马尔可夫决策：
[0032]
1)状态s：静电系统局部布局模型形成的初始的局部布局信息序列状态，包括宏单元信息si及其依附型标准单元簇bi的长和宽及其在网格中的位置信息；
[0033]
2)动作集合a：所有标准单元可能采取的动作的集合；
[0034]
3)衰减因子γ：设置γ为1，表示所有的后续状态和当前奖励一致；
[0035]
4)探索率∈：使用∈-贪婪法进行价值迭代，即设置一个较小的∈值，使用1-∈的概率贪婪地选择目前认为是最大行为价值的行为，而用∈的概率随机的从所有m个可选行为中选择行为；用公式表示为：
[0036][0037]
其中，a表示动作，s表示为状态；
[0038]
s3-3-2、约束设定；
[0039]
s3-3-3、损失函数设定；
[0040]
s3-3-4、更新网络参数，得到actor网络参数θ、critic网络参数ω以及策略梯度估计
[0041]
进一步地，所述约束设定包括：
[0042]
1)线长约束：
[0043]
采用半周长线长，其最接近斯坦纳树，布线的最低成本，其计算公式为：
[0044]
hpwl(i)＝(max
b∈i
{xb}-min
b∈i
{xb})+(max
b∈i
{yb}-min
b∈i
{yb})
[0045]
其中xb和yb表示网格i的x和y坐标，对hpwl(i)进行求和，其目的是为了提升线长模型的收敛速度以及对指标评判的精度，用归一化因子q将宏单元和标准单元之间的总线长之和进行归一化，其归一化后的总线长公式如下所示：
[0046][0047]
目标之一是要使得hpwl越小越好，netlist表示线网；
[0048]
2)拥塞约束：
[0049]
采用基于最大溢出方式作为拥塞度量来评价布局是否可布通性；最大溢出方式表示为：of(e)＝max(ωe+b
e-ce，0)；为了使得网格边界的溢出容易被相邻区域吸收，保证设计的可布线性，则使用如下拥塞评价公式：
[0050]
congestion(e)＝100
×
(ωe+be)/ce[0051]
其中ce为边e的最大容量，be为边e上的布线拥塞，ωe为边e上的布线占用，拥塞小于50％视为可布通，目标要使得拥塞程度越小越好；
[0052]
3)密度约束：对于密度约束，设计空间利用率函数应用在局部布局中，具体设计如下：
[0053]
根据排序好的宏单元及限制规则以及空间利用率函数f对宏单元s1和宏单元s2进行组合，计算组合后的空间利用率f，当空间利用率达到预设的要求，即将宏单元进行合并；其中设置的规则为：
[0054]
待合并宏模块单元s1的信息为：长l1，宽w1，位置为p1，面积s1＝l1×
w1；
[0055]
待合并宏模块单元s2的信息为：长l2，宽w2，位置为p2，面积s2＝l2×
w2；
[0056]
组合成新的宏模块单元sn：长为ln，宽为wn，位置为pn，面积sn＝ln×
wn；
[0057]
其中ln和wn满足下面的规则：
[0058]
max(ln，wn)≤min(l，w)
[0059]
为了使得策略网络不将宏单元放置在会导致密度超过目标密度最大值或导致宏重叠的位置，则宏单元的布局满足如下的面积约束：
[0060][0061]
空间利用率函数为：
[0062][0063]
其中，l为长度，w为宽度，目标要使得空间利用率f越大越好。
[0064]
进一步地，所述损失函数设定包括：
[0065]
1)奖励函数设定：把总线长、拥塞程度、浪费率进行加权求和合成一个单目标的奖励函数，其中加权因子λ1和λ2主要用于权衡三个指标的影响，则用于策略网络优化的奖励函数如下：
[0066]
r＝-wirelength-λ1congestion+λ2f
[0067]
s.t.mins≤sn≤maxs
[0068]
其中，wirelength表示总线长，congestion表示总拥塞程度，f表示空间利用率，λ1和λ2分别是拥塞程度和空间利用率所占的权重，0≤λ1≤1，0≤λ2≤1，λ1+λ2＝1且λ1＞λ2，表示的是拥塞的占比权重比损失率的权重高，即首要保证布线的可布通性，再考虑面积的利用率；
[0069]
2)损失函数设定：
[0070]
设置优化的函数目标；设定优化目标为每一时间步的平均价值，即
[0071][0072]
对该式子的θ求导后的梯度如下：
[0073][0074]
为要进行优化的策略梯度估计；为分值函数，指出参数更新的方向，其使用的是softemax策略函数，以及使用描述状态和行为的特征φ(s，a)与参数θ的线性组合来权衡一个行为发生的几率，即：
[0075][0076]
通过求导得分值函数为：
[0077][0078]
进一步地，所述步骤s3-3-4包括：
[0079]
输入迭代次数t，状态维度n，动作集合a，步长a，衰减因子γ，探索率∈，critic网络结构和actor网络结构；
[0080]
更新过程包括：
[0081]
a1、随机初始化所有的状态和动作对应的价值q，i＝1；
[0082]
a2、初始化s为当前状态序列的第一个状态，得到特征向量φ(s)；
[0083]
a3、在actor网络中使用φ(s)作为输入，输出动作集合a，基于动作集合a得到新的状态s
′
，反馈r；
[0084]
a4、在critic网络中分别使用φ(s)，φ(s
′
)作为输入，得到q值输出v(s)，v(s
′
)；
[0085]
a5、计算td误差δ＝r+γv(s
′
)-v(s)；
[0086]
a6、v与q转换：
[0087]
a7、计算策略梯度估计：
[0088]
a8、使用均方差损失函数∑(r+γv(s
′
)-v(s，ω))2作为critic网络参数ω的参数更新；
[0089]
a9、更新actor网络参数θ：
[0090]
a10、判断i是否小于迭代次数t，若是，则i＝i+1，并返回步骤a2，否则输出最新的critic网络参数ω、actor网络参数θ以及策略梯度估计
[0091]
进一步地，所述步骤s5包括：
[0092]
s5-1、设计两层网络结构，分别为公共网络和局部网络；公共网络包括actor网络和critic网络两部分的功能；
[0093]
s5-2、计算各局部布局的梯度估计并累计求和，并将得到的各个局部布局最优的critic网络参数ω、actor网络参数θ输入到公共网络中；
[0094]
s5-3、使用得到的累积梯度估计更新公共网络，更新过程中，若收敛，则输出对应的最优策略，否则返回步骤s5-2；
[0095]
s5-4、通过最优策略对更新的宏模块hn进行布局，最终完成全局自动布局，更新的模块信息序列为h
nn
，并输出全局自动布局信息h
nn
。
[0096]
进一步地，所述步骤s6包括：
[0097]
s6-1、将全局自动布局信息h
nn
输入到力导向法解析器中；
[0098]
s6
‑‑
2、利用力导向的方法把散件型标准单元簇b＝{b1，b2，...，bn}进行填充，通过引力和斥力不断作用，使得散件型标准单元bi在不断移动之后趋于平衡，直至不再发生相对位移，能量不断消耗，最终趋于零；
[0099]
s6-3、输出最优的芯片全局自动布局效果。
[0100]
与现有技术相比，本方案原理及优点如下：
[0101]
本方案可对超大规模集成电路芯片快速布局，能够保证布局结果收敛以实现快速布局，并使得布局布线的线长、拥塞、面积达到近似最优。另外，本方案还提出一种空间利用率的方法，并将该方法应用在局部布局和全局自动布局中，从而使得局部布局和全局自动布局的面积达到最小，另外，应用了异步训练网络结构，通过该网络结构学习训练，可使局部布局和全局自动布局相关性更紧密，且布局结果更容易收敛，能实现芯片全局自动布局的可靠性。
附图说明
[0102]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现
有技术描述中所需要使用的服务作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0103]
图1为本发明基于深度强化学习的芯片全局自动布局方法的原理流程图；
[0104]
图2为静电系统局部布局模型初始布局示意图(u为局部随机散放的宏及其依附单元；v为局部布局得到的初始布局信息)；
[0105]
图3为空间利用率示意图；
[0106]
图4为actor-critic神经网络局部布局图；
[0107]
图5为分层强化学习全局自动布局结构示意图；
[0108]
图6为全局自动布局填充示意图。
具体实施方式
[0109]
下面结合具体实施例对本发明作进一步说明：
[0110]
如图1所示，本实施例所述的基于深度强化学习的芯片全局自动布局方法，包括以下步骤：
[0111]
s1、输入芯片布局信息；
[0112]
s2、对芯片布局信息进行预处理，包括：
[0113]
s2-1网格预处理：设置网格为正方形并建立直角坐标系，其横轴为x，纵轴为y，在网格中，边用e表示，边与边之间的布线容量用ce表示，记第i个格子g的中心点信息为gi＝{xi，yi，c
ei
}，设置网格数为2n×2n
，n为正整数；
[0114]
s2-2、宏单元预处理：把每一个宏单元视为矩形，利用快速排序算法对宏单元进行大小排序，并以此排序的结果组成排序序列集合作为输入集：
[0115]
h＝{si，i＝1，...，n}
[0116]
其中，si＝(li，wi，pi)为元组，表示带有位置信息的宏单元的面积，li表示宏单元的长，wi表示宏单元的宽，pi表示宏单元的位置信息，即pi＝{xi，yi}，n表示宏单元的总数；
[0117]
s2-3、标准单元预处理：将标准单元分为两种单元簇：
[0118]
1)依附宏单元hi的标准单元为依附型标准单元簇，记作bi，则bi＝{b
i1
，b
i2
，...，b
in
}；
[0119]
2)不依附宏单元的标准单元为散件型标准单元簇，记作b，则b＝{b1，b2，...，bn}；
[0120]
s2-4、设计规则：
[0121]
1)遵照“先大后小，先难后易”的布局原则，即宏单元电路及核心单元应当优先布局；
[0122]
2)布局应尽量满足以下要求：总的连线尽可能短，关键信号线最短；
[0123]
3)密度优先原则：从连接关系最密集最复杂的区域着手布线；
[0124]
4)按照均匀分布、重心平衡、版面美观的标准优化布局。
[0125]
s3、进行芯片局部布局的强化学习，得到最优的芯片局部布局信息；
[0126]
本步骤中，强化学习局部布局，包括：
[0127]
s3-1、向布局区域输入宏单元序列h＝{si，i＝1，...，n}及其依附型标准单元簇bi＝{b
i1
，b
i2
，...，b
in
}，并以集合簇的形式随机散放；
[0128]
s3-2、针对每一个宏单元si及其随机放置的依附型标准单元簇bi利用静电系统局部布局模型初始布局，使依附型标准单元簇bi进行分散移动，使得宏单元si与依附型标准单元簇bi整体静电平衡，形成初始的局部布局信息序列状态s，如图2所示；
[0129]
s3-3、从静电系统局部布局模型初始布局后得到的初始布局信息状态s中提取特征信息，令该特征信息为φ(s)，输入到actor-critic强化学习网络中，经过网络训练，得到最优的布局策略，根据最优布局策略输出一个最优的初始局部布局，输出最优策略对应的actor网络参数θ和critic参数ω；
[0130]
本步骤的具体的设定和步骤如下：
[0131]
s3-3-1、马尔可夫决策：
[0132]
1)状态s：静电系统局部布局模型形成的初始的局部布局信息序列状态，包括宏单元信息si及其依附型标准单元簇bi的长和宽及其在网格中的位置信息；
[0133]
2)动作集合a：所有标准单元可能采取的动作的集合；
[0134]
3)衰减因子γ：设置γ为1，表示所有的后续状态和当前奖励一致；
[0135]
4)探索率∈：使用∈-贪婪法进行价值迭代，即设置一个较小的∈值，使用1-∈的概率贪婪地选择目前认为是最大行为价值的行为，而用∈的概率随机的从所有m个可选行为中选择行为；用公式表示为：
[0136][0137]
其中，a表示动作，s表示为状态；
[0138]
s3-3-2、约束设定：
[0139]
1)线长约束：
[0140]
采用半周长线长，其最接近斯坦纳树，布线的最低成本，其计算公式为：
[0141]
hpwl(i)＝(max
b∈i
{xb}-min
b∈i
{xb})+(max
b∈i
{yb}-min
b∈i
{yb})
[0142]
其中xb和yb表示网格i的x和y坐标，对hpwl(i)进行求和，其目的是为了提升线长模型的收敛速度以及对指标评判的精度，用归一化因子q将宏单元和标准单元之间的总线长之和进行归一化，其归一化后的总线长公式如下所示：
[0143][0144]
目标之一是要使得hpwl越小越好，netlist表示线网；
[0145]
2)拥塞约束：
[0146]
采用基于最大溢出方式作为拥塞度量来评价布局是否可布通性；最大溢出方式表示为：of(e)＝max(ωe+b
e-ce，0)；为了使得网格边界的溢出容易被相邻区域吸收，保证设计的可布线性，则使用如下拥塞评价公式：
[0147]
congestion(e)＝100
×
(ωe+be)/ce[0148]
其中ce为边e的最大容量，be为边e上的布线拥塞，ωe为边e上的布线占用，拥基小于50％视为可布通，目标要使得拥基程度越小越好；
[0149]
3)密度约束：对于密度约束，本实施例设计空间利用率函数应用在局部布局与全局自动布局中，用两片宏单元拼接设计空间利用函数，如图3所示，具体设计如下：
[0150]
根据排序好的宏单元及限制规则以及空间利用率函数f对宏单元s1和宏单元s2进
行组合，计算组合后的空间利用率f，当空间利用率达到预设的要求，即将宏单元进行合并；其中设置的规则为：
[0151]
待合并宏模块单元s1的信息为：长l1，宽w1，位置为p1，面积s1＝l1×
w1；
[0152]
待合并宏模块单元s2的信息为：长l2，宽w2，位置为p2，面积s2＝l2×
w2；
[0153]
组合成新的宏模块单元sn：长为ln，宽为wn，位置为pn，面积sn＝ln×
wn；
[0154]
其中ln和wn满足下面的规则：
[0155]
max(ln，wn)≤min(l，w)
[0156]
为了使得策略网络不将宏单元放置在会导致密度超过目标密度最大值或导致宏重叠的位置，则宏单元的布局满足如下的面积约束：
[0157][0158]
空间利用率函数为：
[0159][0160]
其中，l为长度，w为宽度，目标要使得空间利用率f越大越好。
[0161]
s3-3-3、损失函数设定：
[0162]
1)奖励函数设定：把总线长、拥塞程度、浪费率进行加权求和合成一个单目标的奖励函数，其中加权因子λ1和λ2主要用于权衡三个指标的影响，则用于策略网络优化的奖励函数如下：
[0163]
r＝-wirelength-λ1congestion+λ2f
[0164]
s.t.mins≤sn≤maxs
[0165]
其中，wirelength表示总线长，congestion表示总拥塞程度，f表示空间利用率，λ1和λ2分别是拥塞程度和空间利用率所占的权重，0≤λ1≤1，0≤λ2≤1，λ1+λ2＝1且λ1＞λ2，表示的是拥塞的占比权重比损失率的权重高，即首要保证布线的可布通性，再考虑面积的利用率；
[0166]
2)损失函数设定：
[0167]
设置优化的函数目标；设定优化目标为每一时间步的平均价值，即
[0168][0169]
对该式子的θ求导后的梯度如下：
[0170][0171]
为要进行优化的策略梯度估计；为分值函数，指出参数更新的方向，其使用的是softemax策略函数，以及使用描述状态和行为的特征φ(s，a)与参数θ的线性组合来权衡一个行为发生的几率，即：
[0172][0173]
通过求导得分值函数为：
[0174][0175]
s3-3-4、更新网络参数，得到actor网络参数θ、critic网络参数ω以及策略梯度估计
[0176]
具体使用2个相同神经网络，如图4所示。其中critic使用神经网络输出最优价值v
t
且计算td误差δ，把v
t
和td误差δ输出给actor网络，actor利用v
t
这个最优价值迭代更新策略函数的参数θ，进而选择动作a，并得到反馈r和新的状态s
t+1
；critic使用反馈奖励r和新的状态s
t+1
更新神经网络中的参数ω，然后critic使用新的网络参数来帮助actor计算状态的最优价值v
t
。通过以上的循环持续更新actor网络参数θ、critic网络参数ω，直到策略梯度估计收敛，然后输出最终的actor网络参数θ、critic网络参数ω以及策略梯度估计
[0177]
具体过程如下：
[0178]
输入迭代次数t，状态维度n，动作集合a，步长α，衰减因子γ，探索率∈，critic网络结构和actor网络结构；
[0179]
更新过程包括：
[0180]
a1、随机初始化所有的状态和动作对应的价值q，i＝1；
[0181]
a2、初始化s为当前状态序列的第一个状态，得到特征向量φ(s)；
[0182]
a3、在actor网络中使用φ(s)作为输入，输出动作集合a，基于动作集合a得到新的状态s
′
，反馈r；
[0183]
a4、在critic网络中分别使用φ(s)，φ(s
′
)作为输入，得到q值输出v(s)，v(s
′
)；
[0184]
a5、计算td误差δ＝r+γv(s
′
)-v(s)；
[0185]
a6、v与q转换：
[0186]
a7、计算策略梯度估计：
[0187]
a8、使用均方差损失函数∑(r+γv(s
′
)-v(s，ω))2作为critic网络参数ω的参数更新；
[0188]
a9、更新actor网络参数θ：
[0189]
a10、判断i是否小于迭代次数t，若是，则i＝i+1，并返回步骤a2，否则输出最新的critic网络参数ω、actor网络参数θ以及策略梯度估计
[0190]
s3-4、用矩形将该单元模块进行规范化得到宏单元模块，令其长为ln，宽为wn，面积为sn，输出的信息序列为：
[0191]hn
＝{s
n1
，s
n2
，..，s
nn
}
[0192]
其中，sn＝{ln，wn，pn}，ln为更新模块的长，wn为更新模块的宽，pn为该模块的位置信息。
[0193]
s4、判断步骤s3得到的最优的芯片局部布局信息是否满足设计规则，若满足，则进入步骤s5，否则返回步骤s3再次进行芯片局部布局的强化学习；
[0194]
s5、结合最优的芯片局部布局信息进行芯片全局自动布局的深度强化学习，得到最优的芯片全局自动布局信息；具体包括：
[0195]
s5-1、设计两层网络结构，分别为公共网络和局部网络。其中局部网络有i个工作线程，其单一线程的网络结构具体设计见步骤s3；公共网络包括actor网络和critic网络两部分的功能，整体的神经网络模型见图5；
[0196]
s5-2、计算各局部布局的梯度估计并累计求和，并将得到的各个局部布局最优的critic网络参数ω、actor网络参数θ输入到公共网络中；
[0197]
s5-3、使用得到的累积梯度估计更新公共网络，更新过程中，若收敛，则输出对应的最优策略，否则返回步骤s5-2；
[0198]
s5-4、通过最优策略对更新的宏模块hn进行布局，最终完成全局自动布局，更新的模块信息序列为h
nn
，并输出全局自动布局信息h
nn
。
[0199]
s6、依据步骤s5得到的最优的芯片全局自动布局信息进行填充布局，得到最优的芯片全局自动布局效果；具体包括：
[0200]
s6
‑‑
1、将全局自动布局信息h
nn
输入到力导向法解析器中，h
nn
包括了宏单元模块的位置，线长和拥塞等信息；
[0201]
s6
‑‑
2、利用力导向的方法把散件型标准单元簇b＝{b1，b2，...，bn}进行填充，通过引力和斥力不断作用，使得散件型标准单元bi在不断移动之后趋于平衡，直至不再发生相对位移，能量不断消耗，最终趋于零；
[0202]
s6-3、输出最优的芯片全局自动布局效果，效果如图6所示；
[0203]
s7、判断步骤s6得到的最优的芯片全局自动布局效果是否满足设计规则，若满足，则采用该最优的芯片全局自动布局信息进行芯片全局自动布局，否则返回步骤s5继续进行芯片全局自动布局的深度强化学习。
[0204]
以上所述之实施例子只为本发明之较佳实施例，并非以此限制本发明的实施范围，故凡依本发明之形状、原理所作的变化，均应涵盖在本发明的保护范围内。
技术特征：1.基于深度强化学习的芯片全局自动布局方法，其特征在于，包括以下步骤：s1、输入芯片布局信息；s2、对芯片布局信息进行预处理，其中包括设计规则；s3、进行芯片局部布局的强化学习，得到最优的芯片局部布局信息；s4、判断步骤s3得到的最优的芯片局部布局信息是否满足设计规则，若满足，则进入步骤s5，否则返回步骤s3再次进行芯片局部布局的强化学习；s5、结合最优的芯片局部布局信息进行芯片全局自动布局的深度强化学习，得到最优的芯片全局自动布局信息；s6、依据步骤s5得到的最优的芯片全局自动布局信息进行填充布局，得到最优的芯片全局自动布局效果；s7、判断步骤s6得到的最优的芯片全局自动布局效果是否满足设计规则，若满足，则采用该最优的芯片全局自动布局信息进行芯片全局自动布局，否则返回步骤s5继续进行芯片全局自动布局的深度强化学习。2.根据权利要求1所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，对布局信息进行预处理，包括：s2-1网格预处理：设置网格为正方形并建立直角坐标系，其横轴为x，纵轴为y，在网格中，边用e表示，边与边之间的布线容量用ce表示，记第i个格子g的中心点信息为g
i
＝{x
i
，y
i
，c
ei
}，设置网格数；s2-2、宏单元预处理：把每一个宏单元视为矩形，利用快速排序算法对宏单元进行大小排序，并以此排序的结果组成排序序列集合作为输入集：h＝{s
i
，i＝1，...，n}其中，s
i
＝(l
i
，w
i
，p
i
)为元组，表示带有位置信息的宏单元的面积，l
i
表示宏单元的长，w
i
表示宏单元的宽，p
i
表示宏单元的位置信息，即p
i
＝{x
i
，y
i
}，n表示宏单元的总数；s2-3、标准单元预处理：将标准单元分为两种单元簇：1)依附宏单元h
i
的标准单元为依附型标准单元簇，记作b
i
，则b
i
＝{b
i1
，b
i2
，
…
，b
in
}；2)不依附宏单元的标准单元为散件型标准单元簇，记作b，则b＝{b1，b2，...，b
n
}：s2-4、设计规则。3.根据权利要求2所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，强化学习局部布局，包括：s3-1、向布局区域输入宏单元序列h＝{s
i
，i＝1，...，n}及其依附型标准单元簇b
i
＝{b
i1
，b
i2
，
…
，b
in
}，并以集合簇的形式随机散放；s3-2、针对每一个宏单元s
i
及其随机放置的依附型标准单元簇b
i
利用静电系统局部布局模型初始布局，使依附型标准单元簇b
i
进行分散移动，使得宏单元s
i
与依附型标准单元簇b
i
整体静电平衡，形成初始的局部布局信息序列状态s；s3-3、从静电系统局部布局模型初始布局后得到的初始布局信息状态s中提取特征信息，令该特征信息为φ(s)，输入到actor-critic强化学习网络中，经过网络训练，得到最优的布局策略，根据最优布局策略输出一个最优的初始局部布局，输出最优策略对应的actor网络参数θ和critic参数ω；s3-4、用矩形将该单元模块进行规范化得到宏单元模块，令其长为l
n
，宽为w
n
，面积为
s
n
，输出的信息序列为：h
n
＝{s
n1
，s
n2
，..，s
nn
}其中，s
n
＝{l
n
，w
n
，p
n
}，l
n
为更新模块的长，w
n
为更新模块的宽，p
n
为该模块的位置信息。4.根据权利要求3所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述步骤s3-3中，具体的设定和步骤如下：s3-3-1、马尔可夫决策：1)状态s：静电系统局部布局模型形成的初始的局部布局信息序列状态，包括宏单元信息s
i
及其依附型标准单元簇b
i
的长和宽及其在网格中的位置信息；2)动作集合a：所有标准单元可能采取的动作的集合；3)衰减因子γ：设置γ为1，表示所有的后续状态和当前奖励一致；4)探索率∈：使用∈-贪婪法进行价值迭代，即设置一个较小的∈值，使用1-∈的概率贪婪地选择目前认为是最大行为价值的行为，而用∈的概率随机的从所有m个可选行为中选择行为；用公式表示为：其中，a表示动作，s表示为状态；s3-3-2、约束设定；s3-3-3、损失函数设定；s3-3-4、更新网络参数，得到actor网络参数θ、critic网络参数ω以及策略梯度估计5.根据权利要求4所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述约束设定包括：1)线长约束：采用半周长线长，其最接近斯坦纳树，布线的最低成本，其计算公式为：hpwl(i)＝(max
b∈i
{x
b
}-min
b∈i
{x
b
})+(max
b∈i
{y
b
}-min
b∈i
{y
b
})其中x
b
和y
b
表示网格i的x和y坐标，对hpwl(i)进行求和，其目的是为了提升线长模型的收敛速度以及对指标评判的精度，用归一化因子q将宏单元和标准单元之间的总线长之和进行归一化，其归一化后的总线长公式如下所示：目标之一是要使得hpwl越小越好，netlist表示线网；2)拥塞约束：采用基于最大溢出方式作为拥塞度量来评价布局是否可布通性；最大溢出方式表示为：of(e)＝max(ω
e
+b
e-c
e
，0)；为了使得网格边界的溢出容易被相邻区域吸收，保证设计的可布线性，则使用如下拥塞评价公式：congestion(e)＝100
×
(ω
e
+b
e
)/c
e
其中c
e
为边e的最大容量，b
e
为边e上的布线拥塞，ω
e
为边e上的布线占用，拥塞小于50％视为可布通，目标要使得拥塞程度越小越好；3)密度约束：对于密度约束，设计空间利用率函数应用在局部布局中，具体设计如下：
根据排序好的宏单元及限制规则以及空间利用率函数f对宏单元s1和宏单元s2进行组合，计算组合后的空间利用率f，当空间利用率达到预设的要求，即将宏单元进行合并；其中设置的规则为：待合并宏模块单元s1的信息为：长l1，宽w1，位置为p1，面积s1＝l1×
w1；待合并宏模块单元s2的信息为：长l2，宽w2，位置为p2，面积s2＝l2×
w2；组合成新的宏模块单元s
n
：长为l
n
，宽为w
n
，位置为p
n
，面积s
n
＝l
n
×
w
n
；其中l
n
和w
n
满足下面的规则：max(l
n
，w
n
)≤min(l，w)为了使得策略网络不将宏单元放置在会导致密度超过目标密度最大值或导致宏重叠的位置，则宏单元的布局满足如下的面积约束：空间利用率函数为：其中，l为长度，w为宽度，目标要使得空间利用率f越大越好。6.根据权利要求5所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述损失函数设定包括：1)奖励函数r设定：把总线长、拥塞程度、浪费率进行加权求和合成一个单目标的奖励函数，其中加权因子λ1和λ2主要用于权衡三个指标的影响，则用于策略网络优化的奖励函数如下r＝-wirelength-λ1congestion+λ2fs.t.mins≤s
n
≤maxs其中，wirelength表示总线长，congestion表示总拥塞程度，f表示空间利用率，λ1和λ2分别是拥塞程度和空间利用率所占的权重，0≤λ1≤1，0≤λ2≤1，λ1+λ2＝1且λ1＞λ2，表示的是拥塞的占比权重比损失率的权重高，即首要保证布线的可布通性，再考虑面积的利用率；2)损失函数设定：设置优化的函数目标；设定优化目标为每一时间步的平均价值，即对该式子的θ求导后的梯度如下：对该式子的θ求导后的梯度如下：为要进行优化的策略梯度估计；为分值函数，指出参数更新的方向，其使用的是softemax策略函数，以及使用描述状态和行为的特征φ(s，a)与参数θ的线性组合来权衡一个行为发生的几率，即：
通过求导得分值函数为：7.根据权利要求6所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述步骤s3-3-4包括：输入迭代次数t，状态维度n，动作集合a，步长α，衰减因子γ，探索率∈，critic网络结构和actor网络结构；更新过程包括：a1、随机初始化所有的状态和动作对应的价值q，i＝1；a2、初始化s为当前状态序列的第一个状态，得到特征向量φ(s)；a3、在actor网络中使用φ(s)作为输入，输出动作集合a，基于动作集合a得到新的状态s
′
，反馈r；a4、在critic网络中分别使用φ(s)，φ(s
′
)作为输入，得到q值输出v(s)，v(s
′
)；a5、计算td误差δ＝r+γv(s
′
)-v(s)；a6、v与q转换：a7、计算策略梯度估计：a8、使用均方差损失函数∑(r+γv(s
′
)-v(s，ω))2作为critic网络参数ω的参数更新；a9、更新actor网络参数θ：a10、判断i是否小于迭代次数t，若是，则i＝i+1，并返回步骤a2，否则输出最新的critic网络参数ω、actor网络参数θ以及策略梯度估计8.根据权利要求7所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述步骤s5包括：s5-1、设计两层网络结构，分别为公共网络和局部网络；公共网络包括actor网络和critic网络两部分的功能；s5-2、计算各局部布局的梯度估计并累计求和，并将得到的各个局部布局最优的critic网络参数ω、actor网络参数θ输入到公共网络中；s5-3、使用得到的累积梯度估计更新公共网络，更新过程中，若收敛，则输出对应的最优策略，否则返回步骤s5-2；s5-4、通过最优策略对更新的宏模块h
n
进行布局，最终完成全局自动布局，更新的模块信息序列为h
nn
，并输出全局自动布局信息h
nn
。9.根据权利要求8所述的基于深度强化学习的芯片全局自动布局方法，其特征在于，所述步骤s6包括：s6-1、将全局自动布局信息h
nn
输入到力导向法解析器中；s6-2、利用力导向的方法把散件型标准单元簇b＝{b1，b2，...，b
n
}进行填充，通过引力和斥力不断作用，使得散件型标准单元b
i
在不断移动之后趋于平衡，直至不再发生相对位移，能量不断消耗，最终趋于零；
s6
‑‑
3、输出最优的芯片全局自动布局效果。
技术总结本发明公开了基于深度强化学习的芯片全局自动布局方法，可对超大规模集成电路芯片快速布局，能够保证布局结果收敛以实现快速布局，并使得布局布线的线长、拥塞、面积达到近似最优。另外，芯片全局自动布局方法中提出一种空间利用率的方法，并将该空间利用率的方法应用在局部布局和全局自动布局中，从而使得局部布局和全局自动布局的面积达到最小。还有的是，应用异步训练网络结构，通过该网络结构学习训练，可使局部布局和全局自动布局相关性更紧密，且布局结果更容易收敛，能实现芯片全局自动布局的可靠性。自动布局的可靠性。自动布局的可靠性。
技术研发人员：陈学松 敖启缘 蔡述庭 张丽丽
受保护的技术使用者：广东工业大学
技术研发日：2022.06.23
技术公布日：2022/11/1
