Browse Prior Art Database

Normalized Resistance Clustering Metric

IP.com Disclosure Number: IPCOM000085655D
Original Publication Date: 1976-May-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 3 page(s) / 22K

Publishing Venue

IBM

Related People

Feuer, M: AUTHOR [+3]

Abstract

There are many occasions in the process of laying out integrated circuits when the question arises as to which elements belong together in the same package or portion of a package -- on the basis of their connectivity. This is a key aspect of clustering and partitioning operations.

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

Page 1 of 3

Normalized Resistance Clustering Metric

There are many occasions in the process of laying out integrated circuits when the question arises as to which elements belong together in the same package or portion of a package -- on the basis of their connectivity. This is a key aspect of clustering and partitioning operations.

In computer logic, each logic element (i) is connected to several (c.) electrical voltage nodes, and each such electrical voltage node (j) (commonly referred to as a net) is connected to several (n(j)) logic elements (also known as circuits). Most measures of connectivity among circuits are based on the number of nets shared by the circuits, neglecting the indirect connections through other circuits. This has the disadvantage of giving no estimate of connectivity for circuits which have no direct connections. In partitioning, for example, it is useful to know which two circuits are the least connected.

This technique assigns a node in a circuit net bigraph for each circuit i and each net j of the original logic graph. The order or total number of nodes is C for the circuit nodes and N for the net nodes. A simple example of such a bigraph is shown in the figure.

Each edge of this bigraph connects a circuit i and a net j and is assigned a connectivity (or direct electrical conductance) of: -Proportional to -Beta Cij = c(j). nj , Prop. to >0 & Beta >0.

The distance (or electrical conductance) between two nodes is calculated in the following way. Define:

(Image Omitted)

Then the distance (or electrical conductance) between two nodes is given by: d(mn)...