Title :
A gradient method on the initial partition of Fiduccia-Mattheyses algorithm
Author :
Liu, L.-T. ; Kuo, M.-T. ; Huang, S.-C. ; Cheng, C.-K.
Author_Institution :
AT&T Bell Labs., Murray Hill, NJ, USA
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 :
logic CAD; logic partitioning; Fiduccia-Mattheyses algorithm; bipartitioning; gradient descent algorithm; gradient method; initial partition; multi-way partitioning; replication; Algorithm design and analysis; Bipartite graph; Circuits; Computer science; Gradient methods; Minimization; Partitioning algorithms; Size control;
Conference_Titel :
Computer-Aided Design, 1995. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA, USA
Print_ISBN :
0-8186-8200-0
DOI :
10.1109/ICCAD.1995.480017