A Unified Approach to Partitioning and Placement

Abstract

We propose a unified formulation and method of solution to two seemingly different problems: partitioning and placement. Both are important in many fields of engineering, especially in VLSI designs. Using a geometrical model and a matrix inner product technique, we demonstrate that partitioning and placement are indeed mathematically equivalent. Depending on whether the cost measure is based on Manhattan or Euclidean square distance, either a linear programming or a quadratic programming approach can be applied for solutions of both problems. We discuss in details two general algorithms based on quadratic programming. The first algorithm is based on eigenvector decomposition, applicable for designs in which all modules are movable. The basic idea of the approach is that it iteratively replaces the high-order nonlinear constraints with linear constraints and then gradually approaches the global optimum. The second algorithm is for designs with some prescribed fixed modules. For such a case, the quadratic programming problem is simplified as a linear system problem. An efficient algorithm has been successfully developed and applied for high complexity VLSI designs. © 1991 IEEE