基于强化学习的三维固定轮廓集成电路布图规划方法及系统

1.本发明属于三维集成电路设计及机器学习技术领域，尤其涉及一种基于强化学习的三维固定轮廓集成电路布图规划方法及系统。


背景技术：

2.近年来随着超大规模集成电路的飞速发展，芯片中晶体管集成度不断提高，芯片性能大幅度增强。然而，如今工艺尺寸已逐渐逼近物理极限，难以通过减小工艺尺寸的方式大幅提高晶体管集成度，“摩尔定律”面临严峻挑战。三维集成电路被认为是延续“摩尔定律”定律最有前景的解决方案之一，它将多层芯片在垂直方向上进行堆叠，并通过tsv
3.(through-silicon via；硅通孔)技术实现各层芯片在垂直方向上的连接和通信。相较于二维集成电路，三维集成电路具有功耗低、集成度高、芯片尺寸小等优点。
4.布图规划是集成电路物理设计阶段的第一步，也是最为关键的步骤。在三维集成电路布图规划阶段，需要对电路进行划分，将电路模块和tsv抽象成几何图形放置到多层芯片上，确定模块和tsv所在的层和具体位置，在模块、tsv相互不重叠的约束条件下优化芯片面积、连线长度和tsv数目。集成电路布图规划阶段可以提供前期规划阶段的反馈数据，指导系统架构的调整，同时，布图规划的结果对布局和布线等后续步骤有着重要影响。
5.目前布图规划的求解主要有模拟退火和分析型两类方法。模拟退火算法使用布图规划表示方法编码电路，构造搜索空间，对布图解进行随机扰动，生成邻域布图解，然后通过模拟退火策略确定搜索方向。该类方法适用于小规模电路，处理大规模电路时存在收敛速度慢的问题。分析型方法将约束条件(软模块、模块重叠、固定轮廓等)通过数学公式表达，建立成有约束的优化问题，优化目标函数获得布图解。该类方法运行时间短，同时能处理复杂约束。然而，布图规划问题中的约束和目标需要用近似的可微函数表示，只能生成约束条件松弛后的解并不能生成严格的合法解，且其性能受超参数影响较大，可靠性不如模拟退火算法。强化学习具有自学习和泛化能力，近年来被广泛应用于组合优化领域，其智能体通过与环境交互，以“试错”的方式进行学习，积累经验，以获得最大回报。基于强化学习的搜索框架相比模拟退火算法拥有更快的收敛速度，相比分析型方法更具稳定性和可靠性。基于此，本发明首次对三维集成电路布图规划问题的局部搜索框架进行强化学习建模，提出了一个两阶段的布图规划方法，依次布图模块和tsv，在模块布图阶段运用基于强化学习的搜索框架搜索模块布图解。tsv布图阶段，在模块布图解的基础上保持模块的相对位置，运用模拟退火算法完成tsv的布图，输出最终布图解。


技术实现要素：

