一种基于神经网络和序列对的布图规划面积最优方法

allin2023-03-24  64



1.本发明涉及数字集成电路电子设计自动化领域,具体涉及一种基于神经网络和序列对的布图规划面积最优方法。


背景技术:

2.在摩尔定律的激励下,集成电路进入了超大规模时代。单芯片上集成的晶体管数量已经达到百亿级,工程师手工设计电路已经无法满足设计指标的需要。在这种情况下,出现了电子设计自动化(eda)技术,指利用计算机辅助设计软件,来完成超大规模集成电路(vlsi)芯片的功能设计、仿真、综合、验证、物理设计等流程的设计方式。其中,物理设计是将网表的电路信息转化为物理几何表示的过程,此过程最后得到的版图gdsii文件将用于芯片生产制造环节。布图规划(floorplan)是物理设计中的核心步骤,目的是确保每个模块被分配一个形状或合适的位置以及每个与外部有连接的引脚被分配合理的位置。此外,布图规划一方面将影响芯片的性能、功耗、面积、线长等指标,进而影响时序、拥塞等设计目标。另一方面影响后续布局、布线阶段的进行,一个布图规划不良的设计,很难在后续阶段满足设计需求。由此,布图规划是集成电路物理设计流程中非常重要的环节。
3.随着5g和人工智能时代的到来以及对算力的需求,单颗芯片所包含的功能越来越来多,这样就导致单颗芯片面积增大。在物理设计中,芯片的最终面积是在布图规划阶段确定,因而,面积成为了布图规划的评价指标之一。在工艺节点的持续降低下,出现了一些新的评价指标,例如可布线性、时序驱动等等,但是最主要的评价指标是面积。
4.虽然布图规划已经被证明是一个np-hard问题,但在研究人员多年的努力下,涌现出大量解决布图规划的优秀方法。尽管这些方法各有优缺点,但是根据方法切入点的不同,大致可以分为四类:基于划分的方法(dunlop a e,kernighan b w.a procedure for placement of standard cell vlsi circuits[j].ieee transactions on computer-aided design,1985,4(1):92-98.)、基于模拟退火等启发式方法(tang x,wong d f.fast-sp:a fast algorithm for block placement based on sequence pair[c]//proceedings of the 2001 asia and south pacific design automation conference.2001:521-526.)、基于力导向等解析式方法(p.spindler,u.schlichtmann and f.m.johannes,"kraftwerk2—a fast force-directed quadratic placement approach using an accurate net model,"in ieee transactions on computer-aided design of integrated circuits and systems,vol.27,no.8,pp.1398-1411,aug.2008,doi:10.1109/tcad.2008.925783.)以及基于人工智能的方法(mirhoseini a,goldie a,yazgan m,et al.a graph placement methodology for fast chip design[j].nature,2021,594(7862):207-212.),其中人工智能方法主要是传统机器学习和强化学习这两类。
[0005]
上述方法中,第一种方法是分而治之的思想,即将顶层设计划分为许多规模更小的设计,直到问题能够被解决为止,这种方式会损失解决方案的质量同时缺乏全局观;第二种方法通过在设计空间中寻找最优解,容易陷入局部最优解的麻烦,并且存在收敛速度慢
的问题;第三种方式使用数学的形式求解模块坐标约束构成的表达式,此种方法能得到精确解,其复杂度随着问题规模增大而增大,而且受限于方程表达式和所设约束条件;上述三种方式都不能从上一次迭代的经验中学习。第四种方式利用人工智能在联合优化方面优势提高解的质量,是目前布图规划领域研究的热点,但是其存在每个步骤搜索空间大、训练模型时硬件要求高、训练数据集不透明的问题。如果能够降低每个步骤搜索空间的复杂度同时解决训练数据的问题,那人工智能方式将为布图规划带来新的发展方向。


技术实现要素:

[0006]
本发明的目的是提供一种基于神经网络和序列对的布图规划面积最优方法,利用开源工具生成机器学习所需的数据库,配合基于表示方法的序列对布图表示方式,通过搭建单步搜索空间较小的神经网络模型,使其能够快速有效的找到布图规划面积最优解。
[0007]
为了实现上述任务,本发明采用以下技术方案:
[0008]
一种基于神经网络和序列对的布图规划面积最优方法,包括:
[0009]
构建电路模块数量为n的数字集成电路布图规划数据库,该数据库中的数据用于完整表示一个布图规划,由四个数组组成:其中一个数组w存储n个模块的宽度、一个数组h存储n个模块的高度,另外两个数组splus和smin代表最优面积序列对;
[0010]
将布图规划中序列对表示的布图转化为机器学习中的分类问题,包括:从数字集成电路布图规划数据库里抽取一组数据[w,h,splus,smin],将序列对splus和smin分别存储在s1和s2中;计算出数组s1和数组s2中n个元素所构建的n个标签值index,同时创建正序列对数组p和负序列对数组m用于储存已经确定位置的元素,未确定位置的元素用-1代替;然后,输入特征x:{w,h,p,m}和标签index组成的训练数据对被写入新的数据库,此数据库将用于神经网络模型训练;
[0011]
采用多层感知机搭建神经网络模型,整个模型从输入到输出依次为展开层、隐藏层和输出层,模型的输入特征是一个四维元素{w,h,p,m};将所述新数据库中的训练数据输入到模型得到预测结果,根据预测结果与标签之间的差距计算损失量,使用反向传播方法更新模型参数,进而缩小预测结果与标签之间的差距,最终得到一个泛化性最优的模型作为训练好的模型;
[0012]
利用训练好的模型对数组s1和数组s2中的元素进行预测,直至s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对s1、s2为这n个模块布图规划面积最优的解。
[0013]
进一步地,所述构建电路模块数量为n的数字集成电路布图规划数据库,包括:
[0014]
根据实际的应用场景选择模块的数量n和模块尺寸的大小范围range;
[0015]
根据所述模块的数量n和模块尺寸大小范围range,利用随机函数随机生成各模块的具体尺寸,然后将各模块的宽度和高度分别保存进宽度数组w和高度数组h;
[0016]
使用两个大小为n的数组splus、smin分别表示n个模块序列对的正序列s1、负序列s2,数组splus和smin的初始值为b0,b1,b2,...,b
n-1
,其中bi(i=0,1,

n-1)表示模块名;接着分别无序打乱数组splus、smin,最后将打乱得到的数组splus和smin作为n个模块布图规划初始解;
[0017]
利用模拟退火方法搜索面积最优的序列对,并将各模块宽度数组w、高度数组h、布
图规划面积最优面积序列对splus、smin保存到数字集成电路布图规划数据库中。
[0018]
进一步地,所述利用模拟退火方法搜索面积最优的序列对,包括:
[0019]
模拟退火方法的输入参数为最高温度t、最低温度t、冷却因子alpha、各模块宽度数组w、各模块高度数组h、以及序列对数组splus和smin;模拟退火通过在数组splus和smin上扰动的方式寻找面积更小的解,扰动后的序列对数组为splus_disturb、smin_disturb,其中扰动方式为:随机交换数组splus、smin中两个相同元素的位置、随机交换数组splus中两个元素、随机交换数组smin中两个元素以及随机打乱数组splus、smin;
[0020]
在扰动完成之后,计算扰动后的数组splus_disturb、smin_disturb所代表的序列对的面积,如果该面积比数组splus、smin所代表的序列对的面积小,则将数组splus_disturb、smin_disturb分别赋予数组splus、smin,以达到将数组splus_disturb、smin_disturb作为最优解的目的;如果该面积比数组splus、smin所代表的面积大,则以概率exp(-delta/t)接受这个差解,否则丢弃;其中delta是两个面积之差;当温度低于最低温度t结束模拟退火方法,最终将数组splus、smin作为n个模块最优面积序列对。
[0021]
进一步地,所述将布图规划中序列对表示的布图转化为机器学习中的分类问题,具体包括:
[0022]
2.1从数字集成电路布图规划数据库中导出数据,包括存储有n个模块宽度的数组w、存储有n个模块高度的数组h,以及最优面积序列对splus和smin,将序列对splus和smin分别存储在s1和s2中;
[0023]
2.2对于n个模块,模块名分别为b0,b1,b2,...,b
n-1
,选择的编码方式为bi=i,则编码后各模块为:0、1、2、...、n-2、n-1;随后创建成字典dicts,字典的关键字为模块名,值为编码编号,这个字典在创建分类标签时,能够将模块名映射为对应的编号,即dicts(bi)=i;
[0024]
2.3构建神经网络模型的输入特征四元组{w,h,p,m},其中w是n个模块的宽度数组,h是n个模块的高度数组,p、m分别是序列对中正序列、负序列已经确定元素的数组,p和m中如果某个元素还没确定则用-1代替;
[0025]
初始化数组p和m中的元素均为-1,设i=0,计算标签:index=n*dicts(s1[i])+dicts(s2[i]);
[0026]
2.4如果i等于0,则数组p和数组m的所有元素都为-1;如果i大于0,则p[i-1]=dicts(s1[i-1]),m[i-1]=dicts(s2[i-1]);再结合数组w和数组h,创建输入特征x为:{w,h,p,m};
[0027]
2.5将输入特征x和标签index组成数据对,将数据对保存到data中;如果i《n,则i++,重复步骤2.3和步骤2.4;在新一轮迭代中,重新计算标签index的值,接着根据i的值判断数组p和数组m中那些元素需要赋值,得到输入特征x,最后,把数据对保存到data中用于神经网络模型的训练。
[0028]
进一步地,所述神经网络模型的训练过程为:
[0029]
首先,特征x={w,h,p,m}输入到模型中,展开层将其从四维降至一维数组;其次,隐藏层和输出层开始学习输入特征和输出特征之间的关联;接着,利用softmax函数选择输出层上概率最大神经元的索引号作为分类的结果然后,使用交叉熵损失函数计算分类结果和标签index之间的差距,结合差距和反向传播方法进行模型参数的更新,参
数包括神经元的权重和偏置;最后得到一个训练完成的模型。
[0030]
进一步地,利用训练好的模型对数组s1和数组s2中的元素进行预测,包括:
[0031]
(1)获取n个模块的基本特征,然后创建数组w和数组h分别保存n个模块的宽度和高度,同时创建两个包含n个元素且初始值为-1的数组s1和s2;
[0032]
(2)第i次把{w,h,s1,s2}输入到模型中,得到输出结果y;计算s[i]的值,即s1[i]=y/n,s2[i]=y%n;
[0033]
(3)如果i不等于n,i自增1随即重复步骤(2);否则跳到步骤(4);
[0034]
(4)当s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对为这n个模块布图规划面积最优的解。
[0035]
与现有技术相比,本发明具有以下技术特点:
[0036]
1.本发明针对集成电路电子设计自动化中布图规划领域,提出一种基于神经网络和序列对的布图规划面积最优的方法,本方法能够快速有效的找到最佳方案。
[0037]
2.本发明利用开源工具生成布图规划最优解,进而形成数据库,解决机器学习数据量不够的问题;同时将模块序列对转化为数值标签,布图规划转化为机器学习中的分类问题,通过实验的方式验证了方法的可行性以及有效性。
附图说明
[0038]
图1为利用开源工具生成数据集的过程;
[0039]
图2为序列对代表布图规划的示例;
[0040]
图3为将布图规划转为机器学习中分类问题的示意图;
[0041]
图4为神经网络模型训练的示意图;
[0042]
图5为新数据预测布图规划最优解过程示意图;
[0043]
图6为模拟退火的运行结果示意图;
[0044]
图7为本发明方法的运行结果示意图;
[0045]
图8为本发明方法的整体设计流程图。
具体实施方式
[0046]
针对人工智能方法解决布图规划存在训练数据集不透明的问题,这是一个目前工业界和学术界普遍存在的现象。本发明专利将使用开源工具生成数据集,并且达到数据集可重现的效果。另外,经过几十年的发展,基于表示的方法是布图规划中的一种布图表示,其主要有波兰表达式、b*-tree、o*-tree、序列对等等。序列对的表示比较简洁,因此成为本发明的布图表示形式。
[0047]
参见附图,本发明的一种基于神经网络和序列对的布图规划面积最优方法,包括以下步骤:
[0048]
步骤1,构建电路模块数量为n的数字集成电路布图规划数据库,该数据库中的每一条数据用于完整表示一个布图规划,由四个数组组成;其中一个数组w存储n个模块的宽度、一个数组h存储n个模块的高度,另外两个数组splus和smin代表最优面积序列对;这个数据库将用于训练数据的生成,其流程如图1所示。
[0049]
1.1根据实际的应用场景选择模块的数量n和模块尺寸的大小范围range,例如
mcnc benchmark中的apte电路的模块数量范围为9块,则可以将n设置为9,range可以设为0到apte模块宽度或者高度最大值,以此提高数据库覆盖率;range只会规定这n个模块最终的尺寸范围。
[0050]
1.2根据1.1所输入的模块数量n和模块尺寸大小范围range参数,利用python内嵌的随机数函数randint随机生成各模块具体尺寸,具体尺寸的数值一定小于等于range;将各模块的宽度和高度分别保存进宽度数组w和高度数组h。
[0051]
1.3首先,介绍序列对中是如何表示两个模块的关系。
[0052]
序列对由两个序列s1(也称为正序列)、s2(也称为负序列)构成,假设有模块a和模块b,如果在序列s1中《...a,...b,...》,在序列s2中《...a,...b,...》,则模块a在模块b的左边;如果在序列s1中《...a,...b,...》,在序列s2中《...b,...a,...》,则模块a在模块b的上边。
[0053]
图2是一个序列对所代表的布图规划例子,其中s1:《acdbe》,s2:《cdaeb》。为此,使用两个大小为n的数组splus、smin分别表示n个模块序列对的正序列s1、负序列s2,数组splus和smin的初始值为b0,b1,b2,...,b
n-1
,其中bi(i=0,1,

n-1)表示模块名,在实际应用中模块名可以是存储块的名字如mem,也可以是ip模块的某个实例如io;接着利用python内嵌random库中的shuffle函数分别无序打乱数组splus、smin,最后将打乱得到的数组splus和smin作为n个模块布图规划初始解。
[0054]
1.4利用模拟退火方法搜索面积最优的序列对。
[0055]
模拟退火方法的输入参数为最高温度t、最低温度t、冷却因子alpha、步骤1.2中的各模块宽度数组w、各模块高度数组h、以及步骤1.3中的序列对数组splus和smin。模拟退火通过在数组splus和smin上扰动的方式寻找面积更小的解,扰动后的序列对数组为splus_disturb、smin_disturb,其中扰动方式为:随机交换数组splus、smin中两个相同元素的位置(即随机交换两个模块)、随机交换数组splus中两个元素(即交换上下两个模块)、随机交换数组smin中两个元素(即交换左右两个模块)以及随机打乱数组splus、smin(即重新选择一个布图规划)。在扰动完成之后,计算扰动后的数组splus_disturb、smin_disturb所代表的序列对的面积,如果该面积比数组splus、smin所代表的序列对的面积小,则将数组splus_disturb、smin_disturb分别赋予数组splus、smin,以达到将数组splus_disturb、smin_disturb作为最优解的目的;如果该面积比数组splus、smin所代表的面积大,则以概率(exp(-delta/t),其中delta是两个面积之差)接受这个差解,否则丢弃。通过冷却温度、扰动序列对、计算面积等等步骤,直到温度低于最低温度t才结束模拟退火方法,最终将数组splus、smin作为n个模块最优面积序列对。
[0056]
1.5将各模块宽度数组w、高度数组h、布图规划面积最优面积序列对splus、smin保存到数字集成电路布图规划数据库中,以便后续机器学习使用。此数据库中的数据包含了n个模块面积最优的序列对,因此,用这些面积最优的数据训练出来的模型,其预测结果理论上也是面积最优的。
[0057]
由于机器学习训练模型时需要大量原始数据,因此将重复执行步骤1.2至步骤1.5所有步骤以获得多份数据。例如需要原始数据为10,000份,则需要重复执行上述步骤10,000次,其中步骤1.5将每组数据保存至数据库,故程序执行结束时,数据库将有10,000组数据。
[0058]
步骤2,将布图规划中序列对表示的布图转化为机器学习中的分类问题。
[0059]
从步骤1中得到的数据库里抽取一组数据,此组数据包含四个数组w、h、splus和smin,将序列对splus和smin分别存储在s1和s2中;计算出数组s1和数组s2中n个元素所构建的n个标签值index,同时创建正序列对数组p和负序列对数组m用于储存已经确定位置的元素,未确定位置的元素用-1代替。然后,输入特征x:{w,h,p,m}和标签index组成的数据对被写入新的数据库,此数据库将用于模型训练。此步骤中,一组数据被重构成n份数据,用于训练模型具备预测序列对中n个元素的能力。值得注意的是,标签index的取值范围为:0~(n
2-1),且标签index是整数,所以此问题转化为输入特征为x,输出类别数为n2的机器学习分类问题。
[0060]
将序列对转化为机器学习所需数据的过程如图3所示。
[0061]
2.1从步骤1构建的数据库中导出数据,包括存储有n个模块宽度的数组w、存储有n个模块高度的数组h,以及最优面积序列对splus和smin,将序列对splus和smin分别存储在s1和s2中;
[0062]
2.2对每个模块进行编码。
[0063]
对于n个模块,模块名分别为b0,b1,b2,...,b
n-1
,选择的编码方式为bi=i,则编码后各模块为:0、1、2、...、n-2、n-1;随后创建成字典dicts,字典的关键字为模块名,值为编码编号,这个字典在创建分类标签时,能够将模块名映射为对应的编号,即dicts(bi)=i。值得注意的是,模块编码前构成的序列对和编码后构成的序列对表示同一个布图规划。
[0064]
2.3创建分类的标签。
[0065]
在本方案中神经网络模型的输入特征由四元组构成,即{w,h,p,m},其中w是n个模块的宽度数组,h是n个模块的高度数组,p是序列对中正序列已经确定元素的数组,如果某个元素还没确定则用-1代替,m是序列对中负序列已经确定元素的数组,如果某个元素还没确定则用-1代替。例如,不妨设模块数量为5,w=[4,4,6,8,8],h=[6,6,6,5,5],s1=[b3,b1,b2,b0,b4],s2=[b0,b2,b1,b4,b3],此时数组p和m有两个元素已经确定,则p=[3,1,-1,-1,-1],m=[0,2,-1,-1,-1]。
[0066]
首先初始化数组p和m中的元素均为-1,-1代表序列中这个位置还没确定取值。设i=0,则使用标签生成公式计算标签:index=n*dicts(s1[i])+dicts(s2[i])。例如:s1[i]=b2,s2[i]=b1,n=5,则index=5*2+1=11。此步中,s1,s2中各个元素的编号是唯一的,所以得到的index也是唯一的。因此,在模型中用index值作为分类的标签不存在二义性的问题。由于index的取值范围为:0~(n
2-1),每一步问题的规模变为n2,进而降低了搜索空间的复杂性。
[0067]
2.4合并数组成机器学习输入特征。
[0068]
如果i等于0,则数组p和数组m的所有元素都为-1;根据此时p(所有元素为-1)、m(所有元素为-1)、w、h来预测p[0]和m[0]的值。
[0069]
如果i大于0,则p[i-1]=dicts(s1[i-1]),m[i-1]=dicts(s2[i-1]),代表正序列中i-1这个位置的元素确定为dicts(s1[i-1])、负序列中i-1这个位置的元素确定为dicts(s2[i-1])。再结合步骤2中的数组w和数组h,创建输入特征x为:{w,h,p,m}。当i=1时,此时p[0]和m[0]是有值的分别为dicts(s1[0]),dicts(s2[0]),此时模型会根据p(p[0]有值,其他为-1)、m(m[0]有值,其他为-1)、w、h来预测p[1]和m[1]的值,以此类推。
[0070]
例如:如果i=0,则{w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1]];如果i=1,则{w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,-1,-1,-1,-1],[0,-1,-1,-1,-1]];如果i=2,则{w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,1,-1,-1,-1],[0,2,-1,-1,-1]]。
[0071]
2.5将输入特征x和标签index组成数据对,将数据对保存到data中。如果i《n,则i++,重复步骤2.3和步骤2.4。在新一轮迭代中,重新计算标签index的值,即index=n*dicts(s1[i])+dicts(s2[i])。接着根据i的值判断数组p和数组m中那些元素需要赋值,得到输入特征x,最后,把数据对保存到data中。
[0072]
2.6上述循环终止时,data中保存了n份数据,这n份数据用于训练模型具备预测序列对中n个元素的能力。最后,保存data中的所有数据到新数据库中,下次训练直接读取这个文件即可,为机器学习训练节省时间。
[0073]
步骤3,在完成上述两点之后,即可进行神经网络模型的搭建。
[0074]
本方案采用多层感知机(multi-layer perception,mlp)搭建神经网络模型,模型的输入特征是一个四维元素{w,h,p,m},输出神经元个数为n2(n为模块数量),隐藏层层数为5层,另外还有一层展开层,各层之间的连接方式为全连接。整个模型从输入到输出经过的层依次为展开层、隐藏层和输出层;其中,展开层将输入四维元素展开成一维数组;隐藏层的大小分别为(4*n,128)、(128,256)、(256,512),(512,256)和(256,128),其作用是拟合输入特征与输出特征之间的关系;输出层的大小为(128,n2),其作用是约束最终分类的类数。其他的超参数选择如下:
[0075]
表1 神经网络模型参数统计表
[0076][0077]
将所述新数据库中的训练数据输入到模型得到预测结果,根据预测结果与标签之间的差距计算损失量,使用反向传播方法更新模型参数,进而缩小预测结果与标签之间的差距,最终得到一个泛化性最优的模型,如图4所示。
[0078]
模型的训练过程为:首先,特征x={w,h,p,m}输入到模型中,展开层将其从四维降至一维数组。其次,隐藏层和输出层开始学习输入特征和输出特征之间的关联。接着,利用pytorch库中softmax函数选择输出层上概率最大神经元的索引号作为分类的结果然后,使用交叉熵损失函数计算分类结果和标签index之间的差距,结合差距和反向传播方法进行模型参数的更新,参数包括神经元的权重和偏置。最后得到一个训练好的模
型用于序列对的预测。
[0079]
例如:当输入特征x={w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1]],index=15时,要训练模型有能够预测p[0]和m[0]的能力,如果此时则训练没有损失;如果此时不等于15,则使用交叉熵函数计算损失。当输入特征x={w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,-1,-1,-1,-1],[0,-1,-1,-1,-1]],index=7时,要训练模型有能够预测p[1]和m[1]的能力;当输入特征x={w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,1,-1,-1,-1],[0,2,-1,-1,-1]],index=11时,要训练模型有能够预测p[2]和m[2]的能力;当输入特征x={w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,1,2,-1,-1],[0,2,1,-1,-1]],index=4时,要训练模型有能够预测p[3]和m[3]的能力;当输入特征x={w,h,p,m}=[[4,4,6,8,8],[6,6,6,5,5],[3,1,2,0,-1],[0,2,1,4,-1]],index=23时,要训练模型有能够预测p[4]和m[4]的能力;由于在整个训练过程中使用的是同一个模型,所以这个模型具备预测完成序列对的能力。
[0080]
步骤4,利用训练好的模型对数组s1和数组s2中的元素进行预测,直至s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对s1、s2为这n个模块布图规划面积最优的解。
[0081]
在实际应用中,对于包含n个模块的布图规划问题面积最优求解,其处理过程,如图5所示。
[0082]
(1)获取n个模块的基本特征(宽度和高度),然后创建数组w和数组h分别保存n个模块的宽度和高度,同时创建两个包含n个元素且初始值为-1的数组s1和s2。
[0083]
(2)第i(i初始为0)次把{w,h,s1,s2}输入到模型中,得到输出结果y。根据标签生成公式反推s[i]的值,即s1[i]=y/n,s2[i]=y%n。例如:当i=0时,w=[8,4,4,4,4],h=[4,3,5,5,6],s1=[-1,-1,-1,-1,-1],s2=[-1,-1,-1,-1,-1],此时是为了预测s1[0]和s2[0]的值,假设模型输出结果y=2,则s1[0]=2/5=0,s2[0]=2%5=2。当i=1时,输入模型的特征{w,h,s1,s2}=[[8,4,4,4,4],[4,3,5,5,6],[0,-1,-1,-1,-1],[2,-1,-1,-1,-1]],让模型预测s1[1]和s2[1]的值。此过程用于构造步骤2中2.6提及的n份数据。
[0084]
(3)如果i不等于n,i自增一随即重复步骤(2);否则跳到步骤(4)。
[0085]
(4)此时s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对为这n个模块布图规划面积最优的解。
[0086]
本发明所使用的建模方式将每一步的时间复杂度变为n2,运行速度变快。每一步都是从n2个类别中选择一个,与其他方式方法复杂度相比有了数量级的提高。
[0087]
在后续的布图规划设计中,对于基于表示的方法表示布图,可以使用o*-tree或者波兰表达式代替本方法的序列对;对于利用开源工具生成数据集中,针对启发式方法模拟退火,可以采用粒子群优化方法实现同样的效果,因此,粒子群优化方法也是本方法中的一种替代方案;而对于神经网络搭建这部分,可以使用卷积神经网络(convolutional neural networks,cnn)或者强化学习(reinforcement learning,rl)代替,即使前人已使用强化学习解决布图规划,但是结合本方法中的建模方式,其效果也会优于前人单独使用强化学习的方法。
[0088]
本方法已经在开源且具有行业权威性的mcnc benchmark上进行完成验证。apte为mcnc benchmark中的一个benchmark,其包含9个模块,模块尺寸在286-3186微米之间,每个
模块是一个矩形。验证方式如下:
[0089]
将apte数据集中的模块尺寸w,h和两个大小为9、元素值为-1的数组p和m构成的矩阵输入到模型,得到模型的输出值y。把输出值填补到数组p和m,具体做法是:假设i=0,p[i]=y/9,m[i]=y%9,i++。然后将{w,h,p,m}带入模型得到新的值y,按照上述的方式将y填入p和m,重复上述步骤直到p,m中没有元素值为-1,即i==9。
[0090]
为了比较本方法的优越,采用模拟退火进行同样实验,模拟退火的输入参数如最高温度、最低温度、冷却因子,与步骤1的相同。最终的实验结果如图6,7所示,本方法得到的面积是4.75x107,运行时间2.2s,而模拟退火得到的面积是4.82x107,运行时间11.9s,实验表明,本方法能够有效快速的找到布图规划面积最优解。
[0091]
以上实施例仅用以说明本技术的技术方案,而非对其限制;尽管参照前述实施例对本技术进行了详细的说明,本领域的普通技术人员应当理解:其依然可以对前述各实施例所记载的技术方案进行修改,或者对其中部分技术特征进行等同替换;而这些修改或者替换,并不使相应技术方案的本质脱离本技术各实施例技术方案的精神和范围,均应包含在本技术的保护范围之内。

