Min-cut replication in partitioned networks
- 1 January 1995
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 14 (1) , 96-106
- https://doi.org/10.1109/43.363121
Abstract
Logic replication has been shown empirically to reduce pin count and partition size in partitioned networks. This paper presents the first theoretical treatment of the min-cut replication problem, which is to determine replicated logic that minimizes cut size. A polynomial time algorithm for determining min-cut replication sets for k-partitioned graphs is derived by reducing replication to the problem of finding a maximum flow. The algorithm is extended to hypergraphs and replication heuristics are proposed for the NP-hard problem with size constraints on partition components. These heuristics, which reduce the worst-case running time by a factor of O(k2) over previous methods, are applied to designs that have been partitioned into multiple FPGA's. Experimental results demonstrate that min-cut replication provides substantial reductions in the numbers of FPGA's and pins requiredKeywords
This publication has 11 references indexed in Scilit:
- A cell-replicating approach to minicut-based circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Placement and routing for a field programmable multi-chip modulePublished by Association for Computing Machinery (ACM) ,1994
- Optimal replication for min-cut partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Computer-aided prototyping for ASIC-based systemsIEEE Design & Test of Computers, 1991
- Combinatorial Algorithms for Integrated Circuit LayoutPublished by Springer Nature ,1990
- MIS: A Multiple-Level Logic Optimization SystemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- 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