基于再聚类和离散优化的k路划分算法  

k-Way Partitioning Algorithm Based on Re-Clustering and Discrete Optimization

作　　者：潘萍梅 刘欣恬 李兴权 朱文兴[1] Pan Pingmei;Liu Xintian;Li Xingquan;Zhu Wenxing(Center for Discrete Mathematics and Theoretical Computer Science,Fuzhou University,Fuzhou 350116;School of Mathematics and Statistics,Fuzhou University,Fuzhou 350116;Peng Cheng Laboratory,Shenzhen 518073;School of Mathematics and Statistics,Minnan Normal University,Zhangzhou 363000)

机构地区：[1]福州大学离散数学与理论计算机科学研究中心,福州350116 [2]福州大学数学与统计学院,福州350116 [3]鹏城实验室,深圳518073 [4]闽南师范大学数学与统计学院,漳州363000

出　　处：《计算机辅助设计与图形学学报》2024年第3期473-484,共12页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(62174033);国家重点研发计划(2023YFA1011302);中央引导地方科技发展专项(2023L3003).

摘　　要：为了寻得集成电路更优的k路划分,提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模,即根据给定划分计算顶点间的评级函数值,依据取值大小进行顶点聚类;然后将超图转换为星型图,并将k路划分问题转换为无约束的离散优化问题;进而设计一个算法迭代移动增益值最大的顶点,在算法求解过程中放宽平衡约束,允许暂时处于不可行域的解,扩大问题的求解空间.在同一平台上使用ISPD98电路测试基准对所提算法、hMETIS-Kway和KaHyPar-K进行测试,并比较最小割值和运行时间.实验结果表明该算法优于hMETIS-Kway,特别是在k=2时,最小割值减少了0.173,速度提升了0.706.此外,该算法对KaHyPar-K也有相应的改进效果.To achieve a better partitioning of VLSI circuit,re-clustering and discrete optimization are applied to the k-way partitioning algorithm.Firstly,re-clustering is used to reduce the scale of hypergraph,i.e.,the rating function value between two vertices is calculated according to the given partitionings,and vertices are clus-tered according to the magnitude of the rating function values.Secondly,the hypergraph is converted to a star graph,and the k-way partitioning problem is transformed to an unconstrained discrete optimization problem.In turn,an algorithm is designed to iteratively move the vertices with the largest gain.During the solution proc-ess,the balancing constraints are relaxed,allowing a solution to be temporarily in the infeasible region,which expands the solution space of the problem.The proposed algorithm,hMETIS-Kway and KaHyPar-K are tested on the same platform on the ISPD98 test benchmarks,and the min-cut and running time are compared.Ex-perimental results show that,the proposed algorithm is superior to hMETIS-Kway,especially when k=2,for which the min-cut is reduced by 0.173 and the runtime is sped up by 0.706.The proposed algorithm has almost the same improvement effect over KaHyPar-K.

关 键 词：k路划分 最小割 超图聚类 离散优化 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]