-
题名一种基于点割的电路划分算法
被引量：1
- 1
-
-
作者
张恩利
高琳
-
机构
西安电子科技大学计算机学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2014年第7期1528-1537,共10页
-
基金
国家自然科学基金(60933009
91130006)
中央高校基本科研业务费专项资金(BDZ021404)资助~~
-
文摘
文中提出了一种基于IG图（Intersection Graph）点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元（模块）的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K DualFM算法平均有3％～7.8％的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18％,比基于二部图匹配的点割优化算法提高36％,对较大规模数据划分优化效果更好.
-
关键词
电路划分
ig图
点割
集成电路
-
Keywords
circuit partitioning； intersection graph； vertex separator； integrated circuit
-
分类号
TP312
[自动化与计算机技术—计算机软件与理论]
-
