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

摘要：

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

关键词：电路划分、最小割、概率增益、NP-完全问题

所属期刊栏目：29

分类号：TN47(微电子学、集成电路（IC）)

资助基金：国家自然科学基金60676020;上海应用材料科技合作共同计划项目AM0406;复旦大学校科研和教改项目JKH1203001

在线出版日期：2008-01-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：2762-2766