# Accession Number:

## ADA169679

# Title:

## Compaction with Automatic Jog Introduction.

# Descriptive Note:

## Master's thesis,

# Corporate Author:

## MASSACHUSETTS INST OF TECH CAMBRIDGE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1986-05-01

# Pagination or Media Count:

## 37.0

# Abstract:

This thesis presents an algorithm for one-dimensional compaction of VLSI layouts. It differs from older methods in treating wires not as objects to be moved, but as constraints on the positions of other circuit components. These constraints are determined for each wiring layer using the theory of planar routing. Assuming that the wiring layers can be treated independently, the algorithm minimizes the width of a layout, automatically inserting as many jogs in wires as necessary. It runs in time 0n4 on input of size n. Several heuristics are suggested for improving the algorithms practical performance. The compaction algorithm takes as input a data structure called a sketch, which explicitly distinguishes between flexible components wires and rigid components modules. The algorithm first finds constraints on the positions of modules that ensure enough space is left for wires. Next, it solves the system of constraints by a standard graph-theoretic technique, obtaining a placement for the modules. It then relies on a single-layer router to restore the wires to each circuit layer. An efficient single-layer router is already known it is able to minimize the length of every wire, though not the number of jogs. As given, the compaction algorithm applies only to a VLSI model that requires wires to run a rectilinear grid. This restriction is needed only because the theory of planar routing and single-layer routers has not yet been extended to other models.

# Descriptors:

# Subject Categories:

- Electrical and Electronic Equipment