Accession Number : ADA186990

Title :   Single-Layer Wire Routing.

Descriptive Note : Technical rept.,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Maley, F M

PDF Url : ADA186990

Report Date : Aug 1987

Pagination or Media Count : 363

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.

Descriptors :   *CUTTING, *INTEGRATED CIRCUITS, *LAYERS, *PRINTED CIRCUIT BOARDS, *ROUTING, *WIRE, ALGORITHMS, EFFICIENCY, INPUT, LENGTH, LIFT, MATHEMATICS, POLYNOMIALS, SIZES(DIMENSIONS), THEOREMS, THEORY, TOOLS, TOPOLOGY

Subject Categories : Electrical and Electronic Equipment

Distribution Statement : APPROVED FOR PUBLIC RELEASE