科研之友
微信
新浪微博
Facebook
分享链接
摘要
超图平衡二划分是VLSI物理设计的重要一环。KL算法和FM算法等迭代优化算法是求解该NP-困难问题的常用方法。这些算法有如下可改进之处:一是对于较差的初始解,算法容易陷入局部最优。二是由于平衡条件的约束,顶点的移动受到诸多限制。针对上述问题,本文将超图平衡二划分问题转化为0-1规划问题,并设计了求解该问题的离散迭代算法,在一定程度上克服了传统的迭代算法受平衡条件与初始解约束的缺点。在ISPD98电路划分测试样例上,本文的算法取得了比FM算法质量更高的解。在20次随机实验中,本文的平均割边数比FM算法少13.2%。将本文的结果作为FM算法的初始解作进一步优化,所产生的平均割边数比FM算法少30.1%。不仅如此,本文的算法还可以嵌入到多级划分算法框架中,取得的平均割边数比MLPart少3.6%。
- 单位
