An effective algorithm for multiway hypergraph partitioning
IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications - Tập 49 Số 8 - Trang 1079-1092 - 2002
Tóm tắt
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.
Từ khóa
#Partitioning algorithms #Iterative algorithms #Databases #Very large scale integration #Circuit synthesis #Decision support systems #Data mining #NP-hard problem #NP-complete problemTài liệu tham khảo
hauck, 1997, an evaluation of bipartitioning techniques, IEEE Trans on Computer-Aided Design, 16, 849, 10.1109/43.644609
karypis, 1999, multilevel hypergraph partitioning: applications in vlsi domain, IEEE Trans VLSI Syst, 7, 69, 10.1109/92.748202
10.1002/j.1538-7305.1970.tb01770.x
10.1109/TC.1984.1676460
mobasher, 1996, Web mining Pattern discovery from world wide web transactions
10.1109/43.248079
10.1109/TCAD.2002.1004312
10.1145/800153.804930
10.1109/12.8730
shekhar, 1996, partitioning similarity graphs: a framework for declustering problems, Inf Syst, 21, 475, 10.1016/0306-4379(96)00024-5
10.1145/288548.289079
10.1109/ICCAD.1997.643573
dutt, 1996, vlsi circuit partitioning by cluster-removal using iterative improvement techniques, Proc IEEE/ACM Int Conf Computer-Aided Design, 92
dasdan, 1997, two novel multiway circuit partitioning algorithms using relaxed locking, IEEE Trans on Computer-Aided Design, 16, 169, 10.1109/43.573831
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
10.1109/DAC.1982.1585498
berge, 1976, Graphs and Hypergraphs
10.1016/0167-9260(95)00008-4
10.1109/EURDAC.1995.527400
yang, 1996, efficient network flow based min-cut balanced partitioning, IEEE Trans on Computer-Aided Design, 15, 1533
yeh, 1994, a general purpose, multiway partitioning algorithm, IEEE Trans on Computer-Aided Design, 13, 1480, 10.1109/43.331405