Browse Prior Art Database

Topological Affinities of Nets on a Module

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

Publishing Venue

IBM

Related People

Ditlow, GS: AUTHOR

Abstract

Solutions to nets on a module are ordered efficiently by computing the minimum spanning tree and subtracting it from each allowable solution of the net to obtain the respective differences. The solutions are ordered in accordance with the absolute value of the respective differences.

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

Page 1 of 3

Topological Affinities of Nets on a Module

Solutions to nets on a module are ordered efficiently by computing the minimum spanning tree and subtracting it from each allowable solution of the net to obtain the respective differences. The solutions are ordered in accordance with the absolute value of the respective differences.

The interconnections between chips on a module are "trees". These trees assume a variety of topologies. They can range from chains to trees which fan out only from the driver to each receiver. Some typical configurations for a 5-pin net are:

(Image Omitted)

Assume that the above configurations are allowable solutions for a given technology. Notice that there are some 5-pin trees which are not included. For example,

(Image Omitted)

This solution may not be allowable for some electrical reason which was verified through circuit analysis.

The following is an efficient procedure for selecting which trees to process first. First, compute the minimum spanning tree for a net.

(Image Omitted)

Create an identifying vector for this tree by traversing it in a depth- first search order (keeping track of the fan out at each vertex).

(Image Omitted)

Each allowable tree also has an identifying vector.

(Image Omitted)

If the minimum spanning tree (MST) is in the solution of trees, then the task is finished. Otherwise, one must process the trees in some order. The order resulting from the following procedure is preferred. (1) Subtract the MST vector from eac...