本发明公开了一种全局布线中针对单元移动的位置预测方法，包括以下步骤：构建任意两个格点间最小代价查找表；基于深度优先搜索，生成初始搜索集合；基于广度优先搜索，遍历搜索二维网格图，得到单元在每个格点上的代价值，实现对于移动单元满足约束的位置的准确预测，其中需要满足的约束包括最小布线层、布线方向和电压区域约束，同时本发明还考虑了关键线网布线路径上的延时和各布线层的功率消耗这两个关键指标。本发明能够在保持预测准确性的前提下，克服传统3D暴力搜索方法时间复杂度高的缺点，极大地缩短了位置预测时间，快速优化布局布线质量。
1.一种全局布线中针对单元移动的位置预测方法，其特征在于：包括以下步骤：
步骤S1，构建两格点间最小代价的查找表，查找表包括：两格点在z方向上的通孔距离、在x、y方向上经过的布线层的powerfactor数值；
步骤S2，构建数组，在读入层信息时，保存powerfactor数值发生变化的当前层的id信息；并基于单元所连接线网的布线点，计算后续遍历位置的边界框边界信息；
步骤S3，遍历单元相连接的线网，基于深度优先搜索，遍历线网布线路径上的所有格点，生成初始搜索集合；
步骤S4，计算初始搜索集合中的每一点与此线网在当前预测单元的pin所处布线层上此点正下方的点之间的最小代价dis，并将dis与布线层上的这一点作为一组值一同插入优先队列；
步骤S5，对优先队列中的每一组值，基于广度优先搜索，在步骤S2计算的边界框内，遍历预测单元的pin所处布线层上的每一个格点，计算每一格点连接到线网剩余连通部分的最小代价，将代价存放在此线网的cost数组中；
步骤S6，重复执行步骤S3至S5，直到当前预测单元连接的所有线网均遍历完成，并生成线网对应的代价数组；
步骤S7，将单元对应的所有线网对应的代价数组加和，得出单元最终预测的代价数组。
2.根据权利要求1所述的全局布线中针对单元移动的位置预测方法，其特征在于：所述步骤S1中，优先构建初始的代价查找表。
3.根据权利要求1或2所述的全局布线中针对单元移动的位置预测方法，其特征在于：
所述步骤S1中，构建查找表时需考虑以下约束：两格点所在布线层、两格点在x与y方向上是否存在偏移与两格点对应线网的最小布线层；构建查找表的步骤为：记格点1所在层为z1，格点2所在层为z2，两格点对应线网最小布线层为m，两点在x方向上是否存在偏移记作状态xState，在y方向上是否存在偏移记作状态yState，则查找表的构建过程需要穷举以上5个变量取值的所有情况，并在对应情况下，计算查找表的三部分代价值。
4.根据权利要求1所述的全局布线中针对单元移动的位置预测方法，其特征在于：所述步骤S2中，对于边界框跨度大的线网，在进行布线时，更偏向于让其向高层去走线，因此，需要将边界框跨度考虑进去，对应采取的办法便是在读入层信息时，保存powerfactor数值发生变化的当前层的id信息，插入比较数组，后续进行广度优先搜索的时候，会将移动单元关联的所有线网的最小布线层的id与比较数组中的值进行比较。
5.根据权利要求1所述的全局布线中针对单元移动的位置预测方法，其特征在于：所述步骤S3中，需要先从移动单元的pin所在的格点开始，拆除线网，拆除之后线网剩余部分必须是一个整体；如果拆除当前pin之后，线网剩余部分包含两个及以上的连通分支，则不对线网进行拆除；拆除过程中，若碰到节点的度小于2，并且格点中不存在pin，则此节点与前一节点的连接需要进行拆除，同时delCntR＝delCntR+powerfactor<此节点的三维坐标>；
直到遍历到有节点的度大于等于2，或者节点包含线网的pin，那么拆除过程停止，接着基于深度优先搜索，从停止的节点开始，将线网剩余连通部分的所有节点插入初始的搜索集合GR。
6.根据权利要求1所述的全局布线中针对单元移动的位置预测方法，其特征在于：所述步骤S5中，基于广度优先搜索时，取出优先队列顶部的一组值，遍历这组值中格点的所有邻居节点，计算每一邻居格点满足约束的条件下，连接到线网剩余部分的最小代价，对每一方向邻居节点的操作包含如下子操作：(a)计算此方向的邻居格点与线网对应的格点的距离，记作dis；
(b)对于比较数组的每一个值，将其与线网最小布线层id进行最大值比较，对最小布线层进行更新，基于查找表重新计算dis，若得到的dis更小，则对dis进行更新；
(c)将此邻居格点以及dis作为一组值一同插入优先队列，同时将dis存在线网的cost数组中。
7.根据权利要求1所述的全局布线中针对单元移动的位置预测方法，其特征在于：所述步骤S7中，将每条线网对应的代价数组减去delCntR，并乘上线网权重，及cost＝(cost–delCntR)*weight，之后将每条线网对应的cost数组进行求和，得出单元最终预测的代价数组。
一种全局布线中针对单元移动的位置预测方法
技术领域
[0001] 本发明涉及一种全局布线中针对单元移动的位置预测方法，属于集成电路设计自动化技术领域。
背景技术
[0002] 集成电路物理设计是典型的NP困难问题，当前主流的方法是将该问题分解成布局和布线这2个子问题，布局确定单元在芯片上的具体位置，后续的布线环节根据布局的结果来确定每个线网的具体走线。为了进一步降低问题的求解难度，通常将布局和布线问题分解成更多的子问题。这种分治的策略可以在合理的时间内求解复杂的物理设计问题。但是，随着越来越多的子问题被定义，子问题之间的相关性/目标可能彼此不一致。虽然预留一定的余量可以改善下一阶段的收敛性，但预留余量和子问题之间的非高度相关性极大地降低了物理设计问题的求解质量，从而影响芯片性能。
[0003] 为了解决物理设计分治方法中预留余量和子问题不相关的问题，在布线阶段支持单元移动越来越受到关注。保持良好布局质量以及满足所有布线约束的情况下，在布线阶段对部分单元进行移动可以实现更好的解质量，大大提高物理设计方法的有效性和鲁棒性。此外，布线阶段移动单元时也应该确保布线约束能够满足，主要的约束包括：(1)布线方向约束，针对特定的布线层，只允许单一方向的布线，即水平或垂直布线；(2)最小布线层约束，这是线网需要满足的约束，即在最小布线层下不允许出现水平和垂直走线；(3)电压区域约束，不同的单元需要的电压基准也可能不同，因此单元必须放置在特定的电压区域内。此外，关键线网布线路径上的延时和不同布线层的功率损耗这2个关键指标也应该被仔细的考虑。
[0004] 获得全局布线的结果后，为了通过单元移动来克服分治方法中预留余量和子问题不相关的问题，如何为单元确定理想的位置变得至关重要。由于布局布线解空间巨大，遍历所有位置几乎可不能实现。因此，好的单元移动是建立在预测位置较为准确的基础上的，由于位置预测这一步骤贯穿于整个单元移动的流程中，不仅在每轮迭代的开始时需要对每个可移动单元进行位置预测，每个单元移动后也要对相关的单元进行位置预测的更新，所以过高的时间复杂度可能会使得位置预测成为整个流程运行时间的瓶颈。因此，设计一种能够在保持预测准确性的前提下，克服传统3D暴力搜索方法时间复杂度高的缺点的针对单元移动的位置预测方法，对优化集成电路物理设计解的质量以及提高芯片性能指标有重要的作用和意义。
发明内容
[0005] 为了克服在布线阶段进行单元移动时传统位置暴力搜索方法时间复杂度高的问题，本发明的目的是提供一种全局布线中针对单元移动的位置预测方法，能够保证在保持预测准确性的同时，极大地缩短位置预测时间，快速优化布局布线质量。
[0006] 为实现上述目的，本发明采用如下技术方案：
[0007] 一种全局布线中针对单元移动的位置预测方法，包括以下步骤：
[0008] 步骤S1，构建两格点间最小代价的查找表，查找表包括：两格点在z方向上的通孔距离、在x、y方向上经过的布线层的powerfactor数值；
[0009] 步骤S2，构建数组，在读入层信息时，保存powerfactor数值发生变化的当前层的id信息；并基于单元所连接线网的布线点，计算后续遍历位置的边界框边界信息；
[0010] 步骤S3，遍历单元相连接的线网，基于深度优先搜索，遍历线网布线路径上的所有格点，生成初始搜索集合；
[0011] 步骤S4，计算初始搜索集合中的每一点与此线网在当前预测单元的pin所处布线层上此点正下方的点之间的最小代价dis，并将dis与布线层上的这一点作为一组值一同插入优先队列；
[0012] 步骤S5，对优先队列中的每一组值，基于广度优先搜索，在步骤S2计算的边界框内，遍历预测单元的pin所处布线层上的每一个格点，计算每一格点连接到线网剩余连通部分的最小代价，将代价存放在此线网的cost数组中；
[0013] 步骤S6，重复执行步骤S3至S5，直到当前预测单元连接的所有线网均遍历完成，并生成线网对应的代价数组；
[0014] 步骤S7，将单元对应的所有线网对应的代价数组加和，得出单元最终预测的代价数组。
[0015] 所述步骤S1中，优先构建初始的代价查找表。
[0016] 所述步骤S1中，构建查找表时需考虑以下约束：两格点所在布线层、两格点在x与y方向上是否存在偏移与两格点对应线网的最小布线层；构建查找表的步骤为：记格点1所在层为z1，格点2所在层为z2，两格点对应线网最小布线层为m，两点在x方向上是否存在偏移记作状态xState，在y方向上是否存在偏移记作状态yState，则查找表的构建过程需要穷举以上5个变量取值的所有情况，并在对应情况下，计算查找表的三部分代价值。
[0017] 所述步骤S2中，对于边界框跨度大的线网，在进行布线时，更偏向于让其向高层去走线，因此，需要将边界框跨度考虑进去，对应采取的办法便是在读入层信息时，保存powerfactor数值发生变化的当前层的id信息，插入比较数组，后续进行广度优先搜索的时候，会将移动单元关联的所有线网的最小布线层的id与比较数组中的值进行比较。
[0018] 所述步骤S3中，需要先从移动单元的pin所在的格点开始，拆除线网，拆除之后线网剩余部分必须是一个整体；如果拆除当前pin之后，线网剩余部分包含两个及以上的连通分支，则不对线网进行拆除；拆除过程中，若碰到节点的度小于2，并且格点中不存在pin，则此节点与前一节点的连接需要进行拆除，同时delCntR＝delCntR+powerfactor<此节点的三维坐标>；直到遍历到有节点的度大于等于2，或者节点包含线网的pin，那么拆除过程停止，接着基于深度优先搜索，从停止的节点开始，将线网剩余连通部分的所有节点插入初始的搜索集合GR。
[0019] 所述步骤S5中，基于广度优先搜索时，取出优先队列顶部的一组值，遍历这组值中格点的所有邻居节点，计算每一邻居格点满足约束的条件下，连接到线网剩余部分的最小代价，对每一方向邻居节点的操作包含如下子操作：
[0020] (a)计算此方向的邻居格点与线网对应的格点的距离，记作dis；
[0021] (b)对于比较数组的每一个值，将其与线网最小布线层id进行最大值比较，对最小布线层进行更新，基于查找表重新计算dis，若得到的dis更小，则对dis进行更新；
[0022] (c)将此邻居格点以及dis作为一组值一同插入优先队列，同时将dis存在线网的cost数组中。
[0023] 所述步骤S7中，将每条线网对应的代价数组减去delCntR，并乘上线网权重，及cost＝(cost–delCntR)*weight，之后将每条线网对应的cost数组进行求和，得出单元最终预测的代价数组。
[0024] 有益效果：本发明采用上述技术方案，具有以下有益效果：(1)速度快，假设单元对应的边界框在x与y方向上的跨度为M和N，布线层数量为L，则进行暴力3D网格搜索的时间复杂度为O(MNL)，但是此方法只需要对单元对应的Pin所在的层进行遍历，时间复杂度为O(MN)，时间大大加快；(2)效果好，对于边界框跨度大的线网，更偏向于让其向高层去走线，因此，在进行预测时，需要将最小布线层进行若干次抬高，即将最小布线层与powerfactor发生变化的层进行比较计算，能够让边界框跨度大的线网的相关单元的预测效果达到与暴力3D搜索相同的效果。
附图说明
[0025] 图1为本发明的一种全局布线中针对单元移动的位置预测方法的流程图；
[0026] 图2为本发明的实施例中构建满足布线方向约束、最小布线层约束以及电压区域约束的两格点间最小代价的查找表的示意图；
[0027] 图3为本发明的实施例的预测单元的某一相关线网的初始状态示意图；
[0028] 图4为本发明的实施例的预测单元的某一相关线网将需要拆除的边进行拆除的示意图；
[0029] 图5为本发明的实施例的预测单元的某一相关线网相关的边拆除之后，基于线网剩余部分向单元对应的pin所在层投影生成的初始搜索集合执行广度优先搜索过程的示意图。
具体实施方式
[0030] 下面结合附图对本发明做更进一步的解释。
[0031] 如图1所示，本发明的一种全局布线中针对单元移动的位置预测方法，包括以下步骤：
[0032] 步骤S1，构建两格点间最小代价的查找表，查找表包括：两格点在z方向上的通孔距离、在x、y方向上经过的布线层的powerfactor数值；
[0033] 其中，优先构建初始的代价查找表；
[0034] 构建查找表时需考虑以下约束：两格点所在布线层、两格点在x与y方向上是否存在偏移与两格点对应线网的最小布线层；构建查找表的步骤为：记格点1所在层为z1，格点2所在层为z2，两格点对应线网最小布线层为m，两点在x方向上是否存在偏移记作状态xState，在y方向上是否存在偏移记作状态yState，则查找表的构建过程需要穷举以上5个变量取值的所有情况，并在对应情况下，计算查找表的三部分代价值；
[0035] 步骤S2，构建数组，在读入层信息时，保存powerfactor数值发生变化的当前层的id信息；并基于单元所连接线网的布线点，计算后续遍历位置的边界框边界信息；
[0036] 对于边界框跨度大的线网，在进行布线时，更偏向于让其向高层去走线，因此，需要将边界框跨度考虑进去，对应采取的办法便是在读入层信息时，保存powerfactor数值发生变化的当前层的id信息，插入比较数组，后续进行广度优先搜索的时候，会将移动单元关联的所有线网的最小布线层的id与比较数组中的值进行比较；
[0037] 步骤S3，遍历单元相连接的线网，基于深度优先搜索，遍历线网布线路径上的所有格点，生成初始搜索集合；
[0038] 步骤S4，计算初始搜索集合中的每一点与此线网在当前预测单元的pin所处布线层上此点正下方的点之间的最小代价dis，并将dis与布线层上的这一点作为一组值一同插入优先队列；
[0039] 步骤S5，对优先队列中的每一组值，基于广度优先搜索，在步骤S2计算的边界框内，遍历预测单元的pin所处布线层上的每一个格点，计算每一格点连接到线网剩余连通部分的最小代价，将代价存放在此线网的cost数组中；
[0040] 基于广度优先搜索时，取出优先队列顶部的一组值，遍历这组值中格点的所有邻居节点，计算每一邻居格点满足约束的条件下，连接到线网剩余部分的最小代价，对每一方向邻居节点的操作包含如下子操作：
[0041] (a)计算此方向的邻居格点与线网对应的格点的距离，记作dis；
[0042] (b)对于比较数组的每一个值，将其与线网最小布线层id进行最大值比较，对最小布线层进行更新，基于查找表重新计算dis，若得到的dis更小，则对dis进行更新；
[0043] (c)将此邻居格点以及dis作为一组值一同插入优先队列，同时将dis存在线网的cost数组中；
[0044] 步骤S6，重复执行步骤S3至S5，直到当前预测单元连接的所有线网均遍历完成，并生成线网对应的代价数组；
[0045] 步骤S7，将单元对应的所有线网对应的代价数组加和，得出单元最终预测的代价数组，具体为：将每条线网对应的代价数组减去delCntR，并乘上线网权重，及cost＝(cost–delCntR)*weight，之后将每条线网对应的cost数组进行求和，得出单元最终预测的代价数组。
[0046] 实施例
[0047] 本实施例包括如下步骤：(1)构建满足布线方向约束、最小布线层约束以及电压区域约束的两格点间最小代价的查找表；(2)保存powerfactor发生变化的当前层的id信息；并基于单元所连接线网的布线点，计算后续遍历位置的边界框边界信息；(3)遍历单元相连接的线网，基于深度优先搜索，遍历线网布线路径上的所有格点，生成初始搜索集合；(4)基于初始搜索集合，计算集合中的每一点与此线网在当前预测单元的pin所处布线层上，此点正下方的点之间的最小代价，并将此代价与布线层上的这一点作为一组值一同插入优先队列；(5)对优先队列中的每一组值，基于广度优先搜索，在步骤S2计算的边界框内，遍历预测单元的pin所处布线层上的每一个格点，计算每一格点连接到线网剩余连通部分的最小代价，将代价存放在此线网的cost数组中；(6)重复执行步骤(3)‑(5)，直到单元连接的所有线网均遍历完，并生成了线网对应的cost数组；(7)将单元对应的所有线网对应的代价数组加权和，得出单元最终预测的代价数组。
[0048] 图2为根据本实施例构建两格点间最小代价查找表的示意图，图中展示了两格点在x与y方向上是否存在偏移的四种组合情况，在满足布线方向约束、最小布线层约束以及电压区域约束的条件下，可以求出两点间理论情况下的最小代价，如图连线所示：从g1到g2、g3、g4、g5的四条路径即两格点在x与y方向上是否存在偏移的四种情况的举例说明；以g1‑g4的连接路径为例，这两点对应的查找表中的代价为：zCost＝1.2+1.0+0.8＝3.0，xCost＝0.8，yCost＝0.6。
[0049] 图3为根据本实施例单元的某一相关线网的初始状态示意图，图中的灰色圆形是此线网在当前移动单元中的pin，黑色折线表示当前线网在最小布线层上的完整布线路径。
[0050] 图4为根据本实施例预测单元的某一相关线网将需要拆除的边进行拆除的示意图，以pin所在格点为起始点，若碰到节点的大于1，或者格点存在pin，则拆除停止，拆除掉的点的powerfactor进行求和，和值记作delCntR。
[0051] 图5为根据本实施例预测单元的某一相关线网相关的边拆除之后，基于线网剩余部分向单元对应的pin所在层投影生成的初始搜索集合执行广度优先搜索过程的示意图，经过n次扩展，最终单元的整个边界框内在当前pin所在层的所有2D格点均遍历完成，生成最终的代价数组。
[0052] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。
