基于概率增益的电路划分算法

该文提出了一种新的划分算法，算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个，为了充分将线网增加的权重作用到与该线网相连的所有节点上去，线网增益采用了概率增益模型。该算法与原有算法相比较，可以有效地让电路的划分跳出局部最小，结果有较大的改进，特别是当电路规模比较大的时候，改进更明显。由于采用概率增益模型，出现浮点数，节点增益的存储采用了平衡二叉树(balanced binary tree)，因此算法的速度相对于FM算法有所下降，但是时间复杂度仍然接近为线性复杂度，时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和，n为电路的逻辑单元数)。

A Circuit Partition Algorithm Basing on Probability Gain

This paper proposes a new partition algorithm. The variable weight of the nets is introduced into the algorithm. Generally,the nodes connected to the nets are more than two in the hypergraph,so the probability gain model is used to enforce the effect of the increased weight of the nets. This algorithm can jump out of local minimal effectively when compared with original algorithm. The improvement is especially obvious for the large-scale circuits. For the gain value of the cell is floating-point,balanced binary tree is used to store the gain value of the cells,so the speed of this algorithm is several times slower than FM algorithm. The time complexity of this algorithm is O(P log2(n) )(where P is the sum of the pins of all logic cells of the circuit,and n is the number of the circuit logic cells) .