Browse Prior Art Database

Weighted and Iterative Multi-wire Routing

IP.com Disclosure Number: IPCOM000050854D
Original Publication Date: 1982-Dec-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 7 page(s) / 87K

Publishing Venue

IBM

Related People

Moore, A: AUTHOR [+2]

Abstract

The efficient iterative capabilities of electronic data processing are employed for the design of wire routes on printed circuit cards. The individual wire paths are routed using an algorithm in which all surrounding points at each point as the path is defined are assigned cumulative penalty weights. Alternative paths for individual wires are examined until each path is eliminated by defined barriers. A path of minimum penalty weight is sought. Paths for multiple wires are first plotted by assigning a low penalty weight to crossovers of the wires. The wires are replotted iteratively, with progressively higher penalty weights assigned to crossovers, vias, and other factors.

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 18% of the total text.

Page 1 of 7

Weighted and Iterative Multi-wire Routing

The efficient iterative capabilities of electronic data processing are employed for the design of wire routes on printed circuit cards. The individual wire paths are routed using an algorithm in which all surrounding points at each point as the path is defined are assigned cumulative penalty weights. Alternative paths for individual wires are examined until each path is eliminated by defined barriers. A path of minimum penalty weight is sought. Paths for multiple wires are first plotted by assigning a low penalty weight to crossovers of the wires. The wires are replotted iteratively, with progressively higher penalty weights assigned to crossovers, vias, and other factors.

Single Wire Routing. The single wire router is a callable routine which finds the minimum weighted path through a grid upon which positive penalty weights are assigned. One such single wire router is described specifically here. The penalty weights and start and end points of each wire are provided by the multi- wire router routine. In a typical embodiment, the alternatives requiring consideration are limited by the directions of plot being only horizontal, vertical, diagonal at 45 degrees, and via. A via is a connection through the card to continue a wire on the opposite side.

In a typical application, a circuit card upon which wires are to be routed is 20 inches by 20 inches, and vias are used to permit wires on both sides. Each side is represented in memory as a regular grid of points of 40 per inch, which total
1.3 million grid points for both sides. As a single wire is routed, each grid point will have a bit set to indicate that the wire-plot search includes the point (visited bit) and will have other bits set to indicate the direction of arrival to that point (arrival direction). Wires are plotted sequentially through adjoining grid points. All points on the perimeter of the search have associated data giving cumulative weight to that point, the next direction which leads to the next point having the lowest cumulative weight (next direction), and that next cumulative weight (next weight). This data constitutes the perimeter structure for each point on the perimeter of the search. The perimeter structures are kept in a list which is sorted by next weight.

All alternative routes of an individual wire are plotted up to the point that other alternative routes present are an effective barrier to the route. Essentially, this occurs because visited bits for alternative routes in the search establish that wire has nowhere to go which would not intersect already established alternative routes.

In addition to the sum of penalty weights to each point on the perimeter, the perimeter structure includes the address of the point for up the perimeter structure for the initial point. The perimeter list is a list of one, having one next direction. The visited bit at the initial point is set. The search then proceeds in steps. For ea...