基于深度强化学习的优化芯片布局系统及方法

1.本发明涉及的是一种芯片制造领域的技术，具体是一种基于深度强化学习的优化芯片布局系统及方法。


背景技术：

2.芯片布局问题是芯片设计过程中最复杂、最耗时的阶段之一。优化布局的目标是将宏元件(例如sram)和标准元件(逻辑门，例如nand、nor)放置到芯片板上，要求满足密度以及拥塞等约束的同时优化ppa目标(性能、功耗、面积)。现有求解布局问题的算法通常基于启发式算法、遗传算法、蒙特卡罗采样或者基于力导向的传统优化算法，在时间效率和对具体布局问题的设计复杂度上都具有瓶颈，且无法有效释放现有ai领域飞速发展的硬件算力。
3.现有的改进技术一般使用图神经网络得到图的特征向量，以反卷积的形式输出放置元件，但这类技术具有非常大的计算量，在tpu上需要数十小时训练，也难以在公开数据集上复现结果，且处理百万数量级的标准元件时采用了聚类和力导向的方法，无法得到完整并且准确的布局结果。


技术实现要素：

4.本发明针对现有技术不具备泛化能力，即使在大量数据上进行实验也不会提升算法的时间效率和性能，且无法有效释放ai领域飞速发展的硬件算力的不足，以及现有基于学习的布局技术都难以处理优化芯片布局问题中数量级巨大的状态空间的缺陷，提出一种基于深度强化学习的优化芯片布局系统及方法，采用机器学习方法设计新的优化布局问题求解器，通过人工优化常见的数据驱动机制，采用强化学习训练模型参数使算法具有泛化到新网表图的能力，同时通过卷积神经网络及图神经网络对状态空间建模，实现更好的拟合效果。
5.本发明是通过以下技术方案实现的：
6.本发明涉及一种基于深度强化学习的优化芯片布局系统，包括：数据预处理模块、策略网络模块、奖励预测模块和参数更新模块，其中：数据预处理模块读取并解析pl、net文件，将其中的网表图信息转换为智能体(agent)的初始状态以及奖励函数；策略网络模块通过卷积神经网络和图神经网络分别得到分别包含粗细粒度的全局嵌入特征与结点嵌入特征，将两个网络分别得到的特征向量融合，最终预测出当前时刻行为，即元件可能的放置位置的概率分布；奖励预测模块在网表图内的所有元件都放置完毕后，对布局结果进行总体评价，估计得到线长和拥塞程度指标反馈给智能体；参数更新模块根据从经验池中进行采样得到的样本采用近端策略优化算法(proximal policy optimization)周期地更新神经网络的参数。
7.优选地，为了保证当前元件能有效地放置，对输出的概率分布进行检验并找到合适的替代行为，具体为：
8.1)观察当前时刻棋盘的放置情况，用1表示已摆放元件的格点，得到大小为32*32(即棋盘规模)的图像。通过双线性插值对其上采样，最终输入84*84的图像给卷积神经网络，得到图像的特征向量。
9.2)将网表图抽取出的图输入到图卷积网络(gcn)进行处理，得到网表图的嵌入特征(embedding features)。
10.3)将图像的特征向量与图的嵌入特征进行拼接，经过全连接层后输出当前元件可能的放置位置，用长度为32*32的向量表示。
11.4)检验其预测的放置位置是否有效(即是否与之前放置的元件冲突)，当输出的位置已被占用，则以该位置为中心进行广度优先搜索，直到找到一个可用的放置位置。
12.所述的奖励预测包括传统预测算法和基于梯度的布局优化算法。
13.所述的传统预测算法是指：对于布局任务而言，真实的奖励值应该是eda工具的输出，包括线长，布线拥塞，密度，功耗等等。但强化学习模型通常至少需要上万轮来训练，为了尽可能高效地计算出奖励函数，选择了线长和拥塞这两个最重要的指标作为代表。使用最常见的半周长线长(hpwl)来近似绕线长度，即网表中所有节点边界框的半周长，具体为：min
b∈i
{xb})+(max
b∈i
{yb}-min
b∈i
{yb})+2，其中：xb和yb表示网端点的坐标，理论可以证明hpwl近似于斯坦纳树(steiner tree)的长度，也就是布线开销的下界。而针对拥塞的近似，采用矩形均匀线密度(rectangular uniform wire density，rudy)的估计方法，主要思路是将网表内的拥塞近似成均匀分布来计算，具体为：使用rudy来近似拥塞一方面在于这种方法比较直观，而且易于实现，另一方面则是hpwl正是计算过程的中间结果之一，进一步减小了计算开销。最后，定义奖励函数为线长和拥塞的加权求和，超参数λ有利于平衡这两个指标，具体为：r
t
＝-wirelength-λ*congestion，其中：wirelength和congestion分别为上述所定义的线长以及拥塞指标。
14.所述的基于梯度的布局优化算法是指：为了得到完整的布局结果，同时更准确地预测奖励值，将基于梯度的布局优化算法(例如dreamplace)结合到强化学习框架中，具体包括：
15.a)智能体放置完所有宏元件，将布局结果转换为标准的pl文件格式。
16.b)运行基于梯度的布局优化算法读取生成的pl文件及对应的网表图信息，迭代优化数百轮，得到标准元件的布局情况。
17.c)根据完整的布局结果计算其奖励值，更新选择动作的策略，如果训练未结束回到步骤1，训练结束则算法终止。
18.所述的近端策略优化算法是指：其中：r
t
为新策略与旧策略概率的比值，为t时刻的估计优势(advantage)，该算法很好地权衡了实现复杂度、样本复杂度和参数设计复杂度，它尝试在每次迭代时计算一次更新以最大化奖励函数，在计算梯度时还确保了与先前策略有相对较小的偏差。技术效果
19.本发明通过同时引入卷积神经网络和图神经网络的策略网络，提供了两种视角来建模布局问题，实现全局嵌入与结点嵌入信息的综合挖掘，与现有常规技术手段相比，本发明卷积神经网络将全局图像作为输入生成全局嵌入向量fg，而图神经网络提取节点嵌入特征fd。策略网络在经过拼接和全连接层之后最终输出可用位置的概率分布。
附图说明
20.图1为本发明策略网络结构图；
21.图2为本方法流程图；
22.图3为实施例中布局样例(即输入文件)示意图；
23.图4为优化后的布局效果图。
具体实施方式
24.基于强化学习的优化芯片布局求解器是优化布局问题研究发展的前沿方向之一，目前在此方向上的工作还处于比较基础的阶段。通常，强化学习算法会先把问题建模成一个马尔可夫决策过程(markov decision processes，mdps)。简单来说，就是智能体(agent)采取动作(action)，改变自己的状态(state)获得奖励(reward)并与环境(environment)发生交互的循环过程，具体为：m＝《s，a，p
s，a
，r》，其中：s表示状态，a表示动作，p
s，a
是状态转移函数，r表示奖励。
25.在具体问题中，将状态定义为当前时刻网表图的放置情况。根据粗细粒度的不同，把状态拆分成两部分：一部分把布局问题类比为在棋盘上摆放棋子，状态定义为一个用0，1表示的图像，1代表已经摆放了元件的格点，反之则是目前空闲的格点。这样表示的优势是抽象程度较高，处理图像的技术比较成熟，但却会造成具体元件位置信息的丢失，因此是对网表图的粗粒度刻画；另一部分则是把网表图建模成一个图结构，每个元件对应图中的“节点”(vertex)，用图中的“边”(edge)连接同一个网(net)中的所有元件，已放置的元件位置通过其对应节点的特征表示。这种建模方式的优势是更贴近真实的物理意义，几乎没有信息缺失。相应的，这种细粒度的表示方式使得状态空间极大，一般的学习算法可能并不适用。
26.所述的行动是指：当前时刻所选宏元件(macro)的放置位置，动作空间的大小与所选棋盘的规模有关，而状态转移概率只需依据状态的定义来进行。注意到强化学习的目标是通过对当前状态的观测与分析做出相应的动作，并以此获得尽可能高的奖励值。因此将奖励定义为布局结果的指标，即线长和拥塞的线性组合，在每轮(episode)结束的时候反馈给智能体。
27.如图1所示，为本实施例涉及一种基于深度强化学习的优化芯片布局系统，包括：数据预处理模块、策略网络模块、奖励预测模块和参数更新模块。
28.所述的数据预处理模块包括：输入单元、解析单元以及输出单元，其中：输入单元读取pl、net格式文件，得到处理的中间结果(列表数据)，解析单元根据列表信息，提取其中待布局的宏元件以及对应的网表，得到智能体的初始状态以及奖励函数，输出单元根据宏元件布局结果，将结果写入对应的pl格式文件，得到布局输出。
29.所述的策略网络模块包括：卷积神经网络单元、图神经网络单元以及全连接层单
元，其中：卷积神经网络单元根据全局图像信息，得到全局嵌入向量，图神经网络单元根据网表图信息，提取当前布局元件的节点嵌入特征，全连接层单元根据全局嵌入向量以及节点嵌入信息，进行特征融合处理，得到有效布局位置的概率分布。
30.所述的奖励预测模块包括：传统预测单元以及基于梯度的布局优化单元，其中：传统预测单元根据网中元件布局坐标，根据公式分别计算线长和布线拥塞这两种指标，加权求和后得到该种布局的奖励值，基于梯度的布局优化单元根据宏元件布局情况，将布局结果转换为标准的pl文件格式，运行基于梯度的布局优化算法迭代优化数百轮得到标准元件的布局结果以及对应的评价指标。
31.所述的参数更新模块包括：损失计算单元以及参数更新单元，其中：损失计算单元根据奖励值计算新策略与旧策略概率的比值以及估计优势，参数更新单元根据损失函数更新策略网络参数，并重新与环境交互得到新的奖励。
32.本实施例根据上述系统的基于深度强化学习的优化芯片布局方法，具体包括：
33.步骤1)通过数据预处理模块接收描述待布局电路中元件及网表图信息的数据文件，将提取出的状态保存到计算机内存中，供算法模块处理；
34.步骤2)构建一个空白棋盘网格，初始化结果列表，选择一个待放置的宏元件；
35.步骤3)通过策略网络预测元件可能的放置位置，并检验结果是否有效。当所选位置已被占用，则搜索得到可用的放置位置，同时选择下一个待放置元件；
36.步骤4)当还有宏元件未被放置，回到步骤3，否则进入步骤5；
37.步骤5)当需要放置标准元件，进入步骤6，否则进入步骤7；
38.步骤6)运行基于梯度的布局优化算法读取结果列表中的宏元件位置，经过迭代优化后完成标准元件的放置。
39.步骤7)根据对应方式计算得到本次的奖励值，适当更新选择智能体动作的策略，当训练未结束回到步骤2，训练到达设定的轮数则进入步骤8；
40.步骤8)训练完毕后，就得到了一个可以用于解决芯片布局问题的求解器。
41.经过具体实际实验，在ispd-2005这一具体数据集下，以学习率为2.5*10-4
，更新步长为2056参数启动/运行上述装置/方法，能够得到的实验数据如表1所示。
42.与现有技术相比，在所有测试电路上，本方法与独立布局宏元件与标准元件都可以得到可行的最终布局结果，而直接运行dreamplace时由于宏元件之间的拥塞过大无法得到可行的布局结果。与独立学习方法相比，本方法对于所有测试电路在线长指标上都有明显的提升。并且本方法给予了用更多的计算能力来提升布局问题求解效率的可能；本发明具有泛化能力，能够从数据中自适应地学习模型参数，无需大量专家经验；可以快速放置所有的宏元件以及标准元件，同时实现更好的布局结果，使得用户能够渐进的求解放置宏元
件，用户可以观察、评估布局质量。
43.上述具体实施可由本领域技术人员在不背离本发明原理和宗旨的前提下以不同的方式对其进行局部调整，本发明的保护范围以权利要求书为准且不由上述具体实施所限，在其范围内的各个实现方案均受本发明之约束。

