-
题名基于概率增益的电路划分算法
被引量：4
- 1
-
-
作者
胡云
王伶俐
唐璞山
童家榕
-
机构
复旦大学专用集成电路与系统国家重点实验室
-
出处
《电子与信息学报》
EI
CSCD
北大核心
2007年第11期2762-2766,共5页
-
基金
国家自然科学基金(60676020)
上海应用材料科技合作共同计划项目(AM0406)
复旦大学青年科学基金(JKH1203001)资助课题
-
文摘
该文提出了一种新的划分算法,算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个,为了充分将线网增加的权重作用到与该线网相连的所有节点上去,线网增益采用了概率增益模型。该算法与原有算法相比较,可以有效地让电路的划分跳出局部最小,结果有较大的改进,特别是当电路规模比较大的时候,改进更明显。由于采用概率增益模型,出现浮点数,节点增益的存储采用了平衡二叉树(balanced binary tree),因此算法的速度相对于FM算法有所下降,但是时间复杂度仍然接近为线性复杂度,时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和,n为电路的逻辑单元数)。
-
关键词
电路划分
最小割:概率增益
NP-完全问题
-
Keywords
Circuit partition
Min cut
Probability gain
NP complete
-
分类号
TN47
[电子电信—微电子学与固体电子学]
-
