Compaction with Automatic Jog Introduction
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 O(n4) on input of size n. Several heuristics are suggested for improving the algorithm's practical performance. The compaction algorithm takes as input a data structure called a sketch, which explicitly distinguished between flexible components (wires) and rigid components (modules). The algorithms 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1986
- Accession Number
- ADA176525
Entities
People
- F. M. Maley
Organizations
- Massachusetts Institute of Technology