技术特征：
1.一种基于深度强化学习的优化芯片布局系统，其特征在于，包括：数据预处理模块、策略网络模块、奖励预测模块和参数更新模块，其中：数据预处理模块读取并解析pl、net文件，将其中的网表图信息转换为智能体的初始状态以及奖励函数；策略网络模块通过卷积神经网络和图神经网络分别得到分别包含粗细粒度的全局嵌入特征与结点嵌入特征，将两个网络分别得到的特征向量融合，最终预测出当前时刻行为，即元件可能的放置位置的概率分布；奖励预测模块在网表图内的所有元件都放置完毕后，对布局结果进行总体评价，估计得到线长和拥塞程度指标反馈给智能体；参数更新模块根据从经验池中进行采样得到的样本采用近端策略优化算法周期地更新神经网络的参数。2.根据权利要求1所述的的优化芯片布局系统，其特征是，对输出的概率分布进行检验并找到合适的替代行为，具体为：1)观察当前时刻棋盘的放置情况，用1表示已摆放元件的格点，得到大小为32*32的图像；通过双线性插值对其上采样，最终输入84*84的图像给卷积神经网络，得到图像的特征向量；2)将网表图抽取出的图输入到图卷积网络进行处理，得到网表图的嵌入特征；3)将图像的特征向量与图的嵌入特征进行拼接，经过全连接层后输出当前元件可能的放置位置，用长度为32*32的向量表示；4)检验其预测的放置位置是否有效，即是否与之前放置的元件冲突，当输出的位置已被占用，则以该位置为中心进行广度优先搜索，直到找到一个可用的放置位置。3.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的奖励预测包括传统预测算法和基于梯度的布局优化算法；所述的基于梯度的布局优化算法是指：为了得到完整的布局结果，同时更准确地预测奖励值，将基于梯度的布局优化算法结合到强化学习框架中，具体包括：a)智能体放置完所有宏元件，将布局结果转换为标准的pl文件格式；b)运行基于梯度的布局优化算法读取生成的pl文件及对应的网表图信息，迭代优化数百轮，得到标准元件的布局情况；c)根据完整的布局结果计算其奖励值，更新选择动作的策略，如果训练未结束回到步骤1，训练结束则算法终止。4.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的近端策略优化算法是指：其中：r
t
为新策略与旧策略概率的比值，为t时刻的估计优势，该算法很好地权衡了实现复杂度、样本复杂度和参数设计复杂度，它尝试在每次迭代时计算一次更新以最大化奖励函数，在计算梯度时还确保了与先前策略有相对较小的偏差。5.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的数据预处理模块包括：输入单元、解析单元以及输出单元，其中：输入单元读取pl、net格式文件，得到处理的中间结果(列表数据)，解析单元根据列表信息，提取其中待布局的宏元件以及对应的网表，得到智能体的初始状态以及奖励函数，输出单元根据宏元件布局结果，将结果写入对应的pl格式文件，得到布局输出。6.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的策略网络模块包括：
卷积神经网络单元、图神经网络单元以及全连接层单元，其中：卷积神经网络单元根据全局图像信息，得到全局嵌入向量，图神经网络单元根据网表图信息，提取当前布局元件的节点嵌入特征，全连接层单元根据全局嵌入向量以及节点嵌入信息，进行特征融合处理，得到有效布局位置的概率分布。7.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的奖励预测模块包括：传统预测单元以及基于梯度的布局优化单元，其中：传统预测单元根据网中元件布局坐标，根据公式分别计算线长和布线拥塞这两种指标，加权求和后得到该种布局的奖励值，基于梯度的布局优化单元根据宏元件布局情况，将布局结果转换为标准的pl文件格式，运行基于梯度的布局优化算法迭代优化数百轮得到标准元件的布局结果以及对应的评价指标。8.根据权利要求1所述的的优化芯片布局系统，其特征是，所述的参数更新模块包括：损失计算单元以及参数更新单元，其中：损失计算单元根据奖励值计算新策略与旧策略概率的比值以及估计优势，参数更新单元根据损失函数更新策略网络参数，并重新与环境交互得到新的奖励。9.根据权利要求1～8中任一所述系统的基于深度强化学习的优化芯片布局方法，其特征在于，包括：步骤1)通过数据预处理模块接收描述待布局电路中元件及网表图信息的数据文件，将提取出的状态保存到计算机内存中，供算法模块处理；步骤2)构建一个空白棋盘网格，初始化结果列表，选择一个待放置的宏元件；步骤3)通过策略网络预测元件可能的放置位置，并检验结果是否有效；当所选位置已被占用，则搜索得到可用的放置位置，同时选择下一个待放置元件；步骤4)当还有宏元件未被放置，回到步骤3，否则进入步骤5；步骤5)当需要放置标准元件，进入步骤6，否则进入步骤7；步骤6)运行基于梯度的布局优化算法读取结果列表中的宏元件位置，经过迭代优化后完成标准元件的放置；步骤7)根据对应方式计算得到本次的奖励值，适当更新选择智能体动作的策略，当训练未结束回到步骤2，训练到达设定的轮数则进入步骤8；步骤8)训练完毕后，就得到了一个可以用于解决芯片布局问题的求解器。

技术总结
一种基于深度强化学习的优化芯片布局系统及方法，包括：数据预处理模块、策略网络模块、奖励预测模块和参数更新模块，其中：数据预处理模块读取并解析pl、net文件，将其中的网表图信息转换为智能体的初始状态以及奖励函数；策略网络模块通过卷积神经网络和图神经网络分别得到分别包含粗细粒度的全局嵌入特征与结点嵌入特征，将两个网络分别得到的特征向量融合，最终预测出当前时刻行为，即元件可能的放置位置的概率分布；奖励预测模块在网表图内的所有元件都放置完毕后，对布局结果进行总体评价，估计得到线长和拥塞程度指标反馈给智能体；参数更新模块根据从经验池中进行采样得到的样本采用近端策略优化算法周期地更新神经网络的参数，实现更好的拟合效果。实现更好的拟合效果。实现更好的拟合效果。


技术研发人员：程若愚 严骏驰
受保护的技术使用者：上海交通大学
技术研发日：2021.11.25
技术公布日：2022/3/8