An effective algorithm for multiway hypergraph partitioning

摘要

In this paper, we propose an effective multiway hypergraph partitioning algorithm. We introduce the concept of net-gain and embed it in the selection of cell moves. Unlike traditional FM-based iterative improvement algorithms in which the selection of the next cell to move is only based on its cell gain, our algorithm selects a cell based on both its cell-gain and the sum of all net-gains for those nets incident to the cell. To escape from local optima and to search broader solution space, we propose a new perturbation mechanism. These two strategies significantly enhance the solution quality produced by our algorithm. Based on our experimental justification, we smoothly decrease the number of iterations from pass to pass to reduce the computational effort so that our algorithm can partition large benchmark circuits with reasonable run time. Compared with the recent multiway partitioning algorithms proposed by Dasdan and Aykanat, our algorithm significantly outperforms theirs in term of solution quality (cutsize) and run time, the average improvements in terms of average cutsize over their PLM3 and PFM3 are 47.64% and 36.76% with only 37.17% and 9.66% of their run time, respectively.