Optimal replication for min-cut partitioning
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 6 references indexed in Scilit:
- A cell-replicating approach to minicut-based circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A new approach to the maximum flow problemPublished by Association for Computing Machinery (ACM) ,1986
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A Heuristic Procedure for the Partitioning and Mapping of Computer Logic GraphsIEEE Transactions on Computers, 1971
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956