Browse Prior Art Database

Automatic Embedding Software

IP.com Disclosure Number: IPCOM000047058D
Original Publication Date: 1983-Sep-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 49K

Publishing Venue

IBM

Related People

Rogoyski, E: AUTHOR [+2]

Abstract

An algorithm is described which improves automatic chip wiring quality by reducing the manual interactive steps normally required to embed overflow connections when wiring chips. Automatic wiring programs typically place most of the wiring connections when wiring chips. However, overflows from the automatic wiring program that cannot be placed must be wired manually in a process called embedding. In this regard, it is known that unwired two-point connections usually result from congestion in the neighborhood of at least one of the end points. These neighborhoods are identified indirectly by testing the end points for primary or secondary metal (pin metal). This approach has been found to be simple and statistically valid. An automatic embedding strategy is employed here, as embodied in the algorithm shown in the figure.

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

Page 1 of 3

Automatic Embedding Software

An algorithm is described which improves automatic chip wiring quality by reducing the manual interactive steps normally required to embed overflow connections when wiring chips. Automatic wiring programs typically place most of the wiring connections when wiring chips. However, overflows from the automatic wiring program that cannot be placed must be wired manually in a process called embedding. In this regard, it is known that unwired two-point connections usually result from congestion in the neighborhood of at least one of the end points. These neighborhoods are identified indirectly by testing the end points for primary or secondary metal (pin metal). This approach has been found to be simple and statistically valid. An automatic embedding strategy is employed here, as embodied in the algorithm shown in the figure. The overflows from the automatic wiring program are introduced into the algorithm, one by one, as represented by the "enter" legend at the top of the figure. The first step in the embedding algorithm is to let the overflow connection to be embedded be the active connection to be addressed by the algorithm. This is represented by block 1 in the figure. Next, the process acts to determine the "region" of congestion at the respective end points of the overflow connection.

In this regard, it is desirable to select the largest area possible surrounding the end points as the "region" or neighborhood of congestion. The major limitation in this selection is the size of the working store. This step is represented by block 3 in the figure. After determining the "region" of congestion at the respective end points of the overflow connection being processed, the next step in the algorithm is to endeavor to connect the end points of this connection. This is achieved, as represented by block 5, through operation of a maze run algorithm, as understood by those skilled in the art. The maze run algorithm acts to make the connection by going around, under, over, etc., the interfering wires.

If the maze run process fails, i.e., the connection cannot be made between its intended points because of intervening wires, then a segment of one of the intervening wires is selected to be removed. This is represented by block 9 in the figure. With the wire segment removed, a maze run is again carri...