Browse Prior Art Database

Ordering Algorithm for FET Circuits in LSI Arrays

IP.com Disclosure Number: IPCOM000078925D
Original Publication Date: 1973-Apr-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Wang, PT: AUTHOR

Abstract

An ordering algorithm for field-effect transistor (FET) circuits in a large-scale integrated (LSI) circuit array includes a scoring mechanism. The algorithm is an iterative process which is heuristic in nature. A starting circuit, typically an off chip driver is chosen to initialize the iteration. A set of circuits called candidate set is constructed from the net structure of circuits. The process of constructing candidate sets and selecting the best circuit repeats until all circuits are ordered.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 2

Ordering Algorithm for FET Circuits in LSI Arrays

An ordering algorithm for field-effect transistor (FET) circuits in a large-scale integrated (LSI) circuit array includes a scoring mechanism. The algorithm is an iterative process which is heuristic in nature. A starting circuit, typically an off chip driver is chosen to initialize the iteration. A set of circuits called candidate set is constructed from the net structure of circuits. The process of constructing candidate sets and selecting the best circuit repeats until all circuits are ordered.

The score for each circuit is calculated by C or connectivity, or the number of common nets between the set of ordered circuits and a candidate circuit; Z or the size of a circuit, or the number of nets associated with the candidate circuit; N or the number of new nets generated by a candidate circuit or N = X-C; U or the number of incompleted nets, or an indication of how many nets are still incomplete after an i/th/ iteration; D or the degree of completeness or an indication of the potential of a candidate to complete its associated net, as given by the following equations: a. Sum Form

D = CT/i/ (x-)+1 over CT(x)

b. Product Form

n NET(x).

Where

CT(x) = the total number of distinct circuits in the

set of nets associated with the circuit x.

CT/i/ (x) = a subset of CT(x), denoting the number of

distinct circuits that have been ordered after the

i/th/ iteration.

NT(n) = the total number of circuits in the net n.

NT/i/(n) = a subset of NT(n), deno...