基于分支定界法的电路通道布线方法、装置及电子设备

摘要

本公开提供一种基于分支定界法的电路通道布线方法、装置及电子设备，其中，方法包括：在布线空间内构建二维网格；在所述二维网格中标记电路图中各个引脚的坐标；将所述电路图中相连的引脚作为引脚对，其中，所述电路图包含多个引脚对；根据分支定界法确定所述电路图中的多个引脚对对应的布线路径；根据各个引脚对的布线路径绘制电路布线图。能够利用分支定界法对电路图中各个相连引脚对进行布线路径的选取，选取的布线路径能够在不会引起断路或短路的情况下，保证布线路径最优，进而减小连接电线引入的寄生电阻对整个电路性能的影响。

说明书

技术领域

本公开涉及电路布线技术领域，尤其涉及一种基于分支定界法的电路通道布线方法、装置及电子设备。

背景技术

集成电路是信息产业的核心部分，集成电路是利用半导体技术把电子元件集成在一起的具有特定功能的电路，已广泛应用于生产生活的方方面面。随着技术的发展，集成电路内部的元器件数目已达到十亿级别，需要借助专用计算机软件才能完成电路设计与实现，该类软件统称为电子设计自动化（Electronic Design Automation, EDA）工具。

在进行电路导线的布设时，在不引起断路或短路的情况下，需要最小化布线的长度，减少导线电阻的影响，传统的电路通道布线是直接按照最小化布线长度的方式进行布线的，但是这种方式容易出现短路或断路的情况。

发明内容

有鉴于此，本公开的目的在于提出一种以便克服上述问题或者至少部分地解决上述问题的基于分支定界法的电路通道布线方法、装置及电子设备。

基于上述目的，本公开的第一方面提供了一种基于分支定界法的电路通道布线方法，包括：

在布线空间内构建二维网格；

在所述二维网格中标记电路图中各个引脚的坐标；

将所述电路图中相连的引脚作为引脚对，其中，所述电路图包含多个引脚对；

根据分支定界法确定所述电路图中的多个引脚对对应的布线路径；

根据各个引脚对的布线路径绘制电路布线图。

基于上述目的，本公开的第二方面提供了一种基于分支定界法的电路通道布线装置，包括：

网络构建模块，用于在布线空间内构建二维网格；

标记模块，用于在所述二维网格中标记电路图中各个引脚的坐标；

引脚对确定模块，用于将所述电路图中相连的引脚作为引脚对，其中，所述电路图包含多个引脚对；

路径确定模块，用于根据分支定界法确定所述电路图中的多个引脚对对应的布线路径；

布图模块，用于根据各个引脚对的布线路径绘制电路布线图。

基于上述目的，本公开的第三方面提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如第一方面所述的方法。

从上面所述可以看出，本公开提供的基于分支定界法的电路通道布线方法、装置及电子设备，能够利用分支定界法对电路图中各个相连引脚对进行布线路径的选取，选取的布线路径能够在不会引起断路或短路的情况下，保证布线路径最优，进而减小连接电线引入的寄生电阻对整个电路性能的影响。

附图说明

为了更清楚地说明本公开或相关技术中的技术方案，下面将对实施例或相关技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本公开的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本公开实施例的基于分支定界法的电路通道布线方法的流程图；

图2为本公开实施例的基于分支定界法的电路通道布线方法中步骤104的具体流程图；

图3为本公开实施例的基于分支定界法的电路通道布线方法中步骤104的另一个具体流程图；

图4为本公开实施例的基于分支定界法的电路通道布线方法中步骤104的在一个具体流程图；

图5为本公开实施例的一个布线空间的示意图；

图6为图5中引脚对[3,1]最短路径示意图；

图7为图5中各个引脚对的一个布线解的示意图；

图8为本公开实施例的另一个空白布线空间的示意图；

图9为图8中引脚对[1,1]的布线路径的示意图；

图10为图8中引脚对[2,2]的引脚（1,4）的可达路径搜索树的示意图；

图11为图8中引脚对[2,2]的引脚（4,3）的可达路径搜索树的示意图；

图12为图8中引脚对[2,2]的布线路径的示意图；

图13为图8中引脚（1,5）的可达路径的搜索树的示意图；

图14为图8中引脚对[3,3]的布线路径的示意图；

图15为表1中各个引脚对的布线路径的示意图；

图16为合格通孔间距设置示意图；

图17为待布线的空白引脚示意图；

图18为图17中引脚对[1,1]布线路径的示意图；

图19为图17中引脚（1,4）的可达路径的搜索树的示意图；

图20为图17中引脚对[2,2]布线路径的示意图；

图21为图17中引脚号2的上引脚(1,4)的可达路径的搜索树的示意图；

