电路版图的快速布线方法、装置、介质及设备与流程

本发明涉及电路版图设计领域，特别是涉及一种电路版图的快速布线方法、装置、介质及设备。

背景技术：

1、在电路版图设计中，在对数量众多的布线起点和布线终点进行布线，即在各布线起点和布线终点之间布置布线路径时，如果各布线起点可以与任一个布线终点进行布线，且布线规则相同，且布线路径不能交叉，那么可能存在一种最优布线结果，就是每一个布线起点与对应的布线终点之间都生成布线路径。

2、在寻找最优布线结果时，布线顺序可以视作一个排列组合，组合的数量为a！，a表示布线起点的数量。如果a很大，那么组合数量将爆炸性增长，例如布线起点的数量为13个时，布线顺序的组合数量为13！，约为62亿，显然遍历所有布线顺序是不现实的，这会显著增加布线逻辑的计算规模，降低布线速度。

技术实现思路

1、本发明的目的是提供一种电路版图的快速布线方法、装置、存储介质及电子设备，以解决现有技术中布线逻辑计算规模大、布线速度慢的问题，能够降低布线逻辑的计算规模、加快布线速度，可以提高版图布线效率。

2、为解决上述技术问题，本发明提供一种电路版图的快速布线方法，包括：

3、s1：确定电路版图中多个具有初始顺序的布线起点和布线终点，创建根节点为空的树状结构，并将各布线起点分别单独排序创建为根节点的子节点；

4、s2：以根节点为当前节点，重复进行比较当前节点的子节点的置信值，并选择一个置信值最大的子节点替代当前节点的过程，直至当前节点未进行过布线为止，其中，子节点的置信值不存在时，设置预设值为置信值；

5、s3：在当前节点的排序末尾分别添加一个不重复的布线起点创建出子节点，对所述排序中的布线起点进行整体布线和对剩余布线起点分别进行单独布线；

6、s4：对当前节点及其向上的每一级节点的置信值进行反馈补偿，并返回步骤s2，直至整体布线成功且布线起点无剩余为止，其中，所述反馈补偿仅在单独布线全部成功时为正反馈，否则为负反馈。

7、优选的，在步骤s2中，如果置信值最大的子节点为多个，被选择的子节点为随机的一个或者子节点中的排序末尾的布线起点在初始顺序中顺序最靠前的一个。

8、优选的，在步骤s4中，对置信值进行反馈补偿时，置信值采用下列计算式计算得到：

9、

10、其中，z为置信值，v为节点的当前回报值，v-为节点的历史回报值，ln()为以常数e为底的对数，f为进行反馈补偿的值，n为节点作为当前节点的次数，n为节点的父节点作为当前节点的次数，c为大于零的常数，在n＝0时，z和v-均为所述预设值。

11、优选的，所述步骤s3还包括：在所述排序包含全部布线起点时，取消子节点的创建，并进行所述整体布线和所述单独布线过程。

12、优选的，所述对所述排序中的布线起点进行整体布线，包括：

13、s31：按照所述排序将布线起点与布线终点进行配对并网格化电路版图；

14、s32：依序选择一对未查找过布线路径的布线起点和布线终点作为布线对；

15、s33：按照预设布线规则查找布线对之间经过网格点的布线路径，并返回步骤s32，直至每对布线起点和布线终点均完成布线路径查找，其中，布线路径经过的网格点满足筛选条件，所述筛选条件为不属于障碍点且不是其它布线起点或布线终点，且每当查找到布线路径时，将查找到的布线路径经过的网格点设为障碍点。

16、优选的，所述按照预设布线规则查找布线对之间的布线路径，包括：

17、s331：将布线对中的布线起点作为布线点，判断所述布线点的邻近网格点中是否包含布线对中的布线终点；

18、s332：如果包含，将布线对中的布线终点作为新的布线点，依次连接每个未剔除的布线点生成布线路径；

19、s333：如果不包含，判断所述布线点的邻近网格点中是否存在与所述布线点的连线不与预设布线边界相交且满足所述筛选条件的目标网格点；

20、s334：如果存在，选择到预设布线边界的垂直距离、到布线终点的欧氏距离以及到布线起点的曼哈顿距离的总和最小的一个目标网格点作为新的布线点，并返回所述判断所述布线点的邻近网格点中是否包含布线对中的布线终点；

