一种基于点割的电路划分算法

• 作者: 张恩利 高琳
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 电路划分 IG图 点割 集成电路
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 芯片设计及嵌入式系统
• 页码范围: 1528-1537
• 页数: 10页
• 分类号: TP312
• 字数: 8106字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2014.01528

摘要

文中提出了一种基于IG图(Intersection Graph)点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元(模块)的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K DualFM算法平均有3％～7.8％的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18％,比基于二部图匹配的点割优化算法提高36％,对较大规模数据划分优化效果更好.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高琳	西安电子科技大学计算机学院	43	810	16.0	28.0
2	张恩利	西安电子科技大学计算机学院	1	1	1.0	1.0