On Board Radar PCB Cloning
On Board Radar PCB Cloning
The idea of recursive minimum cut placement is to partition the circuit into subcircuits subject to minimizing the number of wires running between the two partitions of On Board Radar PCB Cloning. Simultaneously, the board surface is divided vertically or horizontally into subregions and each subcircuit is assigned to one region. This procedure is repeatedly applied to each of the subcircuits and subregions until the remaining circuit can be trivially placed, for instance, if it consists of a single component only.
The problem can be stated by representing the circuit as a hypergraph. The components correspond to the nodes and the nets correspond to the hyperedges connecting these components (nodes). Thus, decomposing the circuit into two subcircuits with an approximately equal share of components subject to minimizing the number of wires between the two subcircuits corresponds to finding a balanced bipartition (or a bisection) of the hypergraph with a minimal cut.
This results in the so called balanced hypergraph bipar- tition problem, and hypergraph bisection problem, respectively. Both problems are NP-hard, but many heuristics were proposed in literature. Two very common approaches in practice are the heuristic of Fiduccia and Mattheyses for solving the balanced hypergraph bipartition problem and the algorithm of Kernighan and Lin for solving the bisection problem on graphs after transforming the hypergraph to a graph by replacing each hyperedge by a clique.
Both approaches are based on the idea of iterative improvement. Starting with an initial balanced bipartition (or bisection) of the hypergraph (graph), nodes are interchanged between the two subsets, to reduce the size of the cut.
The recursive minimum cut placement can be extended to partitions with more than two subsets. The placement problem then becomes a multiway partition problem. Efficient implementations of the hypergraph multiway partition problem are presented.
A more extensive discussion on partition-based placement methods for VLSI design is given by Lengauer (1990) and a survey is presented in Alpert and Kahng (1995). In Yang and Wong (1996) a partition approach based on the max-flow-min-cut theorem is proposed.