An Attractor-Repeller Approach to Floorplanning

Miguel F. Anjos (anjosstanfordalumni.org)
Anthony Vannelli (vannellicheetah.vlsi.uwaterloo.ca)

Abstract: The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying dimensions) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard discrete optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distance that arises in this derivation. Numerical results demonstrating the potential of our approach are presented.

Keywords: Facilities planning and design, Convex Programming, VLSI Macro-Cell Layout, Global Optimization

Category 1: Applications -- Science and Engineering (Multidisciplinary Design Optimization )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Mathematical Methods of Operations Research, Vol. 56(1):3-27, 2002.

Download:

Entry Submitted: 04/12/2001
Entry Accepted: 04/13/2001
Entry Last Modified: 03/22/2003

Modify/Update this entry