CaltechTHESIS
  A Caltech Library Service

Monte Carlo methods for 2-D compaction

Citation

Mosteller, R. C. (1986) Monte Carlo methods for 2-D compaction. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-03202008-091615

Abstract

A new method of compaction for VLSI circuits is presented. Compaction is done simultaneously in two dimensions and uses a Monte Carlo simulation method often referred to as simulated annealing for optimization. A new curvilinear representation for VLSI circuits, specifically chosen to make the compaction efficient, is developed. Experiments with numerous cells are presented that demonstrate this method to be as good as, or better than the hand compaction previously applied to these cells. Hand compaction was the best previously known method of compaction. An experimental evaluation is presented of how the run time complexity grows as the number, N, of objects in the circuit increases. The results of this evaluation indicates that the run time growth is order O(N log(A))f(d) where f(d) is a function of the density, d, and A is the initial cell area. The function f(d) appears to have negligible or no dependence on N. A hierarchical composition approach is developed which takes advantage of the capability of the curvilinear representation and the 2—dimensional compaction technique.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Major Option:Computer Science
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • Kajiya, James Thomas
Thesis Committee:
  • Unknown, Unknown
Defense Date:19 May 1986
Record Number:CaltechETD:etd-03202008-091615
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-03202008-091615
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1035
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:03 Apr 2008
Last Modified:12 Feb 2014 00:31

Thesis Files

[img] PDF (Mosteller_rc_1986.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

14Mb

Repository Staff Only: item control page