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.

Files

Additional details