2-D Compaction -- A Monte Carlo Method

Abstract

In this paper we study the two-dimensional compaction of integrated circuit layouts. A curvilinear representation for circuit elements, specifically chosen to make the compaction efficient, is developed. A Monte Carlo algorithm with heuristic termination criteria was applied to a variety of designs. These experiments give running times for compaction that are consistent with a conjectured average complexity of O(N^(3/2) log^2(N)) where N is the number of non-wire primitives in the cell. These experiments also produced favorable comparisons with hand-designs and with designs using iterated applications of one dimensional compactors. Several cells also were fabricated and tested to demonstrate the practicality of the representation and the compaction technique.