计算机辅助设计与图形学学报

作者：潘萍梅, 刘欣恬, 李兴权, 朱文兴

关键词：<i>k</i>路划分, 最小割, 超图聚类, 离散优化

为了寻得集成电路更优的k路划分, 提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模, 即根据给定划分计算顶点间的评级函数值, 依据取值大小进行顶点聚类; 然后将超图转换为星型图, 并将k路划分问题转换为无约束的离散优化问题; 进而设计一个算法迭代移动增益值最大的顶点, 在算法求解过程中放宽平衡约束, 允许暂时处于不可行域的解, 扩大问题的求解空间.在同一平台上使用ISPD98电路测试基准对所提算法、hMETIS-Kway和KaHyPar-K进行测试, 并比较最小割值和运行时间.实验结果表明该算法优于hMETIS-Kway, 特别是在k=2时, 最小割值减少了0.173, 速度提升了0.706.此外, 该算法对KaHyPar-K也有相应的改进效果.

来源：2024年第3期

《计算机辅助设计与图形学学报》期刊编辑部

查看计算机辅助设计与图形学学报杂志2024年第3期