(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211367045.3 (22)申请日 2022.11.02 (71)申请人 西安电子科技大 学广州研究院 地址 510555 广东省广州市黄埔区中新知 识城海丝中心B5、 B6、 B7栋 (72)发明人 赵宏　陈文玮　刘静　 (74)专利代理 机构 广州大象飞扬知识产权代理 有限公司 4 4745 专利代理师 蒋静 (51)Int.Cl. G06F 30/392(2020.01) G06F 30/398(2020.01) G06N 3/12(2006.01) G06K 9/62(2022.01) (54)发明名称 基于遗传算法的大规模集成电路布局优化 方法 (57)摘要 本发明涉及集 成电路布局技术领域， 具体的 说是基于遗传算法的大规模集成电路布局优化 方法， 包括以下步骤： 参数设置、 聚类操作、 进一 步划分聚类操作、 采用遗传算法进行优化、 解码 操作、 选择操作、 交叉操作、 变异操作和判断是否 满足终止条件， 在使用时， 首先采用了基于模块 度的聚类方法， 以此来确定后续放置过程中应 保 持紧密联系的Cell， 不需要人为 设置参数及终止 条件， 能够通过算法本身自动完成上述过程， 用 来寻找每个Cell的放置位置， 可以使得最终的布 局更加紧凑， 总线长更短， 方便进行使用。 权利要求书3页 说明书6页 附图4页 CN 115544947 A 2022.12.30 CN 115544947 A 1.基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 优化方法包括以下步 骤： 步骤一、 参数设置， 设置种群规模Np， 交叉概率Pc， 变异概率Pm， t为大于或等于0的整 数， 表示第t 代， G为终止进化代数， rand是随机产生的0 到1之间的数； 步骤二、 聚类操作， 根据给定的信息， 网表中包含多个net， 每个net中包含多个Cell， 同 一个Cell可以出现在多个net中； 步骤三、 进一步划分聚类操作， 在上一步骤得到聚类结果之后， 在处理大规模电路时， 每个聚类中包含的Cell的数量仍然较大， 因此进行进一步的划分操作， 将问题分解为若干 个更小规模的问题进行求 解； 步骤四、 对上一 步骤中得到的Cel l组合分别采用遗传算法进行优化； 步骤五、 解码操作， 调用滑动窗口算法对每个个体进行解码， 解码后计算得到放置完成 后的总线长， 记录总线长最小的个 体为Best； 步骤六、 选择操作， 根据上一 步计算得到的种群适应值； 步骤七、 交叉操作， 对交配池中的个体， 若rand<Pc， 从交配池中随机选出一对个体， 采 用交叉算子进行优化； 步骤八、 变异操作， 对种群中的每个个体， 若rand<Pm， 采用变异算子进行优化， 且规则 为： 随机选择两个位置， 交换这两个位置的Cel l； 步骤九、 判断是否满足终止条件， 终止条件为迭代次数达到终止进化代数， 若不满足终 止条件， 则继续进行迭代优化， 返回步骤六， 否则， 结束搜索过程， 输出最优个体Best， 得到 最终的布局结果。 2.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤二中， 在构建 网络拓扑图的过程中， 将net看作是图中的一个节 点， 如果两个net包含 共同的Cell， 则这两个节点之 间存在着连接 关系， 即存在一条边， 最 终构造得到的图为无向 无权图， 对图进行聚类操作， 目的是将联系紧密的net 中的Cell尽可能放置在临近的位置， 从而使得总线长更短， 聚类算法采用模块度作为衡量标准。 3.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤三中， 将每个聚类中的net依次展开， 得到其中包含的Cell， 直至总数量大于等于20， 如果某个Cel l在之前出现过， 则跳过。 最终每 个聚类被划分为若干个Cel l的组合。 4.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤四中， 初始化种群： 编码方式采用序列编码， 编码长度为n， n表示待放置Cell的总数 量， 在编码中的位置表示各个Cel l的放置顺序， 且按照以下 方式生成初始种群： A1、 根据Cel l的长度进行从大到小的排序， 得到最终的编码； A2、 根据Cel l的长度进行从小到大的排序， 得到最终的编码； A3、 对Cel l的编号进行随机排列， 得到最终的编码。 5.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤六中， 采用二元锦标赛方法从父代种群中选出Np个个体放入交配池中， 线长更短的 个体具有更 大的概率被选择。 6.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤七中， 交叉算子使用顺序交叉算子， 具体步骤如下：权　利　要　求　书 1/3 页 2 CN 115544947 A 2B1、 从其中一个父代随机 选择一个子串； B2、 生成一个临时子代， 将上一 步得到的子串复制到对应的位置上； B3、 将子串中包含的编号从另一个父代中删除， 剩下的编号便是临时子代所需要的编 号； B4、 将上一步剩下的元素按从左到右的顺序依次放入临时子代中空缺的位置， 最终生 成一个正式后代。 7.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤二中的聚类操作时， 一个目的是将联系较紧密的Cell划分到一个聚类中， 在后续的 放置过程中将它们放置在临近的位置， 另一个目的是将大规模问题分解为若干个较小的子 问题， 从而减少求 解问题所需的时间， 算法具体包 含以下步骤： D1、 构建图操作， 根据给定的信息， 网表中包含多个net， 每个net中包含多个Cell， 同一 个Cell可以出现在 多个net中， 在构建网络拓扑图的过程中， 将net看作是图中的一个节 点， 如果两个net包含共同的Cell， 则这两个节点之间存在着连接关系， 即存在一条边， 最终构 造得到的图为无向无权图； D2、 初始化操作， 将图中的每个节点看成是一个独立的社区， 初始的社区数目与总节点 个数相同； D3、 社区间节点转移操作， 对于每个节点， 依次尝试将该节点分配到其每个邻居节点所 在的社区， 计算分配前后的模块度变化， 将节点归入到模块度增益最大的社区中， 如果将该 节点归入到它的邻居节点所在的社区时， 模块度增益为零或者为负数 的话， 则该节点仍然 保留在原来所处的社区中； D4、 重复执行D3步骤， 直到所有节点的所属社区不再发生改变， 至此， 社区间的节点转 移结束； D5、 图重构操作， 由于节点所属的社区发生了变化， 需要对图进行重构， 对前一步得到 的社区进行折叠， 把每个社区折叠成一个节点， 社区内节点之间的边的权重更新为新节点 的环的权 重， 社区间的边权 重更新为新节点间的边权 重， 然后返回执 行D3步骤。 8.根据权利要求1所述的基于遗传算法的大规模集成电路布局优化方法， 其特征在于： 在步骤五中， 进 行解码操作时， 目的是将序列编码转换为最 终的布局方案， 即确定每个Cell 的位置， 算法具体包 含以下步骤： E1、 初始化， 初始的空闲空间列表只包含一个空闲空间， 该空闲空间的大小等于可放置 空间的大小， 待放置列表包含 所有未放置的Cell， 已放置列表初始 为空， 记录待放置Cell列 表中最大的Cell的大小， 记作maxSize， 从空闲空间中取出第一个窗口， 该窗口大小等于 maxSize， 以确保该窗口至少能放下一个Cel l， 然后更新空 闲空间列表； E2、 判断待放置Cell列表是否为空， 若是， 则算法终止， 计算总线长并返回结果， 否则， 从待放置 Cell列表中取 出下一个要放置的Cel l； E3、 判断当前窗口能否容纳该Cell， 如果不能， 执行E4， 如果能， 则将Cell放置到该窗 口， 同时将该Cell 从待放置Cell列表中删除， 并加入到已放置Cell列表中， 同时记录Cell的 位置信息， 执 行E5； E4、 判断空闲空间列表中的所有空间是否都已尝试， 若是， 则算法终止， 由于没有将所 有的Cell放置完毕， 因此无法计算线长， 返回值设为long  long类型所能表示的最大值， 否权　利　要　求　书 2/3 页 3 CN 115544947 A 3