摘要
文中提出了一种基于IG图（Intersection Graph）点割的电路划分算法,引入IG图模型,根据电路中信号网络间的交互关系构建IG图,直接对电路信号网络IG图进行最小点割划分,从而实现对电路单元（模块）的划分.该算法既有效地解决了电路超图与图之间转换的一致性问题,又实现了点割目标值与直接电路划分目标值的一致性,IG图点割集的大小即为真实电路划分的目标值.此外,通过给每个电路网络赋权重的方式构建带权重网络交互图,实现对电路网络划分的面积平衡进行近似控制,满足电路划分对面积平衡的特殊要求.采用MCNC提供的标准电路测试数据进行测试,实验结果表明,基于IG图点割的电路划分算法较基于网络超图HDN划分的K DualFM算法平均有3％～7.8％的提高;同时,基于IG图点割的随机优化算法ROP比基于超图划分的FM优化算法具有更强的全局优化能力,划分结果提高18％,比基于二部图匹配的点割优化算法提高36％,对较大规模数据划分优化效果更好.
A novel vertex separator based circuit partitioning algorithm is proposed, which parti- tions the cells or modules of the circuit by dividing the signal nets. The approach successfully solves the inconsistency between the objectives of real circuit partitioning and net-based partitioning algorithms that partition the net in terms of edge-cuts, with the size of vertex separator equal exactly to the objective value of real circuit partitioning. By adding weight for each net to construct a weighted intersection graph, the proposed algorithm can approximately control the area of the partitions in dividing the nets, which fulfills the special requirement for area balance. Experiments on the MCNC benchmark sets show that our vertex separator based approach improves the partitions by 3 % - 7.8% on average over the K-DualFM algorithm, and the new refinement algorithm ROP has much better global searching ability than other state of the art schemes. Compared with the FM algorithm and the bipartite-matching based refinement algorithm, the new refinement algorithm ROP improves the results by 18 % and 36 % respectively, with greater improvement on circuits of larger scale.
出处
《计算机学报》
EI
CSCD
北大核心
2014年第7期1528-1537,共10页
Chinese Journal of Computers
基金
国家自然科学基金(60933009
91130006)
中央高校基本科研业务费专项资金(BDZ021404)资助~~
关键词
电路划分
IG图
点割
集成电路
circuit partitioning； intersection graph； vertex separator； integrated circuit