6.为克服以上现有技术存在的缺陷，本发明提供了一种基于强化学习的三维固定轮廓集成电路布图规划方法及系统。
7.本发明采取如下技术方案：
8.一种基于强化学习的三维固定轮廓集成电路布图规划方法，包括如下步骤：
9.s1，数据预处理：获取模块及网表信息，计算模块面积；
10.s2，层分配：根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的tsv(through-silicon via；硅通孔)数量；
11.s3，模块布图：采用序列对(sequence pair)作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp(马尔可夫决策过程)表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；
12.s4，tsv布图：在模块布图的基础上进行tsv布图，输出最终布图解。
13.优选的，所述步骤s2具体包括：
14.s21，根据模块面积以及网表信息，通过超图划分工具kahypar将电路划分为k部分，其中k等于三维集成电路的层数。
15.s22，运用模拟退火算法对划分结果进行优化，平衡各层模块和tsv的总面积。模拟退火算法执行的扰动是交换两个不同层的模块，目标函数如下：
[0016][0017]
其中n
tsv
表示tsv的总数，k表示层数，ai表示第i层模块和tsv的面积总和，表示每层模块和tsv的平均面积。
[0018]
优选的，所述步骤s3具体包括：
[0019]
s31，本阶段完成模块布图规划，目标函数定义如下：
[0020][0021]
表示可行的模块布图解，η为权重系数。a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：
[0022]
a＝ew+eh·
λ+c1·
max{ew,eh·
λ}+c2·
max{w,h
·
λ}
[0023]
w和h分别表示当前布图的宽度和高度，ew＝max{w-w0,0}，eh＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，ew、eh为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：
[0024][0025]
a表示所有模块的总面积，k表示层数，γ表示空白面积分数，λ表示固定轮廓的长宽比。w(
·
)为线长函数，运用半周长模型(hpwl)来评估模块布图的线长：
[0026][0027]
m表示网的总数，分别表示网ni中模块的最大x坐标、最小x坐标、最大y坐标、最小y坐标。
[0028]
s32，运用序列对作为模块布图规划的表示方法，每一层的模块均用序列对[γ1,γ2]对来表示模块间的相对位置关系。
[0029]
s33，将模块三维布图规划的局部搜索过程通过mdp表示：
[0030]
状态空间：每一个状态s都是一个完整的布图解。完整的布图解包括每层一组序列对[γ1,γ2],以及模块的朝向序列(水平、垂直通过0、1表示)。
[0031]
动作空间：通过定义的若干扰动(扰动均在同一层进行)，产生邻域状态，定义的扰动如下：
[0032]
·
随机在γ1中交换两个模块。
[0033]
·
随机在γ2中交换两个模块。
[0034]
·
同时随机在γ1,γ2中交换两个模块。
[0035]
·
随机选择一个模块将他放入其他任意位置。
[0036]
·
随机选择一个模块旋转90
°
。
[0037]
采样一组邻域状态，智能体选择接受移动到其中一个状态或拒绝移动，所以动作空间为采样的邻域状态数量加一。
[0038]
状态转移：给定一个布图解(状态)，上述的任何扰动都会导致原状态转移到另一个确定的状态。
[0039]
奖励：将每一步减小的成本(δε)作为奖励r，并将初始成本作为基准(baseline)，通过将减小的成本除以初始成本将奖励r归一化到[0,1]。
[0040][0041]
s34，提取状态特征，状态特征包括当前状态成本ε、采样邻域状态的成本ε
′
、本轮目前最低成本ε
*
、本轮目前平均成本本轮最低成本至当前状态的平均成本采样邻域状态中的最低成本ε
′
*
，受扰动影响的模块数量num
per
，受扰动影响的模块面积area
per
，当前状态与前n步状态的距离dn，搜索进度t。
[0042]
成本特征：设初始成本为ε0，所有与成本相关的特征均通过min(1,ε/ε
0-1)归一化至[-1,1]。
[0043]
布图特征：定义受扰动影响的模块为扰动前后坐标变动的模块，受扰动影响的模块的数量和面积通过除以模块的总数和总面积进行归一化，范围为[0,1]。
[0044]
状态距离特征：计算当前状态序列对γ1、γ2和之前状态对应序列对γ1′
、γ2′
的编辑距离编辑距离(序列对γ1、γ2转换为序列对γ1′
、γ2′
所需编辑操作的总成本，编辑操作包括插入、修改、删除)和朝向序列的真实匹配距离d
ori
(两个序列中对应位置元素不同的次数)。d
ori
可以通过除以模块的总数num
block
归一化至[0,1]。当前状态(当前搜索步数为t)与前n步状态的距离为：
[0045][0046]
搜索进度特征：当前搜索步数和设置的每轮最大步数的比值。
[0047]
s35，构建基于dqn的模块三维布图规划模型，dqn神经网络的隐藏层通过relu函数激活，将特征串联输入，输入的维数即为特征的维数，神经网络的输出是动作的价值预测，输出的维数为1。定义动作价值函数q
π
(s
t
,a
t
)为观测到在策略π下某个状态s执行动作a以后所能达到奖励的期望
[0048][0049]
γ为折扣率，t为时间步，最优动作价值函数q
*
(s,a)＝max
π
q(s,a)，用神经网络近似最优动作价值函数q(s,a；θ)≈q
*
(s,a)，其中θ为神经网络的参数。q网络每次迭代i损失函数：
[0050]
l(θi)＝e
s,a～ρ(
·
)
[(y
i-q(s,a；θ)2]＝e
(
·
)
[(r+γmaxa′
q(s
′
,a
′
；θ
i-1
)-q(s,a；θ))2]
[0051]
其中ρ(
·
)是关于状态s和动作a的概率分布，通过反向传播算法更新模型；
[0052]
s36，随机生成数据集作为训练集。
[0053]
s37，进行m轮训练，输出模块的布图解。
[0054]
优选的，步骤s4具体包括：
[0055]
s41，将模块分布在不同层的网按层划分成包含tsv的子网，子网包括这一层中的模块、tsv以及上一层的tsv。
[0056]
s42，对tsv进行编号，将每一层的tsv随机插入s3中输出的模块布图解序列对中(tsv为正方形，无朝向)，运用模拟退火算法对tsv进行布图，扰动为随机选择某一层并随机选择这一层中的一个tsv，将其随机放入其他任意位置，扰动不改变序列对中模块的相对位置。目标函数为：
[0057]
ε(fp)＝a(fp)+ηw(fp)
[0058]
fp为可行的模块和tsv布图解，η为权重系数。a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：
[0059]
a＝ew+eh·
λ+c1·
max{ew,eh·
λ}+c2·
max{w,h
·
λ}
[0060]
w和h分别表示当前模块和tsv布图的宽度和高度，ew＝max{w-w0,0}，eh＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，ew，eh为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：
[0061][0062]
a表示所有模块和tsv的总面积，k表示层数，γ表示空白面积分数，λ表示固定轮廓的长宽比。
[0063]
w(
·
)为线长函数，运用半周长模型(hpwl)来评估模块和tsv布图的线长，线长的大小为所有子网线长的总和：
[0064][0065]
m表示网的总数，分别表示子网ni中这层的模块、tsv和上一层tsv在该层映射位置的最大x坐标、最小x坐标、最大y坐标、最小y坐标。
[0066]
s43，输出最终布图解，包括各层模块和tsv的序列对、模块的朝向序列以及模块和tsv所在的层次和坐标。
[0067]
本发明还公开了一种基于强化学习的三维固定轮廓集成电路布图规划系统，用于
执行上述的方法，其包括如下模块：
[0068]
数据预处理模块：获取模块及网表信息，计算模块面积；
[0069]
层分配模块：根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的tsv数量；
[0070]
布图解输出模块：采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；
[0071]
tsv布图模块：在模块布图的基础上进行tsv布图，输出最终布图解。
[0072]
本发明与现有技术相比，有益效果如下：
[0073]
(1)首次对三维集成电路布图规划问题的局部搜索框架进行强化学习建模，在模块布图阶段提出了一个基于强化学习的搜索框架，通过智能体对解空间的探索，使其获得有效的启发式特性，相比模拟退火算法具有更快的收敛速度，相比分析类方法更具稳定性和可靠性；
[0074]
(2)设计状态距离特征用于计算搜索过程中不同状态差异，进而评估当前搜索阶段搜索区域的大小，避免陷入局部最优，指导智能体更好均衡探索和利用；
[0075]
(3)采用两阶段的布图规划方法，依次对模块和tsv进行布图，相比模块和tsv协同布图的方法，本发明减小了解空间，加快了算法的收敛。
附图说明
[0076]
图1为本发明优选实施例一种基于强化学习的三维固定轮廓集成电路布图规划方法的流程图。
[0077]
图2是实施例1中6个模块的布图。
[0078]
图3为本发明优选实施例一种基于强化学习的三维固定轮廓集成电路布图规划系统框图。
具体实施方式
[0079]
下面结合附图及优选实施例对本发明做详细说明。
[0080]
实施例1
[0081]
如图1所示，本实施例一种基于强化学习的三维固定轮廓集成电路布图规划方法，包括如下步骤：
[0082]
s1，数据预处理：获取gsrc基准中n100数据集模块及网表信息，n100数据集包含了100个模块和551张网(不包含i/o pad和i/o pad所在的网)，根据模块的长、宽信息，计算模块面积；
[0083]
s2，层分配：根据模块面积及网表信息，运用kahypar超图划分工具对电路进行划分，并运用模拟退火算法对划分结果进行优化，将模块分配到不同层并确定每一层的tsv数量；
[0084]
步骤s2具体如下：
[0085]
s21，根据模块面积以及网表信息，通过超图划分工具kahypar将电路划分为k部分，其中k等于三维集成电路的层数。
[0086]
s22，运用模拟退火算法对划分结果进行优化，平衡各层模块和tsv的总面积。模拟
退火算法执行的扰动是交换两个不同层的模块，目标函数如下：
[0087][0088]
其中，n
tsv
表示tsv的总数，k表示层数，ai表示第i层模块和tsv的面积总和，表示每层模块和tsv的平均面积。本实施例中k＝4,即将电路划分为4层。
[0089]
s3，模块布图：采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；
[0090]
步骤s3具体如下：
[0091]
s31，本阶段完成模块布图规划，目标函数定义如下：
[0092][0093]
表示可行的模块布图解，η为权重系数。a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：
[0094]
a＝ew+eh·
λ+c1·
max{ew,eh·
λ}+c2·
max{w,h
·
λ}
[0095]
w和h分别表示当前布图的宽度和高度，ew＝max{w-w0,0}，eh＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，ew、eh为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：
[0096][0097]
a表示所有模块的总面积，k＝4表示层数，γ＝20％表示空白面积分数，λ＝1表示固定轮廓的长宽比。
[0098]
w(
·
)为线长函数，运用半周长模型(hpwl)来评估模块布图的线长：
[0099][0100]
m表示网的总数，分别表示网ni中模块的最大x坐标、最小x坐标、最大y坐标、最小y坐标。
[0101]
s32，运用序列对作为模块布图规划的表示方法，每一层的模块均用序列对[γ1,γ2]对来表示模块间的相对位置关系。如图2中所示6个模块的布图，可用[431625,635412]表示，六个模块的信息(长，宽)分别为1(4,6)，2(3,7),3(3,3)，4(2,3),5(4,3),6(6,4)。
[0102]
s33，将模块三维布图规划的局部搜索过程通过mdp表示：
[0103]
状态空间：每一个状态s都是一个完整的布图解。完整的布图解包括每层一组序列对[γ1,γ2],以及模块的朝向序列(水平、垂直通过0、1表示)。
[0104]
动作空间：通过定义的若干扰动(扰动均在同一层进行)，产生邻域状态，定义的扰动如下：
[0105]
·
随机在γ1中交换两个模块。
[0106]
·
随机在γ2中交换两个模块。
[0107]
·
同时随机在γ1,γ2中交换两个模块。
[0108]
·
随机选择一个模块将他放入其他任意位置。
[0109]
·
随机选择一个模块旋转90
°
。
[0110]
采样一组邻域状态，智能体选择接受其中一个状态或拒绝，所以动作空间为采样的邻域状态数量加一。
[0111]
状态转移：给定一个布图解(状态)，上述的任何扰动都会导致原状态转移到另一个确定的状态。
[0112]
奖励：将每一步减小的成本(δε)作为奖励，并将初始成本作为基准(baseline)，通过将减小的成本除以初始成本将奖励归一化到[0,1]。
[0113][0114]
s34，提取状态特征，状态特征包括当前状态成本ε、采样邻域状态的成本ε
′
、本轮目前最低成本ε
*
、本轮目前平均成本本轮最低成本至当前状态的平均成本采样邻域状态中的最低成本ε
′
*
，受扰动影响的模块数量num
per
，受扰动影响的模块面积area
per
，当前状态与前n步状态的距离dn，搜索进度t。
[0115]
成本特征：设初始成本为λ0，所有与成本相关的特征均通过min(1,ε/ε
0-1)归一化至[-1,1]。
[0116]
布图特征：定义受扰动影响的模块为扰动前后坐标变动的模块，受扰动影响的模块的数量和面积通过除以模块的总数和总面积进行归一化，范围为[0,1]。
[0117]
状态距离特征：计算当前状态序列对γ1、γ2和之前状态对应序列对γ1′
、γ2′
的编辑距离编辑距离(序列对γ1、γ2转换为序列对γ1′
、γ2′
所需编辑操作的总成本，编辑操作包括插入、修改、删除)和朝向序列的真实匹配距离d
ori
(两个序列中对应位置元素不同的次数)。d
ori
可以通过除以模块的总数num
block
归一化至[0,1]。当前状态(当前搜索步数为t)与前n步状态的距离为
[0118][0119]
搜索进度特征：当前搜索步数和设置的每轮最大步数的比值。
[0120]
本实施例的状态距离特征包括当前状态与本轮成本最低状态的距离d
ε*
、当前状态与前10步状态的距离d
10
、当前状态与前100步状态的距离d
100
、当前状态与前1000步状态的距离d
1000
。
[0121][0122]
s35，构建基于dqn的模块三维布图规划模型，dqn神经网络的隐藏层通过relu函数激活，将特征串联输入，输入的维数即为特征的维数，神经网络的输出是动作的价值预测，输出的维数为1。定义动作价值函数q
π
(s
t
,a
t
)为观测到在策略π下某个状态s执行动作a以后所能达到奖励的期望：
[0123][0124]
γ为折扣率，t为时间步，最优动作价值函数q
*
(s,a)＝max
π
q(s,a)，用神经网络近似最优动作价值函数q(s,a；θ)≈q
*
(s,a)，其中θ为神经网络的参数。q网络每次迭代i损失函数：
[0125]
l(θi)＝e
s,a～ρ(
·
)
[(y
i-q(s,a；θ)2]＝e
(
·
)
[(r+γmaxa′
q(s
′
,a
′
；θ
i-1
)-q(s,a；θ))2]
[0126]
其中ρ(
·
)是关于状态s和动作a的概率分布，通过反向传播算法更新模型；
[0127]
s36，随机生成100个模块和500个网的数据集作为训练集，其中模块长、宽在10-100μm之间，网表中250个网包含2个模块，250个网包含3个模块。
[0128]
s37，进行m＝200轮训练，输出模块的布图解。
[0129]
步骤s37具体如下：
[0130]
s371，初始化经验池d，容量n＝20000；随机初始化网络q的权重θ；设置贪婪策略∈＝0.05；设置终止条件，若在最后w＝1000步没有找到更好的解，则结束本轮搜索；
[0131]
s372，进行m＝200轮迭代，每轮随机生成初始状态为s0，每一轮执行最多t＝50000步动作；
[0132]
s373，对于第m轮迭代，t时刻状态为s
t
，每一步生成范围为[0,1]的随机数u；若u≥∈，随机选择动作a
t
，若u《∈，到达下一状态s
t+1
，存储(s
t
,a
t
,r
t
,s
t+1
)至经验池d。
[0133]
s374，若达到终止条件或已执行t步动作，结束本轮搜索，若未达到，则继续搜索；
[0134]
s375，若存储的容量n》n，从经验池d中选取一组(s
t
,a
t
,r
t
,s
t+1
)，若s
t+1
为最终状态，则y
t
＝r
t
，若s
t+1
不是最终状态，则计算损失l，通过反向传播算法更新θ。
[0135]
s4，tsv布图：运用模拟退火算法，在模块布图的基础上进行tsv布图，输出最终布图解。
[0136]
步骤s4具体如下：
[0137]
s41，tsv采用via-first的封装方式，tsv均分布在1、2、3层，将模块分布在不同层的网按层划分成包含tsv的子网，子网包括这一层中的模块、tsv以及上一层的tsv。
[0138]
s42，tsv取边长为3μm的正方形，对tsv进行编号，将每一层的tsv随机插入s3中输出的模块布图解序列对中(tsv为正方形，无朝向)，运用模拟退火算法对tsv进行布图，扰动为随机选择某一层并随机选择这一层中的一个tsv，将其随机放入其他任意位置，扰动不改变序列对中模块的相对位置。目标函数为：
[0139]
ε(fp)＝a(fp)+ηw(fp)
[0140]
fp为可行的模块和tsv布图解，η为权重系数。a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：
[0141]
a＝ew+eh·
λ+c1·
max{ew,eh·
λ}+c2·
max{w,h
·
λ}
[0142]
w和h分别表示当前模块和tsv布图的宽度和高度，ew＝max{w-w0,0}，eh＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，ew，eh为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：
[0143][0144]
a表示所有模块和tsv的总面积，k＝4，γ＝20％表示空白面积分数，λ＝1表示固定轮廓的长宽比。
[0145]
w(
·
)为线长函数，运用半周长模型(hpwl)来评估模块和tsv布图的线长，线长的大小为所有子网线长的总和：
[0146][0147]
m表示网的总数，分别表示子网ni中这层的模块、tsv和上一层tsv在该层映射位置的最大x坐标、最小x坐标、最大y坐标、最小y坐标。
[0148]
s43，输出最终布图解，包括各层模块和tsv的序列对、模块的朝向序列以及模块和tsv所在的层次和坐标。
[0149]
实施例2
[0150]
如图3所示，本实施例一种基于强化学习的三维固定轮廓集成电路布图规划系统，包括如下模块：
[0151]
数据预处理模块：获取模块及网表信息，计算模块面积；
[0152]
层分配模块：根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的tsv数量；
[0153]
布图解输出模块：采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；
[0154]
tsv布图模块：在模块布图的基础上进行tsv布图，输出最终布图解。
[0155]
本实施例其他内容可参考实施例1。
[0156]
综上，本发明属于三维集成电路设计及机器学习技术领域，具体涉及一种基于强化学习的三维固定轮廓集成电路布图规划方法及系统，本发明方法包括如下步骤：s1，数据预处理：获取模块及网表信息，计算模块面积；s2，层分配：根据模块面积及网表信息，运用kahypar超图划分工具对电路进行划分，并运用模拟退火算法对划分结果进行优化，将模块分配到不同层并确定每一层的tsv(through-silicon via；硅通孔)数量；s3，模块布图：采用序列对(sequence pair)作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp(马尔可夫决策过程)表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；s4，tsv布图：运用模拟退火算法，在模块布图的基础上进行tsv布图，输出最终布图解。本发明能有效地完成三维集成电路布图规划，并获得线长更优的方案。
[0157]
以上所述仅是对本发明的优选实施例及原理进行了详细说明，对本领域的普通技术人员而言，依据本发明提供的思想，在具体实施方式上会有改变之处，而这些改变也应视为本发明的保护范围。

技术特征：
1.一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于，包括如下步骤：s1，获取模块及网表信息，计算模块面积；s2，根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的tsv数量；s3，采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；s4，在模块布图的基础上进行tsv布图，输出最终布图解。2.根据权利要求1所述的一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于：步骤s2具体如下：s21，根据模块面积以及网表信息，通过超图划分工具kahypar将电路划分为k部分，其中k等于三维集成电路的层数；s22，运用模拟退火算法对划分结果进行优化，平衡各层模块和tsv的总面积；模拟退火算法执行的扰动是交换两个不同层的模块，目标函数如下：其中，n
tsv
表示tsv的总数，k表示层数，a
i
表示第i层模块和tsv的面积总和，表示每层模块和tsv的平均面积。3.根据权利要求2所述的一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于：步骤s3具体如下：s31，完成模块布图规划，目标函数定义如下：ε(fp
b
)＝a(fp
b
)+ηw(fp
b
)fp
b
表示可行的模块布图解，η为权重系数；a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：a＝e
w
+e
h
·
λ+c1·
max{e
w
,e
h
·
λ}+c2·
max{w,h
·
λ}w和h分别表示当前布图的宽度和高度，e
w
＝max{w-w0,0}，e
h
＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，e
w
、e
h
为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：a表示所有模块的总面积，k表示层数，γ表示空白面积分数，λ表示固定轮廓的长宽比；w(
·
)为线长函数，运用半周长模型评估模块布图的线长：m表示网的总数，分别表示网n
i
中模块的最大x坐标、最小x坐
标、最大y坐标、最小y坐标；s32，运用序列对作为模块布图规划的表示方法，每一层的模块均用序列对[γ1,γ2]对来表示模块间的相对位置关系；s33，将模块三维布图规划的局部搜索过程通过mdp表示；s34，提取状态特征，状态特征包括当前状态成本ε、采样邻域状态的成本ε
′
、本轮目前最低成本ε
*
、本轮目前平均成本本轮最低成本至当前状态的平均成本采样邻域状态中的最低成本ε
′
*
，受扰动影响的模块数量num
per
，受扰动影响的模块面积area
per
，当前状态与前n步状态的距离d
n
，搜索进度t；s35，构建基于dqn的模块三维布图规划模型，dqn神经网络的隐藏层通过relu函数激活，将特征串联输入，输入的维数即为特征的维数，神经网络的输出是动作的价值预测，输出的维数为1；定义动作价值函数q
π
(s
t
,a
t
)为观测到在策略π下某个状态s执行动作a以后所能达到奖励的期望：γ为折扣率，t为时间步，最优动作价值函数q
*
(s,a)＝max
π
q(s,a)，用神经网络近似最优动作价值函数q(s,a；θ)≈q
*
(s,a)，其中θ为神经网络的参数；q网络每次迭代i损失函数：l(θ
i
)＝e
s,a～ρ(
·
)
[(y
i-q(s,a；θ)2]＝e
(
·
)
[(r+γmax
a
′
q(s
′
,a
′
；θ
i-1
)-q(s,a；θ))2]其中ρ(
·
)是关于状态s和动作a的概率分布，通过反向传播算法更新模型；s36，随机生成数据集作为训练集；s37，进行m轮训练，输出模块的布图解。4.根据权利要求3所述的一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于：步骤s33中，将模块三维布图规划的局部搜索过程通过mdp表示具体如下：状态空间：每一个状态s都是一个完整的布图解；完整的布图解包括每层一组序列对[γ1,γ2],以及模块的朝向序列，水平、垂直通过0、1表示；动作空间：通过定义的若干扰动，产生邻域状态，定义的扰动如下：
·
随机在γ1中交换两个模块；
·
随机在γ2中交换两个模块；
·
同时随机在γ1,γ2中交换两个模块；
·
随机选择一个模块将他放入其他任意位置；
·
随机选择一个模块旋转90
°
；采样一组邻域状态，智能体选择接受其中一个状态或拒绝，动作空间为采样的邻域状态数量加一；状态转移：给定一个布图解，任何扰动都会导致原状态转移到另一个确定的状态；奖励：将每一步减小的成本δε作为奖励r，并将初始成本作为基准baseline，通过将减小的成本除以初始成本将奖励r归一化到[0,1]，5.根据权利要求4所述的一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于：步骤s34中：
成本特征：设初始成本为ε0，所有与成本相关的特征均通过min(1,ε/ε
0-1)归一化至[-1,1]；布图特征：定义受扰动影响的模块为扰动前后坐标变动的模块，受扰动影响的模块的数量和面积通过除以模块的总数和总面积进行归一化，范围为[0,1]；状态距离特征：计算当前状态序列对γ1、γ2和之前状态对应序列对γ1′
、γ2′
的编辑距离离和朝向序列的真实匹配距离d
ori
，两个序列中对应位置元素不同的次数，序列对γ1、γ2转换为序列对γ1′
、γ2′
所需编辑操作的总成本，编辑操作包括插入、修改、删除；d
ori
可以通过除以模块的总数num
block
归一化至[0,1]；当前搜索步数为t，当前状态与前n步状态的距离为：搜索进度特征：当前搜索步数和设置的每轮最大步数的比值。6.根据权利要求5所述的一种基于强化学习的三维固定轮廓集成电路布图规划方法，其特征在于：步骤s4具体如下：s41，将模块分布在不同层的网按层划分成包含tsv的子网，子网包括这一层中的模块、tsv以及上一层的tsv；s42，对tsv进行编号，将每一层的tsv随机插入s3中输出的模块布图解序列对中，运用模拟退火算法对tsv进行布图，扰动为随机选择某一层并随机选择这一层中的一个tsv，将其随机放入其他任意位置，扰动不改变序列对中模块的相对位置；目标函数为：ε(fp)＝a(fp)+ηw(fp)fp为可行的模块和tsv布图解，η为权重系数；a(
·
)为面积函数，w(
·
)为线长函数；其中面积函数a(
·
)：a＝e
w
+e
h
·
λ+c1·
max{e
w
,e
h
·
λ}+c2·
max{w,h
·
λ}w和h分别表示当前模块和tsv布图的宽度和高度，e
w
＝max{w-w0,0}，e
h
＝max{h-h0,0}，w0、h0为固定轮廓的宽和高，e
w
，e
h
为考虑固定轮廓约束，宽度和高度超出固定轮廓的部分，λ为固定轮廓宽度和长度的比值，c1、c2为常量，c1＝1，w0、h0计算公式如下：a表示所有模块和tsv的总面积，k表示层数，γ表示空白面积分数，λ表示固定轮廓的长宽比；w(
·
)为线长函数，运用半周长模型来评估模块和tsv布图的线长，线长的大小为所有子网线长的总和：m表示网的总数，分别表示子网n
i
中这层的模块、tsv和上一层tsv在该层映射位置的最大x坐标、最小x坐标、最大y坐标、最小y坐标；
s43，输出最终布图解，包括各层模块和tsv的序列对、模块的朝向序列以及模块和tsv所在的层次和坐标。7.一种基于强化学习的三维固定轮廓集成电路布图规划系统，用于执行权利要求1-6任一项所述的方法，其特征在于，所述的系统包括如下模块：数据预处理模块：获取模块及网表信息，计算模块面积；层分配模块：根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的tsv数量；布图解输出模块：采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过mdp表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；tsv布图模块：在模块布图的基础上进行tsv布图，输出最终布图解。

技术总结
本发明公开了一种基于强化学习的三维固定轮廓集成电路布图规划方法及系统，方法包括如下步骤：S1，获取模块及网表信息，计算模块面积；S2，根据模块面积及网表信息，对电路进行划分，并对划分结果进行优化，将模块分配到不同层并确定每一层的TSV数量；S3，采用序列对作为布图规划的表示方法，将模块三维布图规划的局部搜索过程通过MDP表示，构建基于强化学习的模块布图规划模型，输出模块的布图解；S4，在模块布图的基础上进行TSV布图，输出最终布图解。本发明能有效地完成三维集成电路布图规划，并获得线长更优的方案。获得线长更优的方案。获得线长更优的方案。


技术研发人员：张忠良 俞宙 姬朋立 雒兴刚 阮渊鹏
受保护的技术使用者：杭州电子科技大学
技术研发日：2023.07.18
技术公布日：2023/10/19