图22为图17中引脚号2的下引脚(6,3)的可达路径的搜索树的示意图；

图23为图17中引脚（1,4）的可达路径的搜索树的示意图；

图24为图17中引脚号3的布线路径的示意图；

图25为死锁问题的布线路径的示意图；

图26为表1中通孔间设定预设距离的布线路径的示意图；

图27为本公开实施例的基于分支定界法的电路通道布线装置的结构框图；

图28为本公开实施例的电子设备的硬件结构示意图。

具体实施方式

为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，并参照附图，对本公开进一步详细说明。

需要说明的是，除非另外定义，本公开实施例使用的技术术语或者科学术语应当为本公开所属领域内具有一般技能的人士所理解的通常意义。本公开实施例中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。“包括”或者“包含”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。“连接”或者“相连”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电性的连接，不管是直接的还是间接的。

集成电路设计由多个阶段组成，其中一个重要阶段称为“物理设计”，先将器件摆放在合适的位置，然后用金属线连接器件实现连接关系。其中，后者称为“布线”，布线是EDA需要解决的重要问题。简单而言，假设布线区域由方格组成，金属线允许沿着直线或直角（方格）放置，连接指定的方格（引脚）而不引起断路或短路，该过程称为“布线”。对于只有一层的金属布线，为了不引起短路，则不允许线路出现交叉。然而实际中，集成电路大多会采用多个金属层，不同的金属层处在不同的高度，相邻层之间需要用通孔连通，这样不同金属层通过共用通孔而不引起短路。在进行导线的布设时，在不引起断路或短路的情况下，需要最小化布线的长度，减少电阻的影响。

本公开侧重于解决“布线”问题中的一个特例：“通道布线”。本公开首先从最简单的单层“通道布线”，到包含两个金属层的“通道布线”，以及当通孔之间的距离受到约束时的两个金属层的“通道布线”，针对这三个不同的问题进行“通道布线”的设计并求解。其中，“通道”是指一个横向的布线区域，在布线区域内需用金属线将相应的引脚连通起来。

如图1所示，本实施了的基于分支定界法的电路通道布线方法，包括：

步骤101，在布线空间内构建二维网格。

在该步骤中，布线空间可以一层布线空间也可以是多层布线空间。构建的二维网络由大小相同的方格构成，方格的宽度可根据实际需要进行对应调整，这样形成的二维网络由n×m个方格构成，其中，n为二维网络横向方格数量，m为二维网络纵向方格数量。

步骤102，在二维网格中标记电路图中各个引脚的坐标。

在该步骤中，根据电路图进行布线之前，需要根据电路图中各个电学元件的引脚的位置在二维网络中进行标记。并且标记之后，将各个引脚的坐标处的方格进行锁定，禁止连线通过。同时如果是进行多层通道布线的话，针对各个引脚坐标的方格也禁止设置通孔。

步骤103，将电路图中相连的引脚作为引脚对，其中，电路图包含多个引脚对。

在该步骤中，将相连引脚对的坐标值进行列表存储，以供按照顺序或者随机从列表中调出对应的引脚对进行布线。

步骤104，根据分支定界法确定电路图中的多个引脚对对应的布线路径。

在该步骤中，利用分支定界法为引脚对寻找对应的布线路径，寻找到的路径可能是一条也可能是多条，如果是多条，则以任意一条布线路径为准对下一个引脚对再利用分支定界算法寻找布线路径。这样一个电路图可能就能对应找到多组布线路径。

步骤105，根据各个引脚对的布线路径绘制电路布线图。

在该步骤中，如果电路图对应的布线路径有至少一组，则可以对应绘制至少一个电路布线图，进而将这至少一个电路布线图呈现给用户，以供用户从中选取一个最为满意的电路布线图进行实际布线。

通过上述方案，能够利用分支定界法对电路图中各个相连引脚对进行布线路径的选取，选取的布线路径能够在不会引起断路或短路的情况下，保证布线路径最优，进而减小连接电线引入的寄生电阻对整个电路性能的影响。

在具体实施例中，步骤104具体包括：

步骤1041，从多个引脚对中选取一个目标引脚对，并利用分支定界法确定目标引脚对的布线路径。

在该步骤中，从引脚对的存储列表中随机或者顺序选出一个引脚对作为第一个目标引脚对，利用分支定界法确定出该第一目标引脚对的布线路径A，然后以该布线路径A为父节点构建空间树。并且该布线路径A可能为多个，例如A1、A2和A3，则分别以A1、A2和A3为父节点构建三个空间树。

步骤1042，将目标引脚对的布线路径进行禁止交叉连接锁定，获取下一个目标引脚对，利用分支定界法确定下一个目标引脚对的布线路径，并不断迭代该过程直至电路图中的引脚对全部确定出对应的布线路径。

