An exact algorithm for wirelength optimal placements in VLSI design

• An algorithm to compute provably wirelength-optimal floorplans.
• The first wirelength-optimal solutions to 3 of the 5 MCNC block packing benchmarks.
• An optimal floorplan for a real-life instance with 27 rectangles.
• A framework using our algorithm that finds good solutions to larger instances.

We present a new algorithm designed to solve floorplanning problems optimally. More precisely, the algorithm finds solutions to rectangle packing problems which globally minimize wirelength and avoid given sets of blocked regions. We present the first optimal floorplans for 3 of the 5 intensely studied MCNC block packing instances and a significantly larger industrial instance with 27 rectangles and thousands of nets. Moreover, we show how to use the algorithm to place larger instances that cannot be solved optimally in reasonable runtime.