21、s335：如果不存在，将所述布线点剔除，选择前一个布线点作为新的布线点，并返回步骤s333，直至首个布线点不存在目标网格点为止。

22、优选的，所述筛选条件还包括布线路径经过的任一个网格点与前后两个网格点的连线的夹角大于90度，其中，在网格点为布线起点时，前一个网格点为预设点。

23、优选的，所述步骤s31还包括：

24、将电路版图中的障碍图形对应的网格点设为障碍点。

25、优选的，所述对剩余布线起点分别进行单独布线，包括：

26、s35：将剩余的每一个布线起点与剩余的全部布线终点分别进行配对；

27、s36：选择一对未查找过布线路径的布线起点和布线终点作为布线对；

28、s37：按照所述预设布线规则查找布线对之间经过网格点的布线路径，并返回步骤s36，直至每对布线起点和布线终点均完成布线路径查找。

29、优选的，所述从当前节点开始向上逐级对节点的置信值进行反馈补偿，包括：

30、s41：判断整体布线是否成功；

31、s42：如果整体布线失败，将小于零的第一设定值向上逐级加入节点的置信值中；

32、s43：如果整体布线成功，判断所述排序中是否包含全部布线起点；

33、s44：如果不包含，判断单独布线是否全部成功；

34、s45：如果单独布线全部成功，将大于零的第二设定值向上逐级加入节点的置信值中；

35、s46：如果单独布线没有全部成功，将小于零的第三设定值向上逐级加入节点的置信值中。

36、优选的，所述第一设定值、所述第二设定值、所述第三设定值的计算式为：

37、s1＝-m

38、s2＝(p/(p+1))*p+m

39、s3＝-(m/((w-p)+k))

40、其中，s1为第一设定值，s2为第二设定值，s3为第三设定值，p为所述排序中包含的布线起点数量，w为全部布线起点的数量，m和k均为大于零的常数。

41、为解决上述技术问题，本发明还提供一种电路版图的快速布线装置，包括：

42、初始化模块，用于确定电路版图中多个具有初始顺序的布线起点和布线终点，创建根节点为空的树状结构，并将各布线起点分别单独排序创建为根节点的子节点；

43、选择模块，用于以根节点为当前节点，重复进行比较当前节点的子节点的置信值，并选择一个置信值最大的子节点替代当前节点的过程，直至当前节点未进行过布线为止，其中，子节点的置信值不存在时，设置预设值为置信值；

44、布线模块，用于在当前节点的排序末尾分别添加一个不重复的布线起点创建出子节点，对所述排序中的布线起点进行整体布线和对剩余布线起点分别进行单独布线；

45、反馈模块，用于对当前节点及其向上的每一级节点的置信值进行反馈补偿，并返回执行选择模块，直至整体布线成功且布线起点无剩余为止，其中，所述反馈补偿仅在单独布线全部成功时为正反馈，否则为负反馈。

46、为解决上述技术问题，本发明还提供一种存储介质，所述存储介质中存储有计算机程序，所述计算机程序被设置为运行时执行前述任一项所述的电路版图的快速布线方法。

47、为解决上述技术问题，本发明还提供一种电子设备，包括存储器和处理器，所述存储器中存储有计算机程序，所述处理器被设置为运行所述计算机程序以执行前述任一项所述的电路版图的快速布线方法。

48、区别于现有技术的情况，本发明提供的电路版图的快速布线方法首先创建根节点为空的树状结构，将每个布线起点单独排序作为根节点的子节点，从根节点开始，遍历当前节点的子节点，选择一个置信值最大的替代当前节点，重复该过程，直到当前节点未进行过布线，然后对当前节点的排序进行扩展形成下级子节点，并对排序中的布线起点进行整体布线以及对剩余布线起点分别进行单独布线，从当前节点开始向上逐级对节点的置信值进行反馈补偿，并再次重复选择当前节点的过程，直至整体布线成功且布线起点无剩余为止，通过上述方式，本技术将布线顺序的寻找问题转化为树状结构，每次遍历时能够优先选择整体布线成功且单独布线全部成功的节点，不需要遍历所有布线顺序，从而能够降低布线逻辑的计算规模、加快布线速度，可以提高版图布线效率。

49、本发明提供的电路版图的快速布线装置、存储介质及电子设备，与电路版图的快速布线方法属于同一发明构思，因此具有相同的有益效果，在此不再赘述。