Title :
Optimal replication for min-cut partitioning
Author :
Hwang, J. ; El Gamal, A.
Author_Institution :
Inf. Syst. Lab., Stanford Univ., CA, USA
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;
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
DOI :
10.1109/ICCAD.1992.279332
