DocumentCode
1683836
Title
Optimal replication for min-cut partitioning
Author
Hwang, J. ; El Gamal, A.
Author_Institution
Inf. Syst. Lab., Stanford Univ., CA, USA
fYear
1992
Firstpage
432
Lastpage
435
Abstract
Heuristics for replicating logic have been shown to reduce pin count and wiring density in partitioned logic networks. An efficient algorithm for determining an optimal min-cut replication set for a k-partitioned graph in O(knm log (n/sup 2//m)) time is presented. For the NP-hard case with limited size partition components, a replication heuristic which reduces the worst-case running time by a factor of O(k/sup 2/) over previous methods is proposed. Experimental results are presented.<>
Keywords
circuit layout CAD; graph theory; integrated logic circuits; logic CAD; optimisation; NP-hard case; k-partitioned graph; min-cut partitioning; partitioned logic networks; reduce pin count; replicating logic; wiring density; worst-case running time; Design automation; Graph theory; Optimization methods;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer-Aided Design, 1992. ICCAD-92. Digest of Technical Papers., 1992 IEEE/ACM International Conference on
Conference_Location
Santa Clara, CA, USA
Print_ISBN
0-8186-3010-8
Type
conf
DOI
10.1109/ICCAD.1992.279332
Filename
279332
Link To Document