基于整数线性规划的超大规模集成电路布线方法

1.本发明属于集成电路布图设计技术领域，具体涉及一种基于整数线性规划的超大规模集成电路布线方法。


背景技术：

2.数字电路设计工具是一个完整的系统，可以自动化地完成从高层次逻辑综合到低层次版图布局布线的过程。布线是将具有相同电位的引脚用线路连接起来的过程，是数字电路设计中的重要步骤，在布线设计过程中一般需要经历全局布线和详细布线两个阶段。其中，全局布线阶段通常在粗粒度的网格中进行，应当理解，布线区域通常用许多粗粒度的布线网格表示，网格的容量表示布线资源的多少；全局布线的结果是产生线网的拓扑结构，这种拓扑结构指明了线网在到达最终的引脚时需要经过的网格。进一步地，详细布线是在全局布线的结果上进行的，是一个细粒度的、将线网分配到具体轨道的过程。
3.随着集成电路的规模越来越大、集成度越来越高、晶体管特征尺寸越来越接近物理极限，互连线带来的功耗和信号延迟已经成为影响电路性能的重要因素，此外，较高的集成度使得部分线网无法完全布开，产生的涉及规则违例无法被消除。相关技术中，常见的布线算法有迷宫布线和模式布线等，但都有一些缺陷，例如迷宫布线虽然有较强的绕线能力，但容易受到线网布线顺序的影响，使得线网长度和通孔数量总体较多；模式布线多用于全局布线阶段，多使用一些简单的拓扑结构，但容易产生设计规则违例，在由2维拓扑结构向3维拓扑结构转变时易发生拥塞。


技术实现要素：