在该步骤中，将上述得到的根节点的布线路径进行禁止交叉连接锁定（即，以该布线路径A为“围墙”），继续采用分支定界法寻找下一个目标引脚对的布线路径B，并将布线路径B放在父节点A的子节点上。其中，如果找到的布线路径有多个（B1、B2），则分别作为父节点A的子节点。

然后再以布线路径B作为父节点，继续采用分支定界法寻找下一个目标引脚对的布线路径C，如此循环直至电路图中的引脚对全部确定出对应的布线路径。

再然后，从最后的子节点Z的父节点Y为子节点向上追溯查找上一个父节点X，判断对应的父节点X是否存在多个子节点，若不存在则继续向上查找。如果查找到W存在多个子节点X1、X2（其中，X1为追溯路径对应的子节点，X1已经有对应的子节点）。将剩余的子节点X2为父节点，将X2布线路径进行禁止交叉连接锁定，利用分支定界法寻找下一个引脚对的布线路径Y1，直至最后一个引脚对的布线路径确定完。不断重复上述过程，直至整个空间树的各个分支从根节点到末端节点都能包含所有的引脚对。

通过上述方案，对应构建一个或多个空间树，每个空间树对应多组包含电路图中所有引脚对的布线路径，这样就可以将每组布线路径进行整理，进行布线绘制，并呈现给用户，以供用户选择。或者构建的空间树只有一个，该空间树只有一个分支走向，证明只有一组包含电路图中所有引脚对的布线路径，则用户就无需选择，直接根据该组布线路径得到的电路布线图进行电路布线即可。

在具体实施例中，在步骤1042之前，该方法还包括：

步骤1042’，设置设定条件为：

其中，

在该步骤中，在进行“通道布线”的时候，两条布线之间不能存在交叉，也就是第一个引脚对和第二个引脚对的列坐标相减的乘积之和要大于0，即如果第一条布线的上引脚的列坐标小于第二条布线的上引脚的列坐标，那么第一条布线的下引脚的列坐标也必须要小于第二条布线的下引脚的列坐标，否则会产生交叉，会引起短路。

如图5所示，上引脚数字3所在的列坐标小于上引脚数字5所在的列坐标（在这个例子中，列坐标等于引脚的数字），下引脚数字1所在的列坐标小于下引脚数字4所在的列坐标，所以如果想让上引脚3和下引脚4相连，上引脚5和下引脚1相连，

另外，s.t.是subject to 的缩写，表示约束条件。

在进行布线路径选择过程中需要按照该设定条件进行约束，能够避免进行布线时两条布线出现交叉短路的情况。

在具体实施例中，如图3所示步骤104具体还包括：

步骤104a，以引脚对中的一个引脚的坐标为基准点，以另一个引脚的坐标为终结点。其中，引脚对代指电路图中的任意一个需要进行布线路径选择的引脚对。

步骤104b，从基准点可移动的至少一个方位点中确定距离终结点最近的方位点作为位移点，并舍弃其余方位点，以位移点为新的基准点，不断迭代该过程直至位移至终结点，确定出引脚对对应的至少一个位移路线。

步骤104c，将确定出的至少一个位移路线作为引脚对的布线路径。

在上述方案中，可以从基准点开始建立一个空间树，对应可移动的方位点作为活结点。每一个活结点只有一次机会成为扩展结点, 活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。从活结点表中选择下一扩展结点的不同方式导致了不同的分支定界法，具体包括：队列式(FIFO，First Input First Output) 分支定界法和/或优先队列(PQ，Priority queuing)式分支定界法。其中，队列式分支定界法具体根据引脚对对应的排列顺序进行依次布线路径的查找过程。优先队列式分支定界法具体按照引脚对对应的优先级的顺序进行布线路径的查找过程。

通过上述方案，在电路图的各个引脚对全部对应查找到布线路径的同时，还能保证能够将电路图对应的所有布线最优解全部查找出来，避免出现遗漏的情况，并且查找到的布线路径可能有多组，用户可以根据实际需要进行选择。

在具体实施例中，以目标引脚对的布线路径为父节点，下一个目标引脚对的布线路径为子节点，目标引脚对代指电路图包含的多个引脚对中的任意一个。

则步骤1042中利用分支定界法确定下一个目标引脚对的布线路径，具体包括：

确定利用分支定界法得到的子节点的布线路径为零个，以父节点为子节点利用回溯法向上查找对应的上一个父节点，并将父节点删除，直至确定上一个父节点存在多个子节点，则从剩余子节点中选取一个子节点作为父节点，利用分支定界法确定对应子节点的布线路径。

在该步骤中，若一个父节点存在多个子节点，则以任意一个子节点为父节点继续进行扩展，剩余子节点作为活结点存储在活结点存储库中。

