Single-Layer Wire Routing.
Abstract
This dissertation concerns the problem of routing wires on a single layer of an integrated circuit or printed circuit board, starting from a sketch of the layer. A sketch specifies the positions of layout features and the topology of the interconnecting wires. Efficient algorithms are presented that (1) determine whether a sketch is routable, and (2) produce for a routable sketch a proper routing that minimizes both individual and total wire length. Both algorithms run in time O(sq n log n) on input of size n, and both are simple to implement. They can be adapted to a variety of wiring models, and they subsume most of the polynomial-time algorithms in the literature for single-layer routing and routability testing. The algorithms are based on two theorems concerning the routings of a sketch. One states that a sketch is routable if and only if for each cut between fixed features, the total amount of wiring forced to cross the cut is no greater than the length of the cut. The second theorem states that every routable sketch has a routing that simultaneously minimizes the length of every wire, and that it characterizes the wires in this routing. To formalize and prove these theorems, a rich mathematical theory of single-layer wire routing is developed. Its central tool, which is new to the wire-routing literature, is the lifting of wires and cuts to a simply connected topological covering space of the routing region.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1987
- Accession Number
- ADA186990
Entities
People
- F. M. Maley
Organizations
- Massachusetts Institute of Technology