4.为了解决现有技术中存在的上述问题，本发明提供了一种基于整数线性规划的超大规模集成电路布线方法。本发明要解决的技术问题通过以下技术方案实现：
5.本发明提供一种基于整数线性规划的超大规模集成电路布线方法，包括：
6.根据所述布线区域内的障碍信息、待布线网信息、设计规则信息以及布线轨道信息，进行基础数据初始化；
7.根据所述基础数据生成线网队列，并利用a*搜索算法，搜索所述线网队列中每个待布线网的候选路径；
8.基于所述设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息；
9.根据所述第一违例信息构建价值函数和约束条件，求解最优路径；
10.基于所述最优路径输出布线结果。
11.在本发明的一个实施例中，所述障碍信息包括布线时需要避开的金属层和障碍区域，所述待布线网信息包括待布线网的构成引脚、所述引脚的坐标以及所在金属层，所述设计规则信息包括最小线宽、最小线间距和最小通孔间距，所述布线轨道信息包括每一金属层的轨道数量与轨道间距。
12.在本发明的一个实施例中，根据所述基础数据初始化生成线网队列的步骤，包括：
13.判断所述布线区域是否为第一次布线；若是，则将所述布线区域中的所有线网作为待布线网，加入线网队列；
14.反之，则将上一次布线时存在违例的线网作为待布线网，加入线网队列。
15.在本发明的一个实施例中，利用a*搜索算法，搜索所述线网队列中每个待布线网的候选路径的步骤，包括：
16.令k＝1，l＝1；
17.针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径；
18.增加所述第l条候选路径所经过的第一格点的权重、以及该第一格点的相邻格点的权重；所述相邻格点为第一格点预设邻域内的其它格点；
19.统计所述第l条候选路径的通孔数量以及线网长度；
20.判断l是否小于预设值l；若否，则令l＝l+1，并返回针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得第k个待布线网的l个候选路线，并进一步判断k是否小于所述线网队列中待布线网数量k；
21.若k《k，则令k＝k+1，并返回针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得所有待布线网的候选路线。
22.在本发明的一个实施例中，利用a*搜索算法搜索其第l条候选路径的步骤之后，还包括：
23.将第k个待布线网的第l条候选路线存储在基础数据的二维数组netarray中；
24.获得第k个待布线网的l个候选路线的步骤之后，还包括：
25.针对第k个待布线网，将其l个候选路线分别经过的第一格点的权重、以及每个第一格点的相邻格点的权重归零。
26.在本发明的一个实施例中，基于所述设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息的步骤，包括：
27.基于所述设计规则信息，分别检查每个待布线网中各个候选路线与其他待布线网中各个候选路线之间的违例情况，并在基础数据的违例数组中保存第一违例信息。
28.在本发明的一个实施例中，根据所述第一违例信息构建价值函数和约束条件，求解最优路径的步骤，包括：
29.根据所述第一违例信息构建价值函数：
[0030][0031]
式中，violation[c]表示违例数组中存储的第c条第一违例信息，c＝1,2，
…
，netsize，violation[c]＝netarray[a][m]*netarray[b][n]，netarray[a][m]、netarray[b][n]为引起所述第c条第一违例信息的两条候选路径，netarray[a][m]表示二维数组netarray中存储的第a个待布线网的第m条候选路径，netarray[b][n]表示二维数组netarray中存储的第b个待布线网的第n条候选路径，netarray[i][j]表示二维数组
netarray中存储的第i个待布线网的第j条候选路径，i＝1,2,
…
，k，j＝1,2，
…
,l，wirelength[i][j]表示netarray[i][j]的金属走线长度，viacout[i][j]表示netarray[i][j]包含的通孔数量，w1、w2、w3均为预设权重；
[0032]
针对每个待布线网构建约束条件：
[0033]
netarray[i][1]+netarray[i][2]+...+netarray[i][maxnum]＝1；
[0034]
在所述约束条件下，使所述价值函数达到最小，计算得到每个所述待布线网的最优路径。
[0035]
在本发明的一个实施例中，netarray[i][j]＝1表示第i个待布线网的第j条候选路径被选为最优路径，netarray[i][j]＝0表示第i个待布线网的第j条候选路径未被选为最优路径。
[0036]
在本发明的一个实施例中，基于所述最优路径输出布线结果的步骤，包括：
[0037]
删除所述线网队列中每个待布线网在所述基础数据中的互连信息，所述互连信息包括所述每个待布线网在上一次布线时的最优路径；
[0038]
将所述每个待布线网的最优路径写入基础数据中的互连信息；
[0039]
清空基础数据中的违例数组；
[0040]
基于所述设计规则信息以及当前的互连信息，对不同最优路径之间的违例情况进行检查，并在基础数据的违例数组中保存第二违例信息；
[0041]
判断所述违例数组是否为空；若否，则将存在违例的待布线网所在区域作为布线区域，并返回判断所述布线区域是否为第一次布线的步骤；若是，则根据所述当前的互连信息输出布线结果。
[0042]
与现有技术相比，本发明的有益效果在于：
[0043]
本发明提供了一种基于整数线性规划的超大规模集成电路布线方法，该方法将每个待布线网在搜索过程中产生的候选路径做了收集，并从这些候选路径中挑选最优路径，极大程度上解决了传统布线方案中不易布开、不能最大限度利用中间结果的问题；并且，本发明对设计规则的检查方式加以优化，可以同时检查多个待布线网、多条候选路径，为布线工具中设计规则检查的方式提供了新的思路。
[0044]
以下将结合附图及实施例对本发明做进一步详细说明。
附图说明
[0045]
图1是本发明实施例提供的基于整数线性规划的超大规模集成电路布线方法的一种流程图；
[0046]
图2是本发明实施例提供的搜索待布线网的候选路径的一种流程图；
[0047]
图3是本发明实施例提供的设计规则检查的一种流程图；
[0048]
图4是本发明实施例提供的待布线网的最优路径的示意图。
具体实施方式
[0049]
下面结合具体实施例对本发明做进一步详细的描述，但本发明的实施方式不限于此。
[0050]
图1是本发明实施例提供的基于整数线性规划的超大规模集成电路布线方法的一
种流程图。如图1所示，本发明实施例提供一种基于整数线性规划的超大规模集成电路布线方法，包括：
[0051]
s11、根据布线区域内的障碍信息、待布线网信息、设计规则信息以及布线轨道信息，进行基础数据初始化；
[0052]
s12、根据基础数据生成线网队列，并利用a*搜索算法，搜索线网队列中每个待布线网的候选路径；
[0053]
s13、基于设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息；
[0054]
s14、根据第一违例信息构建价值函数和约束条件，求解最优路径；
[0055]
s15、基于最优路径输出布线结果。
[0056]
本实施例中，首选需读入布线区域内的障碍信息、待布线网信息、设计规则信息以及布线轨道信息，并根据上述信息对基础数据赋值，完成初始化；示例性地，障碍信息包括布线时需要避开的金属层和障碍区域，形状为多边形集合，待布线网信息包括待布线网的构成引脚、引脚的坐标以及所在金属层，设计规则信息包括最小线宽、最小线间距和最小通孔间距，布线轨道信息表示了可用布线资源的多少，其包括每一金属层的轨道数量与轨道间距。
[0057]
可选地，步骤s12中，根据基础数据初始化生成线网队列的步骤，包括：
[0058]
判断布线区域是否为第一次布线；若是，则将布线区域中的所有线网作为待布线网，加入线网队列；
[0059]
反之，则将上一次布线时存在违例的线网作为待布线网，加入线网队列。
[0060]
应当理解，若布线区域此前未经历布线过程，则布线区域中的所有线网都没有进行过引脚互连，需要将所有的线网作为待布线网；若布线区域本次不是第一次布线过程，则获取上一次布线时存在设计规则违例的线网，作为本次的待布线网加入线网队列。
[0061]
图2是本发明实施例提供的搜索待布线网的候选路径的一种流程图。进一步地，如图2所示，利用a*搜索算法，搜索线网队列中每个待布线网的候选路径的步骤，包括：
[0062]
s21、令k＝1，l＝1；
[0063]
s22、针对线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径；
[0064]
s23、增加第l条候选路径所经过的第一格点的权重、以及该第一格点的相邻格点的权重；相邻格点为第一格点预设邻域内的其它格点；
[0065]
s24、统计第l条候选路径的通孔数量以及线网长度；
[0066]
s25、判断l是否小于预设值l；若否，则令l＝l+1，并返回针对线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得第k个待布线网的l个候选路线，并进一步判断k是否小于线网队列中待布线网的数量k；
[0067]
s26、若k《k，则令k＝k+1，并返回针对线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得所有待布线网的候选路线。
[0068]
其中，利用a*搜索算法搜索其第l条候选路径的步骤之后，还包括：
[0069]
将第k个待布线网的第l条候选路线存储在基础数据的二维数组netarray中；
[0070]
获得第k个待布线网的l个候选路线的步骤之后，还包括：
[0071]
针对第k个待布线网，将其l个候选路线分别经过的第一格点的权重、以及每个第
一格点的相邻格点的权重归零。
[0072]
本实施例中，针对线网队列中的每个待布线网展开路径搜索，并记录搜寻过程中产生的候选路径。具体而言，如图2所示，对于每个待布线网，使用a*搜索方式产生候选路径，每搜索到一条候选路径后，立即将这条候选路径保存到基础数据的二维数组netarray中；之后将该候选路径经过的第一格点及其周围格点权重增加，并统计每条候选路径的线网长度(单位：微米)以及通孔数量(单位：个)。应当理解，通过增加候选路径经过的第一格点及其相邻格点的权重，后续搜索到的候选路径再次经过这个第一格点的机会便会降低，如此可保证每个待布线网搜索过程中候选路径之间的差异性。
[0073]
判断本次搜索后该待布线网产生的候选路径数量是否达到了预设值l；如果否，则重复a*搜索，产生另一条候选路径；反之，如果该待布线网的候选路径数量已经达到了预设值l，则不再对该待布线网搜索新的候选路径，并将该待布线网的l条候选路径所经过的第一格点及第一格点的相邻格点的权重归零，从而保证其他待布线网在路径搜索过程中的自由度。
[0074]
进一步地，对线网队列中的下一待布线网展开候选路径搜索，重复上述步骤，直至所有待布线网搜索完毕，即可获得所有待布线网的候选路径。
[0075]
可选地，上述步骤s13中，基于设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息的步骤，包括：
[0076]
基于设计规则信息，分别检查每个待布线网中各个候选路线与其他待布线网中各个候选路线之间的违例情况，并在基础数据的违例数组中保存第一违例信息。
[0077]
设计规则检查是将待布线网的候选路径裁剪分割，形成多个矩形框，通过比较矩形框之间的相对位置，确定候选路径之间有无违例存在，示例性地，本实施例采用boost库存储候选路径的矩形框信息，boost库提供查找索引功能。
[0078]
需要说明的是，在对第k个待布线框的候选路线进行检查时，只需检查其与其他待布线框的候选路线之间是否存在违例、而无需检查第k个待布线框各个候选路线之间是否存在违例。另外，若第a个待布线网的第l1条候选路径与第b个待布线网的第l2、l3条候选路径同时存在违例，则上述两个违例情况均被记录，相应产生两个第一违例信息。
[0079]
下面以短路、不充分接触和线条间距检查为例，对违例情况的检查做进一步说明。
[0080]
图3是本发明实施例提供的设计规则检查的一种流程图。请参见图3，被检查的矩形框a是主体，其他被所索引到的矩形框b构成集合b，矩形框b称为客体，为避免同一线网的不同候选路径之间被误识产生违例，在设计规则检查前，先过滤掉集合b中与矩形框a属于同一待布线网不同候选路径的矩形框b。对于集合b剩余的矩形框b，若其与矩形框a相交，则进行短路检查和不充分接触检查；若其与矩形框a不相交，则进行线条间距检查。
[0081]
可选地，步骤s14中，根据第一违例信息构建价值函数和约束条件，求解最优路径的步骤，包括：
[0082]
根据第一违例信息构建价值函数：
[0083][0084]
式中，violation[c]表示违例数组中存储的第c条第一违例信息，c＝1,2，
…
，netsize，violation[c]＝netarray[a][m]*netarray[b][n]，netarray[a][m]、netarray[b][n]为引起第c条第一违例信息的两条候选路径，netarray[a][m]表示二维数组netarray中存储的第a个待布线网的第m条候选路径，netarray[b][n]表示二维数组netarray中存储的第b个待布线网的第n条候选路径，netarray[i][j]表示二维数组netarray中存储的第i个待布线网的第j条候选路径，i＝1,2,
…
，k，j＝1,2，
…
,l，wirelength[i][j]表示netarray[i][j]的金属走线长度，viacout[i][j]表示netarray[i][j]包含的通孔数量，w1、w2、w3均为预设权重；
[0085]
针对每个待布线网构建约束条件：
[0086]
netarray[i][1]+netarray[i][2]+...+netarray[i][maxnum]＝1；
[0087]
在约束条件下，使价值函数达到最小，计算得到每个待布线网的最优路径。
[0088]
具体而言，获取基础数据中的违例数组(violations)，违例数组中存储有多条第一违例信息，在构建价值函数时，需要找到每条第一违例信息对应的两个候选路径。例如，若索引到第c条第一违例信息由第a个待布线网的第m条候选路径与第b个待布线网的第n条候选路径产生，则需要找到上述第m条候选路径与第n条候选路径在数组netarray中对应的变量netarray[a][m]和netarray[b][n]。
[0089]
遍历违例数组中的viosize条第一违例信息，按照如下公式构建价值函数：
[0090][0091]
其中，w1＝500、w2＝0.5、w3＝2。
[0092]
接着构建约束条件，根据netarray中的一维变量的个数构建，netarray中的每个一维变量netarray[i]有如下约束：
[0093]
netarray[i][1]+netarray[i][2]+...+netarray[i][maxnum]＝＝1。
[0094]
然后利用cplex求解器求解约束条件下的价值函数，也就是说，在满足约束条件的同时，使价值函数要达到最小。求解结束后，若netarray[i][j]＝1，表示第i个待布线网的第j条候选路径被选为最优路径，若netarray[i][j]＝0表示第i个待布线网的第j条候选路径未被选为最优路径。
[0095]
图4是本发明实施例提供的待布线网的最优路径的示意图。如图4所示，a、b、c为三个待布线网，矩形框表示a、b、c三个待布线网的引脚，a1、a2、b1、b2、c1、c2表示候选路径。可以看出，第一违例信息为v[a1,b1]，v[a1,b2]，v[a1,c1]，v[a1,c2]，v[b1,c1]，v[b2,c2]，为了使价值函数达到最小，求解结果为待布线网a选择候选路径a2为最优路径，待布线网b选
择候选路径b1为最优路径，待布线网c选择候选路径c2。
[0096]
上述步骤s15中，基于最优路径输出布线结果的步骤，包括：
[0097]
删除线网队列中每个待布线网在基础数据中的互连信息，互连信息包括每个待布线网在上一次布线时的最优路径；
[0098]
将每个待布线网的最优路径写入基础数据中的互连信息；
[0099]
清空基础数据中的违例数组；
[0100]
基于设计规则信息以及当前的互连信息，对不同最优路径之间的违例情况进行检查，并在基础数据的违例数组中保存第二违例信息；
[0101]
判断违例数组是否为空；若否，则将存在违例的待布线网所在区域作为布线区域，并返回判断布线区域是否为第一次布线的步骤；若是，则根据当前的互连信息输出布线结果。
[0102]
针对更新过的基础数据做设计规则检查，首先将当前基础数据中储存有第一违例信息的违例数组清空，然后将本次设计规则检查得到的第二违例信息重新写入到违例数组当中。进一步地，判断违例数组是否为空；若为空，则根据更新过的基础数据输出布线结果；若不为空，则需要对存在违例的待布线网重新布线，此时返回步骤s12，生成新的线网队列。
[0103]
需要说明的是，输出的布线结果可以保存为一个文本文件，包含线网经过的金属层和使用的通孔类型，在金属层内的形状可用多个矩形框的顶点坐标表示。
[0104]
通过上述各实施例可知，本发明的有益效果在于：
[0105]
本发明提供了一种基于整数线性规划的超大规模集成电路布线方法，该方法将每个待布线网在搜索过程中产生的候选路径做了收集，并从这些候选路径中挑选最优路径，极大程度上解决了传统布线方案中不易布开、不能最大限度利用中间结果的问题；并且，本发明对设计规则的检查方式加以优化，可以同时检查多个待布线网、多条候选路径，为布线工具中设计规则检查的方式提供了新的思路。
[0106]
在本发明的描述中，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。
[0107]
参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。此外，本领域的技术人员可以将本说明书中描述的不同实施例或示例进行接合和组合。
[0108]
尽管在此结合各实施例对本技术进行了描述，然而，在实施所要求保护的本技术过程中，本领域技术人员通过查看所述附图、公开内容、以及所附权利要求书，可理解并实现所述公开实施例的其他变化。
[0109]
以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的
保护范围。

