本发明属于电子设计自动化eda领域，尤其涉及一种基于网络流的平衡分割方法。
背景技术：
1、在eda领域中，很多环节都会涉及有关分割的算法。比如在逻辑综合过程中要实现并行综合，就需要将电路设计分成不同的子部分，各个子部分同时进行逻辑综合或者综合的优化；在布局过程中，电路设计不仅要被分割成不同的子部分，而且各个子部分在芯片上物理通道的通信代价要被考虑其中。
2、电路设计不同于一般的图结构，它有其自身的结构特点，它的运算模式多基于流水线的处理的模式，同时它内部的连线能够同时连接多个电路模块，具有一定的特殊性，因而需要针对电路设计的分割方法。网络流是一种经典的图问题，利用网络流进行分割则是一种比较高级的算法应用，网络流在进行求解的过程中，也可以看成是分割的求解过程。
3、现有基于网络流的分割方法存在以下问题：1、现有基于网络流的分割方法不能直接处理电路中的连边（net），该连边可以同时连接多个电路模块。2、现有基于网络流的分割方法为在网络流图中随机挑选源点s和汇点t，源点即为流的出发节点，汇点即为流的到达节点，如果源点s和汇点t的节点选择不当，如选择了彼此最大流的值特别大的两个节点，那么将造成分割代价的增加，分割代价是指处在分割边界上的边的权重的总和。3、现有基于网络流的分割方法多适用于无向图，而电路设计中的信号都是有方向的，同时在后期的布线阶段，能够承载信号的物理通道有时也会限定信号的方向，因而基于网络流分割的方法亟需一种能够支持信号有向的分割方式。4、现有基于流的分割方法速度较慢，原因是分割过程中涉及多次最大流的重新计算过程，这消耗了大量的时间。
技术实现思路
1、本发明提供了一种基于网络流的平衡分割方法，以解决现有基于网络流的分割方法不能直接处理电路中的连边、分割代价大、无法支持信号有向分割、分割方法速度较慢等问题。
2、为解决上述技术问题，本发明提供的技术方案为：
3、本发明涉及一种基于网络流的平衡分割方法，其包括以下步骤：
4、s1.将电路中的电路模块作为节点，电路模块间的连边作为边，建立网络流图；
5、s2.选择网络流图中的其中一个节点为源点，另一个节点为汇点；
6、s3.设置网络流图的初始最大流为0；
7、s4.搜索从源点到汇点的未被搜索过的一条路径，若能够搜索到路径，进入s5；若无法搜索到路径，则跳过s5，进入s6；
8、s5.以该路径上的最小边权的边的权重作为该路径的最小流，更新网络流图的最大流和该路径经过的每一条边的权重，返回s4；
9、s6.向更新后的网络流图的源点输入信号流，将信号流能够到达的节点作为x组，将信号流不能到达的节点作为y组，分割网络流图中起点位于x组的节点、终点位于y组的节点的边，形成切割边界，更新后的最大流即为最小切割代价；
10、s7.判断x组节点和y组节点中节点的权重和是否平衡，若平衡，输出分割结果，若不平衡，进入s8；
11、s8.当x组节点的权重和过大时，遍历x组中的节点并与原汇点组成新的汇点，当y组节点的权重和过大时，遍历y组中的节点并与原源点组成新的源点，按s4-s6的方式分析各情况下更新的最大流，选择最大流最小的切割方案并返回s7。
12、优选地，所述s1中以电路模块的逻辑大小作为对应节点的权重；以连边的容量作为对应边的权重。
13、优选地，所述s1中当建立网络流图时，当存在一条连边连接多个电路模块或存在一条连边连接源点和多个电路模块或存在一条连边连接一个电路模块和多个汇点时，记录该连边的权重为w，定义该连边输入端的节点为驱动节点，多个输出端的节点为负载节点，在驱动节点与负载节点之间建立一个虚拟节点，虚拟节点的权重为0，在驱动节点和虚拟节点之间建立一条权重为w的连边，在虚拟节点与各负载节点之间各建立一条权重为正无穷的连边。
14、优选地，所述s5更新网络流图的最大流的更新公式为：
15、max-flow（t）= max-flow（t-1）+ min-flow，
16、公式中，t表示最大流的更新次数，max-flow（t）和max-flow（t-1）分别表示第t次更新和第t-1次更新时网络流图的最大流，min-flow表示路径的最小流。
17、优选地，所述s5更新该路径经过的每一条边的权重的具体方式为：路径上每一条边的权重减少路径的最小流。
18、优选地，所述s7判断x组节点和y组节点中节点的权重和是否平衡的平衡公式为：
19、|wx - wy| / |wx + wy| > α ，
20、其中，wx 为x组节点中的所有节点的权重和，wy 为y组节点中的所有节点的权重和， α为阈值；
21、当满足上述平衡公式时，判断为x组节点和y组节点中节点的权重和平衡，当不满足上述平衡公式时，判断为x组节点和y组节点中节点的权重和不平衡。
22、优选地，所述s8每次遍历x组或y组中的节点，将一个新的节点加入到源点或汇点后，将x组中的节点及边删除，并在计算最大流后还原。
23、优选地，所述s4采用广度优先搜索方法或深度优先搜索算法搜索从源点到汇点的未被搜索过的一条路径。
24、采用本发明提供的技术方案，与现有技术相比，具有如下有益效果：
25、1、本发明涉及的基于网络流的平衡分割方法选择网络流图中的其中一个节点为源点，另一个节点为汇点，设置初始最大流为0，依次搜索从源点到汇点路径并以路径上的最小权的边的权重作为最小流，迭代更新网络流图的最大流和经过该路径的边的权重，向更新后的网络流图的源点输入信号流，将信号流能够到达的节点作为x组，将信号流不能到达的节点作为y组，分割网络流图中起点位于x组的节点、终点位于y组的节点的边，完成一次分割，该方法通过选择虚拟源点和汇点，使网络流算法更加适合于以流处理为特征的电路结构，能够统筹、综合电路输入输出端口的不同位置，使最终得到的最大流的值更小，即切割代价更小，能够处理有方向的信号，适应物理上通道有方向限制的分割场景。
26、2、本发明涉及的基于网络流的平衡分割方法没进行一次分割后，均判断分割后两组节点的权重和是否平衡，若分割后两组节点的权重不平衡，遍历权重较大的组的节点并将遍历到的节点加到源点或汇点中，重复进行从源点到汇点的路径搜索、寻找路径上的最小流、更新网络流图最大流机路径上每条边的权重、网络流图的切割等步骤，找到切割代价最小的情况作为新的切割方案，直至分割后两组节点的权重达到平衡，该方法通过在维持网络流始终为真实流的基础上，以平衡分割为限制条件，通过每次迭代调整，增量式获得新的分割边界与切割代价，控制了切割代价的大小，得到了平衡的分割结果，提升了基于网络流的分割速度。
27、3、本发明涉及的基于网络流的平衡分割方法在建立网络流图时，当存在一条连边连接多个电路模块或一条连边连接源点和多个电路模块或一条连边连接一个电路模块和多个汇点时，定义该连边为超边，记录该连边的权重为w，定义该连边输入端的节点为驱动节点，多个输出端的节点为负载节点，在驱动节点与负载节点之间建立一个虚拟节点，虚拟节点的权重为0，在驱动节点和虚拟节点之间建立一条权重为w的连边，在虚拟节点与各负载节点之间各建立一条权重为正无穷的连边，解决了连边在网络流中的建模问题，使得对电路中连班的切割更加合理，即要么不切割连边，要么切割在驱动节点的输出端口，降低了切割代价。
1.一种基于网络流的平衡分割方法，其特征在于：其包括以下步骤：
2.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s1中以电路模块的逻辑大小作为对应节点的权重；以连边的容量作为对应边的权重。
3.根据权利要求2所述的基于网络流的平衡分割方法，其特征在于：所述s1中当建立网络流图时，当存在一条连边连接多个电路模块或存在一条连边连接源点和多个电路模块或存在一条连边连接一个电路模块和多个汇点时，记录该连边的权重为w，定义该连边输入端的节点为驱动节点，多个输出端的节点为负载节点，在驱动节点与负载节点之间建立一个虚拟节点，虚拟节点的权重为0，在驱动节点和虚拟节点之间建立一条权重为w的连边，在虚拟节点与各负载节点之间各建立一条权重为正无穷的连边。
4.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s5更新网络流图的最大流的更新公式为：
5.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s5更新该路径经过的每一条边的权重的具体方式为：路径上每一条边的权重减少路径的最小流。
6.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s7判断x组节点和y组节点中节点的权重和是否平衡的平衡公式为：
7.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s8每次遍历x组或y组中的节点，将一个新的节点加入到源点或汇点后，将x组中的节点及边删除，并在计算最大流后还原。
8.根据权利要求1所述的基于网络流的平衡分割方法，其特征在于：所述s4采用广度优先搜索方法或深度优先搜索算法搜索从源点到汇点的未被搜索过的一条路径。
