Minplex - A Compactor that Minimizes the Bounding Rectangle and Individual Rectangles in a Layout

Abstract

This paper presents a graph-theoretic compactor that minimizes the areas of the bounding rectangle and the individual rectangles in the layout. The minimization problem is formulated as a two-stage process. In the first stage, the area of the bounding rectangle is minimized, and in the second stage, the weighted sum of the areas of the individual rectangles is minimized, which automatically minimizes the lengths of the inter-connecting wires. This approach provides a general and rigorous method for wirelength minimization. Algorithms for generating and solving the constraints graph are proposed. The minimization algorithm includes a graph-theoretic Simplex method that can be used to solve minimization problems whose constraints can be expressed in terms of a directed graph.