Congestion-driven placement using a new multi-partitioning heuristic

Abstract

A novel hierarchical top down placement technique is presented for circuits implemented in the sea-of-gates design style. It is based on a new hypergraph multi-partitioning algorithm, whose time complexity is linear in the number of pins of a circuit. The partitioning algorithm uses Steiner tress for the modeling of net topologies, which allows taking wiring congestion into account during placement. This leads to a more sophisticated balance criterion compared to conventional min-cut algorithms and consequently to a better distribution of active elements and wiring over the chip area. Experimental results show that the application of the new method makes the wiring of designs considerably easier.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>