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.

This publication has 0 references indexed in Scilit: