A Caltech Library Service

2-D Compaction -- A Monte Carlo Method

Mosteller, Richard C. and Frey, Alexander H. and Suaya, Roberto (1987) 2-D Compaction -- A Monte Carlo Method. In: Advanced Research in VLSI: Proceedings of the 1987 Conference. The MIT Press , Cambridge, MA, pp. 173-197. ISBN 0262121212.

[img] PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Additional Information:© 1987 MIT Press.
Record Number:CaltechAUTHORS:20150203-154219033
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54338
Deposited On:04 Feb 2015 01:17
Last Modified:03 Oct 2019 07:57

Repository Staff Only: item control page