Optimal module sizing in VLSI Floorplanning by nonlinear programming

Floorplanning is the VLSI design problem of deciding the position and shapes of all modules (e.g., memory or random logic) in order to minimize the chip area and satisfy all constraints. The modules may not be fixed in shape-the ratio of height to width may be modified in order to achieve minimal chip area. In the CADRE (AT&T) and Planar Package Planner (IBM) floorplanning systems, relative positions of the modules are specified by a ‘relative position graph’. Given the relative positions, a heuristic attempts to determine the optimal shape of each module subject to the relative orientations dictated by the graph and also interconnection requirements, to minimize the chip area. In CADRE, the heuristics iterate between improving horizontal and vertical module dimensions; the IBM system uses a Simplex-method based heuristic. These heuristics are not guaranteed to solve the problem exactly. Consequently, it is not known how far the heuristic solution is from optimal, and it is not obvious when to terminate the heuristic. In this paper it is shown that, given the relative positions, one can compute the provably optimal shape of each module, by transforming the problem into a convex nonlinear programming problem. Each local minimum of such a problem must also be a global minimum. The method is illustrated by applying it to an example solved by IBM.