A gradient method on the initial partition of Fiduccia-Mattheyses algorithm
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, a Fiduccia-Mattheyses (FM) algorithm incorporating a novel initial partition generating method is proposed. The proposed algorithm applies to both bipartitioning and multi-way partitioning problems with or without replication. The initial partition generating method is based on a gradient descent algorithm. On partitioning without replication, our algorithm achieves an average of 17% improvement over the analytical method, PARABOLI, on bipartitioning, 10% better than Primal-Dual method on 4-way partitioning and 51% better than net-based method. On partitioning allowing replication, our algorithm achieves an average of 23% improvement over the directed Fiduccia-Mattheyses algorithm on Replication Graph (FMRG) method on bipartitioning.Keywords
This publication has 12 references indexed in Scilit:
- A cell-replicating approach to minicut-based circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Partitioning very large circuits using analytical placement techniquesPublished by Association for Computing Machinery (ACM) ,1994
- A simple yet effective technique for partitioningIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1993
- Quadratic Boolean programming for performance-driven system partitioningPublished by Association for Computing Machinery (ACM) ,1993
- Optimal replication for min-cut partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- An improved two-way partitioning algorithm with stable performance (VLSI)IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithmsPublished by Association for Computing Machinery (ACM) ,1989
- Multiple-way network partitioningIEEE Transactions on Computers, 1989
- A heuristic for quadratic Boolean programs with applications to quadratic assignment problemsEuropean Journal of Operational Research, 1983
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982