中文摘要：

文中提出了一种基于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.