基于最优适应启发式序列与组织进化的集成电路布图方法

摘要

本发明公开一直基于最优适应启发式序列与组织进化的集成电路布图方法，属于物理设计布图规划技术领域。本发明将最优适应启发式序列作为编码和解码，与组织进化算法结合，用于求解超大规模集成电路布图方法，其特征在于：首先初始化每个个体，然后采用最优适应启发式序列对每个个体进行编码和解码，最后用设计的分裂算子、吞并算子、培训算子对组织进行优化，验证结果表明，本发明在评定求解超大规模集成电路布图规划问题方法效用的一个重要方面：求最优的芯片的面积利用率，有优势，是一种有效的求解超大规模集成电路布图规划问题的方法，还能扩展到求解多目标的超大规模集成电路布图规划问题。

主权项

一种基于最优适应启发式序列与组织进化的集成电路布图方法，其特征是：具体步骤如下：步骤101：开始基于最优适应启发式序列与组织进化的集成电路布图方法；步骤102：参数设定：最大进化代数T，初始个体数num，合法组织所允许的最大个体数num_max，模块的长宽比的变化范围[min h_w，max h_w]，最优个体的适应度COST，t为大于或等于0的整数，表示进化到第t代；步骤103：初始化每个个体，更新最优值COST，令t＝0，采用随机生成的方法产生模块的放置顺序，模块的长宽比序列，芯片的初始化宽度，如果存在硬直线边界模块，则循环调用预处理算法对硬直线边界模块进行预处理；步骤104：循环调用基于最优适应启发式序列的算法对每个模块个体进行编码和解码；步骤105：使每个个体成为一个组织，将分裂算子作用在组织上，分裂算子根据下面条件：(org_p.num＞num_max)or{(1＜org_p.num≤num_max)and(U(0,1)＜org_p.num/N_member)}把一个组织orgp分裂成两个非空组织，其中orgp.num是orgp中的个体数目，num_max是一个合法组织中允许包含个体数目的最大值，U(0,1)是0到1之间的一个任意值，N_member是所有组织中所有个体的总数，每个组织中的个体按适应度从大到小进行排列；步骤106：将吞并算子作用在两个组织上，随机选择两个组织org_p1和org_p2，如果COST(org_p1)＜COST(org_p2)，则org_p1吞并org_p2，否则org_p2吞并org_p1，其中COST(org_p1)和COST(org_p2)为org_p1和org_p2的适应度值，对两个组织采用吞并算子的具体规则如下：假设组织org_p1吞并org_p2成一个新的组织org_c，这个新的组织由三部分组成：1)org_p1中的所有个体；2)由org_p1和org_p2根据下面公式生成org_p2.num/2个新的个体，member_new1：令0≤i≤org_p2.num/2,0≤j≤n，member_new1[i].b＝org_p2.member[0].b${\mathrm{member}}_{new1}\left[i\right].p\left[j\right]=\left\{\begin{array}{cc}{\mathrm{org}}_{p2}.member\left[0\right].p\left[j\right]& if({\mathrm{org}}_{p1}.member[0].p[j]=\\ & {\mathrm{org}}_{p2}.member\left[i\right].p\left[j\right])\\ & and\left(U\right(0,1)=0)\\ {\mathrm{org}}_{p1}.member\left[0\right].p\left[j\right]& otherwise\end{array}\right.$其中org_p2.num为org_p2中的个体数，member_new1[i].b和org_p2.member[0].b为对应成员中的模块排列信息，member[0]指对应组织中的第一个个体，member[i]指对应组织中的第i+1个个体，member[0].p[j]与member[i].p[j]指对应个体第j+1个模块的长宽比；3)随机生成org_p2.num/2个新个体，member_new2；步骤107：将培训算子作用在从组织选出的个体，被选出的个体称为该组织的代表，按照组织中个体的排列顺序，第一个未被培训过的个体被选为代表，若所有的个体都已经被培训过则选择第一个个体为代表；对培训后的个体进行最优启发式序列编码和解码，找出最优个体，其中对每个组织的代表个体进行培训的具体规则如下：对下面三步独立进行操作，每步执行5次；1)改变模块的放置顺序：对模块b[i](0≤i≤n)，从b中选择另一个模块与其交换位置；2)改变模块的长宽比：对长宽比p[j](0≤j≤n)，用[min h_w，max h_w]中的任意值替换它；3)改变芯片的宽度W：随机生成一个正实数代替W，每次改变后都可以得到一个新的个体，如果新的个体的COST小于选出的代表的COST，则用新的个体代替原来的个体，否则保留原有个体；培训完以后，将培训的个体标记为1，表示该个体已经培训过；步骤108：采用最优适应启发式序列对每个个体编码和解码，找出最优个体；步骤109：如果满足结束条件，即超过最大进化代数，则转向步骤110；否则，令t自加1，并转向步骤105；步骤110：输出布图结果；步骤111：结束基于最优适应启发式序列与组织进化的集成电路布图方法。