Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Connecting Three Points While Minimizing Cost

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

Publishing Venue

IBM

Related People

Donath, WE: AUTHOR [+2]

Abstract

This publication relates to a procedure for connecting three points in an electronic circuit with minimum cost. When designing the wiring (connections among electronic components) of integrated circuit chips, printed circuit boards, and other packages, it is frequently necessary to connect three points together so that they become electrically common. A cost, indicative of wiring congestion and other factors, can be associated with each wiring arrangement. A procedure is described for finding the lowest cost routing of three-point connections.

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

Page 1 of 5

Connecting Three Points While Minimizing Cost

This publication relates to a procedure for connecting three points in an electronic circuit with minimum cost. When designing the wiring (connections among electronic components) of integrated circuit chips, printed circuit boards, and other packages, it is frequently necessary to connect three points together so that they become electrically common. A cost, indicative of wiring congestion and other factors, can be associated with each wiring arrangement. A procedure is described for finding the lowest cost routing of three-point connections.

The procedure described herein is called a three-point maze-runner, because of its resemblance to the two-point maze-runner procedures described by Lee
(1). The procedure is described below, and Fig. 1 shows the same procedure in flow-chart form, with boxes numbered correspondingly. This procedure works not only in a two-dimensional space, but also in a three-dimensional space where some cells reside "on top of" other cells. The procedure is described in terms of a cell grid, but can be described just as well in terms of a graph, with vertices corresponding to cells and edges corresponding to the wiring spaces between cells.

DESCRIPTION OF THE PROCEDURE.

1. Select one of the three points (A, B, and C) as a starting

point. If all three have been used as starting points, go

to step 12 to trace out the best routing.

2. Create a queue containing just entries for the four cells

horizontally or vertically adjacent to the cell containing

the starting point. Each queue entry indicates the cost

starting point. Each queue entry indicates the cost

of wiring from the starting point to this cell, the

direction from which this call was entered, and the

cell's location.

3. Remove the queue entry with lowest cost and make that cell

the current cell".

4. If the current cell is one of the three points to be

connected, but not the starting point of this expansion,

go to step 1. (End of expansion from this starting point.)

5. Select as a "new cell" one of the three which are adjacent

to the current cell either horizontally or vertically

but not in direction from which the current cell

was entered.

6. Calculate the total cost of arriving at the new cell

via the current cell. This is done by adding the

incremental cost of wiring between these two cells to the

total cost associated with the current cell. Cost is

often indicative of wiring congestion in areas traversed

by the wiring, and may include other factors. This

procedure requires that costs be calculated incrementally,

so that each portion of wiring contributes its portion

to the total cost.

7. If the new cell had previously been reached from the same

1

Page 2 of 5

starting point by some other path, compare the old cost

to the total cost just calculated in step 6. If the new

cost is higher (worse), skip to step 11.

8. Record for the cell the cost of wiring to the

starting point (and the direction from the cell t...