k-Way Partitioning Algorithm Based on Re-Clustering and Discrete Optimization
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.
万方数据
维普