基于上述条件，如果找不到子节点对应引脚对的布线路径，需要将该子节点对应的父节点删除，并利用回溯法进行向上追溯查找确定上一个父节点在活结点存储库中是否存在对应的子节点。若有，则从活结点存储库中调取对应子节点，同时在活结点存储库中删除调取出来的子节点，以调取出来的子节点作为父节点，利用分支定界法确定对应子节点的布线路径。若没有，则将该父节点删除，继续向上追溯上一个父节点，直至确定出的上一个父节点在活结点存储库中是否存在对应的子节点，并按照上述方式进行布线路径查找。如果查找过程中又发现找不到子节点对应引脚对的布线路径，则不断重复上述过程。

在具体实施例中，这样不断重复过程中，可能存在一种情况就是，遍历活结点存储库中所有的活结点后仍然无法找到对应的布线路径。即，引脚对未找到对应的布线路径，确定引脚对为不可达引脚对。这种情况需要打通孔利用两层或多层布线空间进行布线，并预先设置通孔集合为空集。

则如图4所示，步骤104具体还包括：

步骤104d，判断通孔集合是否为非空集，是则进入步骤104e，否则进入步骤104g。

步骤104e，判断从通孔集合中是否查找到不可达引脚对的两个引脚能够到达的通孔坐标，若是，则进入步骤104f，否则进入步骤104g。

步骤104f，将查找到的不可达引脚对的两个引脚能够到达的通孔坐标作为不可达引脚对的通孔坐标。

步骤104g，利用回溯法为不可达引脚对确定对应的通孔坐标，将通孔坐标添加至通孔集合中。

步骤104h，确定不可达引脚对的两个引脚分别到达通孔坐标的路径为第一层布线空间的布线路径，以及两个通孔坐标的连接路径为第二层布线空间的布线路径，其中，第二层布线空间指代除第一层布线空间之外的其他至少一个布线空间。

步骤104i，利用分支定界算法查找下一个引脚对的布线路径，直至电路图中的引脚对全部确定出对应的布线路径。

在上述步骤中，有些集成电路是无法采用一层布线空间完成布线的，会采用多层布线空间，不同层的布线空间处在不同的高度，相邻层之间使用通孔连通，这样不同布线空间可共用该通孔而不引起短路。

以两个布线空间层为例在布线空间进行“通道布线”，通过结合分支定界算法以及回溯法，确定引脚对之间的最短可达路径以及通孔位置的确定，使得总布线长度最小。

具体为：

首先，任意选择一个引脚对P1，利用分支定界法在第一层布线空间内得到对应的布线路径L1。

然后，利用分支定界法依次寻找其他引脚对的布线路径，发现引脚对P2之间是不可达的，确定引脚对2为不可达引脚对，需要寻找通孔位置，利用通孔与第二层布线空间进行连接布线。并不断重复该步骤直至电路图中全部的引脚对都找到对应的布线路径，或者对应活结点存储库中没有活结点。

最后，根据各个引脚对的布线路径绘制电路布线图。

通过上述方案，能够利用多层布线空间进行布线设计，这样避免一些电路图由于无法找到对应的布线路径，而导致无法进行电路布线的情况。并且本公开是将分支定界法和回溯法进行结合选择确定的通道位置更加合理，基于对应的通道进行布线设计更加符合实际需要，在保证电路图正常布线的同时，保证电路图的连接导线能够达到最短，降低连接导线产生的附加电阻的影响。

在具体实施例中，步骤104d具体包括：

根据不可达引脚对的两个引脚的可达路径分别构建对应的搜索树，其中，将不可达引脚对的两个引脚的可达坐标作为搜索树的叶子节点；计算两个搜索树的叶子节点之间的节点距离，其中，得到的节点距离为至少一个；将距离值最小的节点距离对应的两个叶子节点作为通孔坐标，并将通孔坐标添加至通孔集合中。

在上述步骤中，另外如果通孔集合为非空集合，则计算不可达引脚对的两个引脚到达通孔集合中任意两个通孔的最短路径，进而从通孔集合中寻找该不可达引脚对对应的通孔位置，如果找不到，则再利用上述步骤104d找对应的通孔位置，并将找到的通孔位置添加至通孔集合中。

通过上述方式，能够保证找到的通孔距离最合适，同时还能尽量减少打通孔的数量。

在具体实施例中，针对一些特定的布线需要，两个相邻通孔之间不能距离太近，因此需要预先设置两个通孔之间的距离要大于等于预设距离

则步骤104d中“将距离值最小的节点距离对应的两个叶子节点作为通孔坐标，并将通孔坐标添加至通孔集合中”具体还包括：

