摘要
该文提出了一种新的划分算法,算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个,为了充分将线网增加的权重作用到与该线网相连的所有节点上去,线网增益采用了概率增益模型。该算法与原有算法相比较,可以有效地让电路的划分跳出局部最小,结果有较大的改进,特别是当电路规模比较大的时候,改进更明显。由于采用概率增益模型,出现浮点数,节点增益的存储采用了平衡二叉树(balanced binary tree),因此算法的速度相对于FM算法有所下降,但是时间复杂度仍然接近为线性复杂度,时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和,n为电路的逻辑单元数)。
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）.
出处
《电子与信息学报》
EI
CSCD
北大核心
2007年第11期2762-2766,共5页
Journal of Electronics & Information Technology
基金
国家自然科学基金(60676020)
上海应用材料科技合作共同计划项目(AM0406)
复旦大学青年科学基金(JKH1203001)资助课题
