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

摘要

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

主权项

一种基于最优适应启发式序列与多目标组织进化的集成电路布图方法，其特征是：具体步骤如下：步骤101：开始基于最优适应启发式序列与多目标组织进化的集成电路布图方法；步骤102：参数设定：最大进化代数T，种群规模num，外部Pareto集规模N_p，一个合法组织所允许的最大规模num_max，最优适应度Best，t为大于或等于0的整数，表示进化到第t代；步骤103：初始化每个个体，更新最优值Best，令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)}把一个组织org_p分裂成两个非空组织，其中U(0,1)是0到1之间的一个任意值，N_member是所有组织中所有个体的总数，每个组织中的个体按适应度从大到小进行排列；步骤106：将吞并算子作用在两个组织上，随机选择两个组织org_p1和org_p2，合并成组织org_c，org_p1和org_p2各自的Pareto解集为P1和P2，把P1和P2合并成一个Pareto集Ph，如果P1在Ph中占的比重大于P2在Ph中的比重，则组织org_p1获胜，org_p1吞并org_p2；如果P1在Ph中占的比重小于P2在Ph中的比重，则组织org_p2获胜，org_p2吞并org_p1；如果P1在Ph中占的比重与P2在Ph中的比重相等，则任取一个吞并另一个；其具体规则如下：假设组织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]& else\end{array}\right.$3)随机生成org_p2.num/2个新个体member_new2；步骤107：通过排序比较找出当前种群的Pareto解集，其规模为Np，构成外部集；步骤108：将培训算子作用在从组织中选出的个体，培训算子对外部集中的每个个体进行操作，以缩短非劣前段与Pareto最优前端的距离，使非劣前段的分布更广更均匀，对个体进行扰动，生成新个体，并计算新个体的两个目标函数值，如果新个体支配原来的个体，则用新的个体取代原个体；否则把新老个体都保留起来，形成伪Pareto集，最后对该集进行排序选择生成下一代的外部集；对培训后的个体进行最优启发式序列编码和解码，从所有组织中找出Pareto解；其中对每个组织的代表个体进行培训的具体规则如下：对下面三步独立进行操作，每步执行5次；1)改变模块的放置顺序：对模块b[i]，其中，0≤i≤n，从b中选择另一个模块与其交换位置；2)改变模块的长宽比：对长宽比p[j]，其中，0≤j≤n，用[min h_w，max h_w]中的任意值替换它；3)改变芯片的宽度：随机生成一个正实数代替W，每次改变后都得到一个新的个体，如果新的个体的COST小于选出的代表的COST，则用新的个体代替原来的个体，否则保留原有个体；培训完以后，将培训的个体标记为1，表示该个体已经培训过；步骤109：用最优适应启发式进行编码和解码每个个体，找出最优个体；步骤110：如果满足结束条件，即超过最大进化代数，则转向步骤111；否则，令t自加1，并转向步骤105；步骤111：输出布图结果；步骤112：结束基于最优适应启发式与多目标组织进化的集成电路布图方法；所述步骤104，包括如下步骤：步骤201：开始基于最优适应启发式的算法，对模块进行编码和解码；步骤202：第一个模块b[0]被放在第一象限的左下角，它的长宽比为p[0]；芯片的初始化宽度为W，令i＝0；步骤203：每个模块都遵循左下紧布局原则，放置在顶线上最低最适合的位置上；只有一种情况例外：当最低线段和次最低线段相邻，且最低段在次最低段的左边时，模块遵循右下紧布局原则放置；软矩形模块的最低最适合的位置满足两个条件：(1)在顶线上，该位置是所有能放置该软矩形模块的最低段；(2)在长宽比允许的限度内，软矩形模块能放置在该位置上，并且尽可能占满该位置，使它留下的空白区最少；步骤204：判断ylowest是否为0，ylowest为放置第一排模块；如果ylowest为0，转向步骤205；否则，转向步骤207；步骤205：软矩形模块的形状由它的初始长宽比决定；步骤206：放置模块，当被放置的模块的右边界超出了芯片的右边界即Rside的限制时，用该模块的右边界更新Rside的值，至此，第一排模块放置完成，以后再放置的任何模块都不允许超出Rside的限制；转向步骤209；步骤207：调整软矩形模块的长宽比；步骤208：为模块寻找最低最合适的位置放置模块；依次在最低线段、次最低线段以及最低线段和次最低线段相邻的三种情况中寻找，如果找到，则放置该模块；否则，抬高最低线段，重新开始寻找，直到模块被放置在最优合适的位置上；步骤209：每放置一个模块或抬高最低线段后，都更新顶线；步骤210：i＝i+1；步骤211：如果i<n，转向步骤203；否则，转向步骤212；步骤212：被放置完时，结束最优适应启发式序列的编码和解码。