将大于等于预设距离的节点距离作为待选节点距离，其中，待选节点距离为至少一个；从至少一个待选节点距离中选择距离值最小的待选节点距离作为最终节点距离；将最终节点距离对应的两个叶子节点作为通孔坐标，并将通孔坐标添加至通孔集合中。

通过上述方案，能够利用预设距离来限定通孔之间的距离，保证两个相邻通孔不会距离太近，避免两个通孔距离太近对布线空间以及连接导线造成影响。

基于上述实施例的描述，本公开的另一个实施例提出的基于分支定界法的电路通道布线方法，通过最小化布线的长度，减小金属线引入的寄生电阻对电路的影响。针对三个不同的问题，最简单的单层“通道布线”，到包含两个金属层的“通道布线”，以及当通孔之间的距离受到约束时的两个金属层的“通道布线”，从简单到复杂、层层递进进行“通道布线”的设计。

分支定界法（branch and bound）是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

分支定界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。与回溯法不同，在搜索问题的解空间树时，每一个活结点只有一次机会成为扩展结点, 活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。从活结点表中选择下一扩展结点的不同方式导致了不同的分支定界法，最常见的有队列式(FIFO) 分支定界法和优先队列(PQ) 式分支定界法两种。本实施例基于分支定界和回溯法解决上述的三个“通道布线”问题。

具体解决上述问题的应用场景的实现过程如下：

一、单层通道布线

假设布线空间由

本发明以图5中的3对引脚数据为例进行单层“通道布线”的求解说明，3对引脚的上引脚和下引脚坐标分别是[3,1]、[5,4]、[6,7]，布线空间为

在进行“通道布线”的时候，两条布线之间不能存在交叉，也就是第一个引脚对和第二个引脚对的列坐标相减的乘积要大于0，即如果第一条布线的上引脚的列坐标小于第二条布线的上引脚的列坐标，那么第一条布线的下引脚的列坐标也必须要小于第二条布线的下引脚的列坐标，否则会产生交叉，会引起短路。如图5所示，上引脚数字3所在的列坐标小于上引脚数字5所在的列坐标（在这个例子中，列坐标等于引脚的数字），下引脚数字1所在的列坐标小于下引脚数字4所在的列坐标，所以如果想让上引脚3和下引脚4相连，上引脚5和下引脚1相连，

定义

同时使用

针对如图5所示的单层“通道布线”问题，步骤如下：

Step 1：首先，考虑引脚坐标对[3,1]的连接问题，引脚对[3,1]在

Step 2：其次，针对引脚对[5,4]的连接问题，在引脚对[3,1]已经布过线这个约束的基础上，即引脚对[3,1]的连线可以看作网格中的一道“围墙”，并且设定已经布线的方格将会被锁定，不允许其它线路穿过，否则会形成短路，在这个约束的基础上，本实施例采用分支定界算法，找到引脚对[5,4]之间的最短路径，并将其连接起来，作为引脚对[5,4]的布线。

Step 3：最后，在引脚对[3,1]和引脚对[5,4]连线“围墙”的基础上，继续采用分支定界算法，找到引脚对[3,1]之间的最短路径，那么整个布线问题就得到解决。如图7所示是图5中

二、两层通道布线

实际情况中，有些集成电路是无法采用一层金属（即，一层布线空间）完成布线的，会采用多个金属层（即，多层布线空间），不同的金属层处在不同的高度，相邻层之间使用通孔连通，这样不同金属层可共用该通孔而不引起短路。本实施例以两个金属层（即，两层布线空间）为例在布线空间进行“通道布线”，通过结合分支定界算法以及回溯法，确定引脚对之间的最短可达路径以及通孔位置的确定，使得总布线长度最小。图8所示，1,2,3分别表示上下的引脚编号，设定图8上下引脚编号相同的引脚需要连接起来，同时设定一个通孔的电阻等于5 个方格的导线。

设定该两层金属布线是在一个

表1 目标布局空间大小及上下引脚连接关系

首先，本实施例随机初始化任意一个引脚对得到其布线为

Step1：首先，初始化任意一对引脚

Step2：利用分支限界算法依次寻找其他引脚的最短可达路径。

通过搜索发现引脚2之间是不可达的，因此需要第二层金属片使之可达。通过搜索通孔集合发现此时

通孔位置的选择采用如下方式：

（1）利用广度搜索优先寻找引脚2上下引脚，此时用坐标表示(1,4)和(4,3)可达路径，产生如图10和图11所示的搜索树。

（2）通过引脚的搜索树可以利用回溯法选取通孔的位置。首先从叶子节点中进行选取，可以得到下引脚(1,4)的叶子节点有(3,1)，(3,2)和(3,3)作为通孔的候选集，上引脚(1,4)的叶子节点有(1,3)作为通孔的候选集