技术特征:
1.一种基于神经网络和序列对的布图规划面积最优方法,其特征在于,包括:构建电路模块数量为n的数字集成电路布图规划数据库,该数据库中的数据用于完整表示一个布图规划,由四个数组组成:其中一个数组w存储n个模块的宽度、一个数组h存储n个模块的高度,另外两个数组splus和smin代表最优面积序列对;将布图规划中序列对表示的布图转化为机器学习中的分类问题,包括:从数字集成电路布图规划数据库里抽取一组数据[w,h,splus,smin],将序列对splus和smin分别存储在s1和s2中;计算出数组s1和数组s2中n个元素所构建的n个标签值index,同时创建正序列对数组p和负序列对数组m用于储存已经确定位置的元素,未确定位置的元素用-1代替;然后,输入特征x:{w,h,p,m}和标签index组成的训练数据对被写入新的数据库,此数据库将用于神经网络模型训练;采用多层感知机搭建神经网络模型,整个模型从输入到输出依次为展开层、隐藏层和输出层,模型的输入特征是一个四维元素{w,h,p,m};将所述新数据库中的训练数据输入到模型得到预测结果,根据预测结果与标签之间的差距计算损失量,使用反向传播方法更新模型参数,进而缩小预测结果与标签之间的差距,最终得到一个泛化性最优的模型作为训练好的模型;利用训练好的模型对数组s1和数组s2中的元素进行预测,直至s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对s1、s2为这n个模块布图规划面积最优的解。2.根据权利要求1所述的基于神经网络和序列对的布图规划面积最优方法,其特征在于,所述构建电路模块数量为n的数字集成电路布图规划数据库,包括:根据实际的应用场景选择模块的数量n和模块尺寸的大小范围range;根据所述模块的数量n和模块尺寸大小范围range,利用随机函数随机生成各模块的具体尺寸,然后将各模块的宽度和高度分别保存进宽度数组w和高度数组h;使用两个大小为n的数组splus、smin分别表示n个模块序列对的正序列s1、负序列s2,数组splus和smin的初始值为b0,b1,b2,...,b
n-1
,其中b
i
(i=0,1,

n-1)表示模块名;接着分别无序打乱数组splus、smin,最后将打乱得到的数组splus和smin作为n个模块布图规划初始解;利用模拟退火方法搜索面积最优的序列对,并将各模块宽度数组w、高度数组h、布图规划面积最优面积序列对splus、smin保存到数字集成电路布图规划数据库中。3.根据权利要求2所述的基于神经网络和序列对的布图规划面积最优方法,其特征在于,所述利用模拟退火方法搜索面积最优的序列对,包括:模拟退火方法的输入参数为最高温度t、最低温度t、冷却因子alpha、各模块宽度数组w、各模块高度数组h、以及序列对数组splus和smin;模拟退火通过在数组splus和smin上扰动的方式寻找面积更小的解,扰动后的序列对数组为splus_disturb、smin_disturb,其中扰动方式为:随机交换数组splus、smin中两个相同元素的位置、随机交换数组splus中两个元素、随机交换数组smin中两个元素以及随机打乱数组splus、smin;在扰动完成之后,计算扰动后的数组splus_disturb、smin_disturb所代表的序列对的面积,如果该面积比数组splus、smin所代表的序列对的面积小,则将数组splus_disturb、smin_disturb分别赋予数组splus、smin,以达到将数组splus_disturb、smin_disturb作为
最优解的目的;如果该面积比数组splus、smin所代表的面积大,则以概率exp(-delta/t)接受这个差解,否则丢弃;其中delta是两个面积之差;当温度低于最低温度t结束模拟退火方法,最终将数组splus、smin作为n个模块最优面积序列对。4.根据权利要求1所述的基于神经网络和序列对的布图规划面积最优方法,其特征在于,所述将布图规划中序列对表示的布图转化为机器学习中的分类问题,具体包括:2.1从数字集成电路布图规划数据库中导出数据,包括存储有n个模块宽度的数组w、存储有n个模块高度的数组h,以及最优面积序列对splus和smin,将序列对splus和smin分别存储在s1和s2中;2.2对于n个模块,模块名分别为b0,b1,b2,...,b
n-1
,选择的编码方式为b
i
=i,则编码后各模块为:0、1、2、...、n-2、n-1;随后创建成字典dicts,字典的关键字为模块名,值为编码编号,这个字典在创建分类标签时,能够将模块名映射为对应的编号,即dicts(b
i
)=i;2.3构建神经网络模型的输入特征四元组{w,h,p,m},其中w是n个模块的宽度数组,h是n个模块的高度数组,p、m分别是序列对中正序列、负序列已经确定元素的数组,p和m中如果某个元素还没确定则用-1代替;初始化数组p和m中的元素均为-1,设i=0,计算标签:index=n*dicts(s1[i])+dicts(s2[i]);2.4如果i等于0,则数组p和数组m的所有元素都为-1;如果i大于0,则p[i-1]=dicts(s1[i-1]),m[i-1]=dicts(s2[i-1]);再结合数组w和数组h,创建输入特征x为:{w,h,p,m};2.5将输入特征x和标签index组成数据对,将数据对保存到data中;如果i<n,则i++,重复步骤2.3和步骤2.4;在新一轮迭代中,重新计算标签index的值,接着根据i的值判断数组p和数组m中那些元素需要赋值,得到输入特征x,最后,把数据对保存到data中用于神经网络模型的训练。5.根据权利要求1所述的基于神经网络和序列对的布图规划面积最优方法,其特征在于,所述神经网络模型的训练过程为:首先,特征x={w,h,p,m}输入到模型中,展开层将其从四维降至一维数组;其次,隐藏层和输出层开始学习输入特征和输出特征之间的关联;接着,利用softmax函数选择输出层上概率最大神经元的索引号作为分类的结果然后,使用交叉熵损失函数计算分类结果和标签index之间的差距,结合差距和反向传播方法进行模型参数的更新,参数包括神经元的权重和偏置;最后得到一个训练完成的模型。6.根据权利要求1所述的基于神经网络和序列对的布图规划面积最优方法,其特征在于,利用训练好的模型对数组s1和数组s2中的元素进行预测,包括:(1)获取n个模块的基本特征,然后创建数组w和数组h分别保存n个模块的宽度和高度,同时创建两个包含n个元素且初始值为-1的数组s1和s2;(2)第i次把{w,h,s1,s2}输入到模型中,得到输出结果y;计算s[i]的值,即s1[i]=y/n,s2[i]=y%n;(3)如果i不等于n,i自增1随即重复步骤(2);否则跳到步骤(4);(4)当s1和s2数组已经没有-1的元素,即完成序列对所有元素的位置预测,此序列对为这n个模块布图规划面积最优的解。

技术总结
本发明公开了一种基于神经网络和序列对的布图规划面积最优方法,该方法针对集成电路电子设计自动化中布图规划问题,首先利用布图规划最优解构建布图规划数据库,解决机器学习数据量不够的问题;同时将将布图规划中序列对表示的布图转化为机器学习中的分类问题,最后通过多层感知机搭建神经网络模型并进行训练,得到训练好的模型用于预测布图规划面积最优的解;本方法能够快速有效的找到布图规划面积最优方案。最优方案。最优方案。


技术研发人员:黄益豪 蔡述庭 邢延 熊晓明
受保护的技术使用者:广东工业大学
技术研发日:2022.03.30
技术公布日:2022/7/5
转载请注明原文地址: https://www.8miu.com/read-7610.html

最新回复(0)