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, a given hypergraph partition is re-clustered for reducing the scale of the hypergraph. Secondly, the k-way partitioning problem is converted into an unconstrained discrete optimization problem, and an iterative improvement algorithm is designed. During the iterations of the algorithm, 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 minimum cut and running time are compared. Experimental results show that, the proposed algorithm is superior to hMETIS-Kway, especially when k=2, for which the minimum cut is reduced by 17.3% and the runtime is sped up by 70.6%. The proposed algorithm has almost the same improvement effect over KaHyPar-K.