最后再次寻找引脚3之间的布线路径，通过广度搜索算法可以发现引脚3之间是不可达的。那么需要通过2层金属板实现其布线，则需要通孔。首先通过索引通孔集合，查找引脚3的上引脚(1,5)和下引脚(4,2)到通孔集合

表2 引脚(1,5) 和引脚(4,2)到通孔的距离

因此，本实施例选择通孔(3,2)作为下引脚(4,2)的通孔，上引脚(1,5)没有可达的通孔则需要重新打一个新的通孔。新的通孔的选择采取上述方法，首先采用广度搜索优先的方法遍历引脚(1,5)的搜索树如图13所示。

首先选取叶子节点(4,7)，(3,6)，(2,6)，(1,7)作为通孔的备选集，计算这些位置到通孔(3,2)的最短路径，则可以得到

针对上述布局，通孔的选择存在如下情况，如果上引脚和下引脚均可以在通孔候选集中找到相应的可达通孔，则做出如下假设。如果通过该通孔在上层金属板的布线距离满足如下公式，则我们会重新打2个通孔进行布线：

其中

综上，完成了表格2中所有引脚的连接，得到的通道布线结果如图15所示：

三、通孔之间距离约束下的两层通道布线

随着集成电路尺寸缩小，假设新的通孔制造工艺要求任意两个通孔的间距必须大于等于2个格点，在此假设下，根据表2中的布线要求重新进行两个金属层的“通道布线”。

首先引入欧式距离如下公式所示，作为两个通孔之间的空间距离。

其中

如果要满足上述条件，则金属板的尺寸的也需要足够的大，如果金属板的尺寸过小则无法找到合适的通孔。本实施例假设金属板的宽度至少是

对图17所示的示例进行布线，在选取通孔时，本实施例的原则是尽可能向右的方式选取通孔，以免影响左边的引脚选择。

引脚1的布线：

首先初始化任意一对引脚

引脚2的布线：

然后利用分支限界算法依次寻找其他引脚对的最短可达路径。通过搜索发现引脚2之间是不可达的，因此需要第二层金属片使之可达。通过搜索通孔集合发现此时是空集，因此没有可利用的通孔，于是需要在电路板上新打两个通孔使引脚2之间可以连接。

一般的，如果路径和欧式距离均等于最小的阈值，那么这个通孔绝对是最优的通孔，这种条件下满足的是通孔在同一行或者同一列上。因此本实施例采用如下方法寻找最优的通孔，首先上引脚(1,4)进行深度优先搜索以此作为候选通孔，然后找在候选通孔横向或者纵向上欧式距离为阈值的四个位置寻找是否存在下引脚(6,3)可达的路径，坐标(1,4)按照图19所示的深度搜索优先的顺序进行寻找，当搜索到(1,3)作为上引脚(1,4)的候选集时，与(1,3)有关的位置为(1,6)，(4,3)。将(1,6)和(4,3)作为下引脚(6,3)的通孔候选集，然后用分支限界算法寻找下引脚(6,3)和候选集的路径，得到

引脚2之间的布线

针对引脚2的布局，如果存在特殊情况即遍历完所有上引脚(1,4)的上下左右的位置，均没有找到下引脚(6,3)的可达通孔位置，则采用如下方式：

通过广度搜索优先的方法得到引脚2的上引脚(1,4)和下引脚(6,3)的搜索树，如图21和图22所示。

首先从叶子节点中进行选取，可以得到上引脚(1,4)的叶子节点有(2,2)，(2,3)，(6,6),(1,6)作为通孔的候选集，下引脚(6,3)的叶子节点有(5,4)，(4,1)，(4,2)，(4,4)作为通孔的候选集。分别计算上引脚通孔候选集和下引脚通孔候选集之间的路径

表3叶子节点之间的路径距离和欧式距离

在满足欧式距离

引脚3的布线：

然后我们寻找第3个引脚的布线，通过分支限界算法可以发现引脚3之间是不可达的。那么需要通过2层金属板实现其布线，则需要通孔。首先通过索引通孔集合，查找引脚3的上引脚(1,5)和下引脚(6,2)到通孔集合

表4 上下引脚到通孔集合的距离

因此，我们选择通孔(3,2)作为下引脚(4,2)的通孔，上引脚(1,5)没有可达的通孔则需要重新打一个新的通孔。新的通孔方法首先确定在通孔(4,3)上下左右4个方位上欧式距离为

如果通孔(4,3)其上下左右均没有合适的通孔位置，则采用如下方式：利用深度搜索优先的方式一次遍历下引脚(1,5)可达的位置，图23所示的搜索树，计算遍历到的位置到通孔(4,3)的在满足欧式距离情况下，路径最短的位置作为最优通孔位置。

通过搜索得到的结果如表5所示：

表5 搜索结果

