| 基于再聚类和离散优化的k路划分算法 |
| |
| 引用本文： | 潘萍梅,刘欣恬,李兴权,朱文兴.基于再聚类和离散优化的k路划分算法[J].计算机辅助设计与图形学学报,2024(3):473-484. |
| |
| 作者姓名： | 潘萍梅 刘欣恬 李兴权 朱文兴 |
| |
| 作者单位： | 1. 福州大学离散数学与理论计算机科学研究中心;2. 福州大学数学与统计学院;3. 鹏城实验室;4. 闽南师范大学数学与统计学院 |
| |
| 基金项目： | 国家自然科学基金(62174033)；;国家重点研发计划(2023YFA1011302)； |
| |
| 摘 要： | 为了寻得集成电路更优的k路划分,提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模,即根据给定划分计算顶点间的评级函数值,依据取值大小进行顶点聚类;然后将超图转换为星型图,并将k路划分问题转换为无约束的离散优化问题;进而设计一个算法迭代移动增益值最大的顶点,在算法求解过程中放宽平衡约束,允许暂时处于不可行域的解,扩大问题的求解空间.在同一平台上使用ISPD98电路测试基准对所提算法、hMETIS-Kway和KaHyPar-K进行测试,并比较最小割值和运行时间.实验结果表明该算法优于hMETIS-Kway,特别是在k=2时,最小割值减少了0.173,速度提升了0.706.此外,该算法对KaHyPar-K也有相应的改进效果.
|
| 关 键 词： | k路划分 最小割 超图聚类 离散优化 |
|
|
