Browse Prior Art Database

Wiring Machine

IP.com Disclosure Number: IPCOM000048881D
Original Publication Date: 1982-Apr-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 6 page(s) / 67K

Publishing Venue

IBM

Related People

Denneau, MM: AUTHOR [+2]

Abstract

A major part of the design of any integrated circuit chip is the wire-routing operation. Basically, once a circuit has been partitioned into chips, and components placed within each chip, wiring involves the assignment of metallization tracks in order to interconnect the components. The wiring program is supplied with a net list which gives sets of points on the chip required to be interconnected.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 6

Wiring Machine

A major part of the design of any integrated circuit chip is the wire-routing operation. Basically, once a circuit has been partitioned into chips, and components placed within each chip, wiring involves the assignment of metallization tracks in order to interconnect the components. The wiring program is supplied with a net list which gives sets of points on the chip required to be interconnected.

Very large scale integrated (VLSI) chips of today may require up to 10,000 wires and take one or more hours of CPU time on a high speed general purpose computer to be wired, often incompletely. The following describes the organization of an inexpensive machine capable of speeding up this operation by a factor of 500 or better.

The following presentation assumes that wiring paths lie along the cells of a rectangular grid. While this is a configuration commonly used, the machine can also accomodate irregular contours for the wiring grid. Provision has also been made to prohibit wires from passing through certain cells which may, for example, house circuit components.

The machine organization lends itself readily to parallel expansion. Thus, for example, 16 units may be configured to route wires almost 16 times as quickly as a single unit. II. THE WIRE ROUTING PROBLEM

A wiring grid is defined here to be a 128 x 128 square matrix, the entries of which are called nodes. Two nodes are adjacent if one is immediately north, south, east, or west of the other. A wire from one node P to another node Q is a sequence (S(1), S(2),..., 8(k)) of nodes with S(1)=P, S(k) equals Q, and such that S(I) is adjacent to S(I-1) for all I between and K. A net is a connected set of wires.

Given a list (source(I), sink(I)) (see original) of M pairs of nodes, the point to point wiring problem is to route a sequence (see original) of wires such that W(I) connects source(I) to sink(I), end such that, except as specified, no two wires have any nodes in common. This definition can be generalized to include point to net and net to net connections. III. WIRE ROUTING ALGORITHM

Let each node of the wiring grid be represented by eight bits, the state bits as follows: B blocked

A active

D distinguished

n north

e east

w west

s south

r reserved

1

Page 2 of 6

The function of these bits will become clear in the ensuing discussion.

For a given sequence of node pairs, the following version of Lee s algorithm will, when successful, determine routes for connections in the point to point wiring problem.

Initialization
1. All eight state bits of each node in the grid are cleared.
2. The blocked bit of each node on the edge of the wiring

grid is set. This prevents attempts to wire outside

the grid.
3. The blocked bits for any prohibited nodes are set.

Wiring
A. Assume that for some N less than M, the first N wires have

been placed, the information being encoded as follows:

1. If a node has been used for a wire, then its blocked

bit is set, and its direction bits indicate...