(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211267276.7 (22)申请日 2022.10.17 (71)申请人 东南大学 地址 211189 江苏省南京市江宁区东 南大 学路2号 (72)发明人 申福恒　朱自然　 (74)专利代理 机构 南京瑞弘专利商标事务所 (普通合伙) 32249 专利代理师 沈廉 (51)Int.Cl. G06F 30/394(2020.01) G06F 30/398(2020.01) G06K 9/62(2022.01) G06F 111/04(2020.01) (54)发明名称 一种考虑先进制程约束和单元移动 的全局 布线方法 (57)摘要 本发明设计了一种考虑先进制程约束和单 元移动的全局布线方法， 属于集成电路设计自动 化领域， 该方法主要包括如下步骤： (1)对于给定 的具有先进制程约束且有初始布局布线解的网 表， 执行功耗感知的布线优化； (2)构建布线层约 束感知的查找表； (3)基于 前级构建的查找表， 提 出时序驱动的增益图生成方法； (4)确定当前轮 次单元移动的顺序； (5)根据前级确定的单元移 动顺序， 执行单元移动 及线网部分拆线重布； (6) 执行聚类移动及线网部分拆线重布线； (7)执行 单元移动量合法化及线网布线优化。 本发明能够 在考虑先进制程约束的前提下， 基于本方法中提 出的高精度单元位置预测算法， 执行高效的单元 移动来有效降低全局布线 线长。 权利要求书4页 说明书9页 附图1页 CN 115526140 A 2022.12.27 CN 115526140 A 1.一种考虑先进制程约束和单元移动的全局布线方法， 其特征在于， 该方法包括如下 步骤： 步骤S1： 对于给定的具有先进制程约束且有初始布局布线解的网表， 执行功耗感知的 布线优化 来获得更优且收敛的布线结果， 从而给后续的单 元移动提供准确的位置信息； 步骤S2： 为了提高后续单 元移动位置预测过程的效率， 构建布线层约束感知的查找 表； 步骤S3： 基于前级构建的查找 表， 提出时序驱动的增益图生成方法； 步骤S4： 对所有单元基于增益图生成方法， 执行位置预测， 根据每个单元的最大移动收 益进行排序， 确定当前轮次单 元移动的顺序； 步骤S5： 根据前级确定的单 元移动顺序， 执 行单元移动及线网部分拆线重布； 步骤S6： 执 行聚类移动及线网部分拆线重布线； 步骤S7： 执 行单元移动量 合法化及线网布线优化； 步骤S8： 重复执 行步骤S4 ‑S7， 直到加权总线长收敛。 2.根据权利要求1所述的一种考虑先进制程约束和单元移动的全局布线方法， 其特征 在于： 在所述步骤S1中， 所述的功 耗感知的布线优化方法， 来 获得基于固定布局的更优且收 敛的布线结果， 包括以下两步： 第一步， 处理线 网最小布线层约束； 首先， 为了简化最小布线层约束对整个布线过程的 影响， 采取一个简单而有效的操作来处理最小布线层约束： 先将网络最小布线层以下 的实 际管脚投射到最小布线层上， 形成虚拟管脚， 然后， 以最小布线层为界， 将线网的布线路径 分为两部 分： 最小层上连接段集合和最小层下连接段集合； 在布线过程中， 只要最小布线层 下的引脚位置不 发生变化， 最小层下连接段集合中的连接部分就不会发生变化， 因此， 在实 际布线过程中不需要处理最小层下连接段集合中的这部 分连接， 只需要在 满足布线方向约 束的前提下， 将最小布线层上的实际引脚与投射到最小层上的虚拟管脚进行布线连接即 可； 第二步， 功耗感知的两级线网重布线； 实现了一种功耗感知的两级线网重布线方案来 优化初始布线 结果； 首先， 通过直角Steiner 最小树算法将网络最小布线层或之上的所有实 际和虚拟引脚分解为多组引脚对； 然后， 利用模式布线与层分配技术来生成更好的3D布线 结果； 其次， 采用直接在3D空间工作的多源多汇的迷宫路由算法， 在考虑拥塞信息的情况 下， 进一步改善布线 结果； 在迷宫布线 过程中， 对于布线模型中的每个3D格点u， 其迷宫布线 的代价由式(1)计算， 布线代价包括基本代价、 拥塞代价和溢出惩罚代价 三部分， 其中 是格点u所在层的基础功耗， 也即布线的基础代价， capacity(u)与demand(u) 分别是格点u的线网容量以及当前被消耗掉 的资源； α1∈{0,1}是避免格点u溢出的惩罚因 子， 当格点u的可用布线 资源为零， 也即capacity(u)＝dem and(u)时， α1将为1， 而u的溢出惩 罚代价将是 无穷大。 3.根据权利要求1所述的一种考虑先进制程约束和单元移动的全局布线方法， 其特征 在于， 在所述步骤S2中， 由于单元移动方法的表现极其依赖位置预测算法的表现， 设计一个 准确估计模型中任意两点之 间的布线连接线长的方法， 构建了一个最小加权布线线长的查权　利　要　求　书 1/4 页 2 CN 115526140 A 2找表； 当布线模型中不存在任何布线约束时， 任意两点之间的最小连接距离为他们之间的 3D曼哈顿距离， 当对模型施加最小层约束与布线方向约束后， 最小的布线距离的估计会变 得非常困难， 在这种 具有先进制程约束的场景下， 对于两点之间的最小加权布线线长的计 算方法， 在满足布线方向约束的前提下， 给定格点u(xu,yu,zv),v(xv,yv,zv)， 这两点之间的加权 布线线长wl(u,v,lx,ly)通过公式(2)进行估计， 其中， Δx＝|xu‑xv|,Δy＝|yu‑yv|,lx,ly是布线路径中水平和垂直连接部分所处的布 线层， wlz是布线路径在z方向上的加权线长 长度， 通过公式(3)进行计算， 其中l＝max(lx,ly),z1＝min(zu,zv),z2＝max(zu,zv)； 用LH与LV分别代表布线模型中布线方向是水平和垂直 的所有布线层， 连接格点u和v的 最小加权布线 线长可以定义如下， 显然， 遍历每一组lx,ly， 就可以得到最小的加权布线 线长； 通过分析布线模型的特点， 对计算过程进行简化， 基于格点u和v的相对位置关系， 将 wlmin(u,v)的计算情况分为如下四种情况： (1)xu≠xv,yu≠yv； (2)xu＝xv,yu≠yv； (3)xu≠xv, yu＝yv； (4)xu＝xv,yu＝yv， 以最复杂的情况(1)为例来 阐述一下我们的简化操作； 对于给定的lx∈LH,ly∈LV， 假设lx>ly， 由于在布线模型中， 从低层到高层， 功耗逐渐减 小， 因此 所以得到 因为式(3)， 所以可以得到w l(u,v,lx,ly)≥wl(u,v,lx,lx‑1)， 因此 同样地， 如果 lx<ly， 可以得到， 从式(6)(7)中可以发现， 可以尝试遍历所有相邻层l,l+1， 并进行布线， 即可得到最短 的加权布 线线长， 这样算法的时间复杂度会大大降低(简化后的时间复杂度为O(Nlayer))， 需 要注意的是， 如果pfl‑1＝pfl+1， 则相邻层l,l+1 的遍历不需要进行计算； 为了减少单元移动 位置预测过程中的冗余计算， 基于两格点之间的相对位置信息构建了最短加权布线线长的 查找表mwrw， 也即wlmin(u,v)＝mwrw(| xu‑xv|,|yu‑yv|,zu,z_v)， 在后续的预测过程中需要求 任意两个格点间的最小加权布线线长时， 只需要根据这两点以上四个特征， 在表mwrw中进权　利　要　求　书 2/4 页 3 CN 115526140 A 3