当排除(4,6)的位置的时候，有两个(3,6)和(5,6)。然后，搜索通孔集合，查找这两个位置与其他通孔是否满足欧式距离的要求

死锁问题

如果引脚引起死锁问题如图25所示，即图中☆号代表的引脚无论如何找不到可达的通孔，因为左上通孔的位置与引脚的候选位置排斥，则将通孔集合

布线结果

针对表格1的布线要求，布线结果如下：

例如，布线要求如表6所示时，此时采用相同的方法得到的布线结果如图26所示：

表6 目标布局空间及需要连接的引脚对

需要说明的是，本公开实施例的方法可以由单个设备执行，例如一台计算机或服务器等。本实施例的方法也可以应用于分布式场景下，由多台设备相互配合来完成。在这种分布式场景的情况下，这多台设备中的一台设备可以只执行本公开实施例的方法中的某一个或多个步骤，这多台设备相互之间会进行交互以完成所述的方法。

需要说明的是，上述对本公开的一些实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于上述实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。

基于与上述各个实施例中基于分支定界法的电路通道布线方法的同一发明构思，本实施例提出基于分支定界法的电路通道布线装置，如图27所示，该装置包括：

网络构建模块21，用于在布线空间内构建二维网格；

标记模块22，用于在二维网格中标记电路图中各个引脚的坐标；

引脚对确定模块23，用于将电路图中相连的引脚作为引脚对，其中，电路图包含多个引脚对；

路径确定模块24，用于根据分支定界法确定电路图中的多个引脚对对应的布线路径；

布图模块25，用于根据各个引脚对的布线路径绘制电路布线图。

在具体实施例中，路径确定模块24具体包括：

选取单元，用于从多个引脚对中选取一个目标引脚对，并利用分支定界法确定目标引脚对的布线路径；

路径确定单元，用于获取下一个目标引脚对，利用分支定界法确定下一个目标引脚对满足设定条件的布线路径，并不断迭代该过程直至电路图中的引脚对全部确定出对应的布线路径。

在具体实施例中，该装置还包括：

条件设置模块，设置设定条件为：

其中，

在具体实施例中，路径确定模块24具体还包括：

引脚坐标确定单元，用于以引脚对中的一个引脚的坐标为基准点，以另一个引脚的坐标为终结点；

位移确定单元，用于从基准点可移动的至少一个方位点中确定距离终结点最近的方位点作为位移点，并舍弃其余方位点，以位移点为新的基准点，不断迭代该过程直至位移至终结点，确定出目标引脚对对应的至少一个位移路线；将确定出的至少一个位移路线作为引脚对的布线路径。

在具体实施例中，以目标引脚对的布线路径为父节点，下一个目标引脚对的布线路径为子节点，目标引脚对代指电路图包含的多个引脚对中的任意一个；

则路径确定单元具体用于：

确定利用分支定界法得到的子节点的布线路径为零个，以父节点为子节点利用回溯法向上查找对应的上一个父节点，并将父节点删除，直至确定上一个父节点存在多个子节点，则从剩余子节点中选取一个子节点作为父节点，利用分支定界法确定对应子节点的布线路径。

在具体实施例中，引脚对未找到对应的布线路径，确定引脚对为不可达引脚对，利用多层布线空间进行布线，并预先设置通孔集合为空集；

路径确定模块24具体还包括：

判断单元，用于确定通孔集合为非空集，从通孔集合中查找不可达引脚对的两个引脚能够到达的通孔坐标作为不可达引脚对的通孔坐标；或者，

判断单元，还用于确定通孔集合为空集或确定通孔集合中未找到不可达引脚对的通孔坐标，利用回溯法为不可达引脚对确定对应的通孔坐标，将通孔坐标添加至通孔集合中；

路径确定单元，还用于确定不可达引脚对的两个引脚分别到达通孔坐标的路径为第一层布线空间的布线路径，以及两个通孔坐标的连接路径为第二层布线空间的布线路径，其中，第二层布线空间指代除第一层布线空间之外的其他至少一个布线空间；利用分支定界算法查找下一个引脚对的布线路径，直至电路图中的引脚对全部确定出对应的布线路径。

在具体实施例中，判断单元具体包括：

构建单元，用于根据不可达引脚对的两个引脚的可达路径分别构建对应的搜索树，其中，将不可达引脚对的两个引脚的可达坐标作为搜索树的叶子节点；

计算单元，用于计算两个搜索树的叶子节点之间的节点距离，其中，得到的节点距离为至少一个；

添加单元，用于将距离值最小的节点距离对应的两个叶子节点作为通孔坐标，并将通孔坐标添加至通孔集合中。

在具体实施例中，添加单元还用于：

