Abstract:

The floorplanning problem consists of arranging a set of rectangular modules on a rectangular chip area so that to optimize an appropriate measure of performance. This problem is known to be NP-hard, and is particularly challenging if the chip dimensions are fixed, which creates a so-called fixed-outline floorplanning problem. Floorplanning is becoming increasingly important as a tool to design flows in the hierarchical design of Application Specific Integrated Circuits and System-On-Chip. Therefore, it has received much attention recently due to the increasingly high complexity of modern chip design. We propose a two-stage optimization methodology to solve the floorplanning problem. In the first stage, an attractor-repeller convex optimization model provides the relative positions of the modules on the floorplan. The second stage places and sizes the modules using second-order cone optimization. With the relative positions of modules obtained from the first stage, a Delaunay triangulation is employed to obtain a planar graph and hence a relative position matrix to connect the two stages. Experimental results on standard benchmarks demonstrate that we obtain significant improvements on the best results in the literature for these benchmarks. Most importantly, our methodology provides greater improvement over other floorplanners as the number of modules increases.

This is joint work with Chaomin Luo (Waterloo) and Anthony Vannelli (Guelph).