技术特征：
1.一种基于整数线性规划的超大规模集成电路布线方法，其特征在于，包括：根据所述布线区域内的障碍信息、待布线网信息、设计规则信息以及布线轨道信息，进行基础数据初始化；根据所述基础数据生成线网队列，并利用a*搜索算法，搜索所述线网队列中每个待布线网的候选路径；基于所述设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息；根据所述第一违例信息构建价值函数和约束条件，求解最优路径；基于所述最优路径输出布线结果。2.根据权利要求1所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，所述障碍信息包括布线时需要避开的金属层和障碍区域，所述待布线网信息包括待布线网的构成引脚、所述引脚的坐标以及所在金属层，所述设计规则信息包括最小线宽、最小线间距和最小通孔间距，所述布线轨道信息包括每一金属层的轨道数量与轨道间距。3.根据权利要求2所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，根据所述基础数据初始化生成线网队列的步骤，包括：判断所述布线区域是否为第一次布线；若是，则将所述布线区域中的所有线网作为待布线网，加入线网队列；反之，则将上一次布线时存在违例的线网作为待布线网，加入线网队列。4.根据权利要求3所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，利用a*搜索算法，搜索所述线网队列中每个待布线网的候选路径的步骤，包括：令k＝1，l＝1；针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径；增加所述第l条候选路径所经过的第一格点的权重、以及该第一格点的相邻格点的权重；所述相邻格点为第一格点预设邻域内的其它格点；统计所述第l条候选路径的通孔数量以及线网长度；判断l是否小于预设值l；若否，则令l＝l+1，并返回针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得第k个待布线网的l个候选路线，并进一步判断k是否小于所述线网队列中待布线网数量k；若k<k，则令k＝k+1，并返回针对所述线网队列中第k个待布线网，利用a*搜索算法搜索其第l条候选路径的步骤；反之，则获得所有待布线网的候选路线。5.根据权利要求4所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，利用a*搜索算法搜索其第l条候选路径的步骤之后，还包括：将第k个待布线网的第l条候选路线存储在基础数据的二维数组netarray中；获得第k个待布线网的l个候选路线的步骤之后，还包括：针对第k个待布线网，将其l个候选路线分别经过的第一格点的权重、以及每个第一格点的相邻格点的权重归零。6.根据权利要求3所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，基于所述设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息的步骤，包括：
基于所述设计规则信息，分别检查每个待布线网中各个候选路线与其他待布线网中各个候选路线之间的违例情况，并在基础数据的违例数组中保存第一违例信息。7.根据权利要求6所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，根据所述第一违例信息构建价值函数和约束条件，求解最优路径的步骤，包括：根据所述第一违例信息构建价值函数：式中，violation[c]表示违例数组中存储的第c条第一违例信息，c＝1,2，
…
，netsize，violation[c]＝netarray[a][m]*netarray[b][n]，netarray[a][m]、netarray[b][n]为引起所述第c条第一违例信息的两条候选路径，netarray[a][m]表示二维数组netarray中存储的第a个待布线网的第m条候选路径，netarray[b][n]表示二维数组netarray中存储的第b个待布线网的第n条候选路径，netarray[i][j]表示二维数组netarray中存储的第i个待布线网的第j条候选路径，i＝1,2,
…
，k，j＝1,2，
…
,l，wirelength[i][j]表示netarray[i][j]的金属走线长度，viacout[i][j]表示netarray[i][j]包含的通孔数量，w1、w2、w3均为预设权重；针对每个待布线网构建约束条件：netarray[i][1]+netarray[i][2]+...+netarray[i][maxnum]＝1；在所述约束条件下，使所述价值函数达到最小，计算得到每个所述待布线网的最优路径。8.根据权利要求7所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，netarray[i][j]＝1表示第i个待布线网的第j条候选路径被选为最优路径，netarray[i][j]＝0表示第i个待布线网的第j条候选路径未被选为最优路径。9.根据权利要求8所述的基于整数线性规划的超大规模集成电路布线方法，其特征在于，基于所述最优路径输出布线结果的步骤，包括：删除所述线网队列中每个待布线网在所述基础数据中的互连信息，所述互连信息包括所述每个待布线网在上一次布线时的最优路径；将所述每个待布线网的最优路径写入基础数据中的互连信息；清空基础数据中的违例数组；基于所述设计规则信息以及当前的互连信息，对不同最优路径之间的违例情况进行检查，并在基础数据的违例数组中保存第二违例信息；判断所述违例数组是否为空；若否，则将存在违例的待布线网所在区域作为布线区域，并返回判断所述布线区域是否为第一次布线的步骤；若是，则根据所述当前的互连信息输出布线结果。

技术总结
本发明公开了一种基于整数线性规划的超大规模集成电路布线方法，包括：根据布线区域内的障碍信息、待布线网信息、设计规则信息以及布线轨道信息，进行基础数据初始化；根据基础数据生成线网队列，并利用A*搜索算法，搜索线网队列中每个待布线网的候选路径；基于设计规则信息对不同候选路径之间的违例情况进行检查，并保存第一违例信息；根据第一违例信息构建价值函数和约束条件，求解最优路径；基于最优路径输出布线结果。本发明解决了传统布线方案中不易布开、不能最大限度利用中间结果的问题；并且，本发明对设计规则的检查方式加以优化，可以同时检查多个待布线网、多条候选路径，为布线工具中设计规则检查的方式提供了新的思路。的思路。的思路。


技术研发人员：彭琪 胡世哲 祁仲冬 朱樟明
受保护的技术使用者：西安电子科技大学
技术研发日：2023.06.25
技术公布日：2023/9/20