将大于等于预设距离的节点距离作为待选节点距离，其中，待选节点距离为至少一个；从至少一个待选节点距离中选择距离值最小的待选节点距离作为最终节点距离；将最终节点距离对应的两个叶子节点作为通孔坐标，并将通孔坐标添加至通孔集合中。

为了描述的方便，描述以上装置时以功能分为各种模块分别描述。当然，在实施本公开时可以把各模块的功能在同一个或多个软件和/或硬件中实现。

上述实施例的装置用于实现前述任一实施例中相应的基于分支定界法的电路通道布线方法，并且具有相应的方法实施例的有益效果，在此不再赘述。

基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上任意一实施例所述的基于分支定界法的电路通道布线方法。

图28示出了本实施例所提供的一种更为具体的电子设备硬件结构示意图， 该设备可以包括：处理器1010、存储器1020、输入/输出接口1030、通信接口1040和总线 1050。其中处理器1010、存储器1020、输入/输出接口1030和通信接口1040通过总线1050实现彼此之间在设备内部的通信连接。

处理器1010可以采用通用的CPU（Central Processing Unit，中央处理器）、微处理器、应用专用集成电路（Application Specific Integrated Circuit，ASIC）、或者一个或多个集成电路等方式实现，用于执行相关程序，以实现本说明书实施例所提供的技术方案。

存储器1020可以采用ROM（Read Only Memory，只读存储器）、RAM（Random AccessMemory，随机存取存储器）、静态存储设备，动态存储设备等形式实现。存储器1020可以存储操作系统和其他应用程序，在通过软件或者固件来实现本说明书实施例所提供的技术方案时，相关的程序代码保存在存储器1020中，并由处理器1010来调用执行。

输入/输出接口1030用于连接输入/输出模块，以实现信息输入及输出。输入输出/模块可以作为组件配置在设备中（图中未示出），也可以外接于设备以提供相应功能。其中输入设备可以包括键盘、鼠标、触摸屏、麦克风、各类传感器等，输出设备可以包括显示器、扬声器、振动器、指示灯等。

通信接口1040用于连接通信模块（图中未示出），以实现本设备与其他设备的通信交互。其中通信模块可以通过有线方式（例如USB、网线等）实现通信，也可以通过无线方式（例如移动网络、WIFI、蓝牙等）实现通信。

总线1050包括一通路，在设备的各个组件（例如处理器1010、存储器1020、输入/输出接口1030和通信接口1040）之间传输信息。

需要说明的是，尽管上述设备仅示出了处理器1010、存储器1020、输入/输出接口1030、通信接口1040以及总线1050，但是在具体实施过程中，该设备还可以包括实现正常运行所必需的其他组件。此外，本领域的技术人员可以理解的是，上述设备中也可以仅包含实现本说明书实施例方案所必需的组件，而不必包含图中所示的全部组件。

上述实施例的电子设备用于实现前述任一实施例中相应的基于分支定界法的电路通道布线方法，并且具有相应的方法实施例的有益效果，在此不再赘述。

基于同一发明构思，与上述任意实施例方法相对应的，本公开还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令用于使所述计算机执行如上任一实施例所述的基于分支定界法的电路通道布线方法。

本实施例的计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存（PRAM）、静态随机存取存储器（SRAM）、动态随机存取存储器（DRAM）、其他类型的随机存取存储器（RAM）、只读存储器（ROM）、电可擦除可编程只读存储器（EEPROM）、快闪记忆体或其他内存技术、只读光盘只读存储器（CD-ROM）、数字多功能光盘（DVD）或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。

上述实施例的存储介质存储的计算机指令用于使所述计算机执行如上任一实施例所述的基于分支定界法的电路通道布线方法，并且具有相应的方法实施例的有益效果，在此不再赘述。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围（包括权利要求）被限于这些例子；在本公开的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本公开实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。

另外，为简化说明和讨论，并且为了不会使本公开实施例难以理解，在所提供的附图中可以示出或可以不示出与集成电路（IC）芯片和其它部件的公知的电源/接地连接。此外，可以以框图的形式示出装置，以便避免使本公开实施例难以理解，并且这也考虑了以下事实，即关于这些框图装置的实施方式的细节是高度取决于将要实施本公开实施例的平台的（即，这些细节应当完全处于本领域技术人员的理解范围内）。在阐述了具体细节（例如，电路）以描述本公开的示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下或者这些具体细节有变化的情况下实施本公开实施例。因此，这些描述应被认为是说明性的而不是限制性的。

尽管已经结合了本公开的具体实施例对本公开进行了描述，但是根据前面的描述，这些实施例的很多替换、修改和变型对本领域普通技术人员来说将是显而易见的。例如，其它存储器架构（例如，动态RAM（DRAM））可以使用所讨论的实施例。

本公开实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本公开实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本公开的保护范围之内。