Global Floorplanning via Semidefinite Programming

A major task in chip design involves identifying the location and shape of each major design block/module in the footprint of the chip. This is commonly known as floorplanning. The first step of this task is known as global floorplanning and involves identifying a location for each module that minimizes wire length and leaves sufficient area for each module. Existing global floorplanning methods either have nonconvex problem formulation or have trivial global solutions with no guarantee on the quality of the result. We propose to model the global floorplanning problem as a Semi-Definite Programming (SDP) problem with a rank constraint. We replace the rank constraint with a direction matrix and convexify the problem, whose solution is shown to be a global optimum if an appropriate direction matrix is chosen. To calculate the direction matrix, a convex iteration algorithm is used where the problem is decomposed into two SDP sub-problems. Furthermore, we introduce a series of techniques that enhance the flexibility, accuracy, and efficiency of our algorithm. The results show that our proposed method reduces the average wirelength by at least from 3.02% to 20.01% on different benchmarks and outline aspect ratios.