US5930500A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel processor implementation of net routing
Assignee: Bell Semiconductor LLC
•
Filing: 1997-02-11
•
Granted: 1999-07-27
•
Expires: 2017-02-11
Abstract
Abstract A method for maximizing effectiveness of parallel processing, using multiple processors, to connect pins of a net of an integrated circuit is disclosed. The method requires the pins to be partitioned into sets of pins and the sets of pins to be further partitioned into meta-sets of the sets of pins. The sets and the meta-sets are connected using a minimal spanning tree algorithm, and the connected sets are made to share a pin, thereby ensuring that the whole net is interconnected without creating a loop in the routing. In addition, because the partitions and the sets of partitions average approximately the same number of pins, the work load can easily be balanced between the processors.
Inventors
- 👤 Ranko Scepanovic
- 👤 Edwin Jones
- 👤 Alexander E. Andreev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 00:32
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/394
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
48 words
A method of organizing pins of a net, said method comprising: partitioning the pins into a plurality of sets, each set having at least a predetermined number of pins; and constructing a minimal spanning tree having vertices and edges, said vertices of said spanning tree representing the sets.
Claim 2
Independent Claim
48 words
A method of organizing pins of a net, said method comprising: partitioning the pins into a plurality of sets, each set having at least a predetermined number of pins; and constructing a minimal spanning tree having vertices and edges, said vertices of said spanning tree representing the sets.
Claim 3
Dependent Claim
87 words
The method according to claim 1 wherein said step of partitioning the pins comprises: (a) constructing a neighborhood of pins for each of the pins, each neighborhood having a center pin; (b) calculating a cluster ratio for each of said neighborhoods; (c) selecting neighborhoods based upon the cluster ratios calculated in step (b); (d) assigning each of the pins to a center pin for one of the neighborhoods selected in step (c); and (e) defining a partition as a center pin and all of its assigned pins.
Claim 4
Dependent Claim
60 words
A computer implemented method for connecting pins of a net, said method comprising: creating partitions of pins and sets of partitions; constructing a minimal spanning tree (MST) for the pins in each partition, a MST for the partitions in each set, and a MST for the sets; and assigning construction of each MST to one of a plurality of processors.
Claim 5
Dependent Claim
60 words
A computer implemented method for connecting pins of a net, said method comprising: creating partitions of pins and sets of partitions; constructing a minimal spanning tree (MST) for the pins in each partition, a MST for the partitions in each set, and a MST for the sets; and assigning construction of each MST to one of a plurality of processors.
Claim 6
Dependent Claim
104 words
The method according to claim 3 wherein said step of creating pin partitions comprises: defining each of the pins as a center pin; for each said center pin, defining a neighborhood by: i. finding a nearest pin from said center pin that does not already belong to said neighborhood; ii. expanding a bounding box to include said nearest pin in said neighborhood; iii. including, within said neighborhood, any other pins which fall within said bounding box and are not already a part of said neighborhood; and iv. repeating steps i to iii until at least a predetermined number of pins belong to said neighborhood.
Claim 7
Dependent Claim
62 words
The method according to claim 4 further comprising: a. determining a cluster ratio for each of said neighborhoods; b. selecting a first neighborhood with the highest cluster ratio; c. denoting the pins of said selected neighborhood as being covered; d. selecting a next neighborhood with the next highest cluster ratio; and e. repeating steps c and d until all pins are covered.
Claim 8
Dependent Claim
54 words
The method according to claim 5 further comprising: identifying the center pins of said selected neighborhoods; assigning each of the pins to the identified center pin closest to said pin; and forming a plurality of partitions, each partition including one of the identified center pins and all the pins assigned to said center pin.
Claim 9
Dependent Claim
169 words
The method according to claim 3 wherein said step of constructing the minimal spanning trees (MSTs) comprises: a. identifying a first pin in a first partition and a second pin in a second partition where the distance between said first pin and said second pin is less than the distance between any other pair of pins in which one is selected from the first partition and one is selected from the second partition; b. determining a first distance between the first pin and another pin in the first partition; c. determining a second distance between the second pin and another pin in the second partition; d. assigning the first pin to the second partition if the first distance is greater than the second distance; and e. assigning the second pin to the first partition if the second distance is greater than the first distance; and f. constructing the MST for the first partition, including the assigned pin, and constructing the MST for the second partition, including the assigned pin.
Claim 10
Independent Claim
62 words
An apparatus for connecting pins of a net comprising: a plurality of processors; memory connected to said processors; said memory having instructions for said processors to partition the pins, to construct a minimal spanning tree using the partitions as nodes of said tree; and to assign each of the partions to one of said processors to connect the pins in said partition.
Claim 11
Independent Claim
62 words
An apparatus for connecting pins of a net comprising: a plurality of processors; memory connected to said processors; said memory having instructions for said processors to partition the pins, to construct a minimal spanning tree using the partitions as nodes of said tree; and to assign each of the partions to one of said processors to connect the pins in said partition.
Claim 12
Dependent Claim
15 words
The apparatus according to claim 8 wherein said processors operate simultaneously to connect the pins.
Claim 13
Dependent Claim
15 words
The apparatus according to claim 8 further comprising a storage device connected to said processors.
Claim 14
Dependent Claim
15 words
The apparatus according to claim 10 wherein said storage device is a computer hard drive.
Claim 15
Dependent Claim
56 words
The apparatus according to claim 8 wherein the instructions for said processors to partition the pins include instructions to: define neighborhoods of pins, each neighborhood having a center pin and a cluster ratio; select the neighborhoods that are most clustered, based on the cluster ratios; and define partitions using the center pins of the selected neighborhoods.
Claim 16
Dependent Claim
55 words
A computer storage medium containing instructions for organizing integrated circuit pins for routing purposes, said instructions comprising: partitioning the pins into a plurality of sets, each set having at least a predetermined number of pins; and constructing a spanning tree having vertices and edges, said vertices of said spanning tree representing said plurality of sets.
Claim 17
Dependent Claim
55 words
A computer storage medium containing instructions for organizing integrated circuit pins for routing purposes, said instructions comprising: partitioning the pins into a plurality of sets, each set having at least a predetermined number of pins; and constructing a spanning tree having vertices and edges, said vertices of said spanning tree representing said plurality of sets.
Claim 18
Dependent Claim
42 words
The storage medium according to claim 13 wherein said storage medium is selected from a group consisting of a magnetic device, an optical device, a magneto-optical device, a floppy diskette, a CD-ROM, magnetic tape, a computer hard drive, and a memory card.
Claim 19
Independent Claim
41 words
A method of routing connections between pins in a net, comprising: partitioning the pins into sets; identifying distances between pairs of sets; routing connections between the sets based on the distances identified; and routing connections between the pins in each set.
Claim 20
Independent Claim
41 words
A method of routing connections between pins in a net, comprising: partitioning the pins into sets; identifying distances between pairs of sets; routing connections between the sets based on the distances identified; and routing connections between the pins in each set.
Claim 21
Dependent Claim
19 words
A method according to claim 15, wherein connections are routed between the sets by constructing a minimum spanning tree.
Claim 22
Dependent Claim
30 words
A method according to claim 15, wherein the distance between a pair of sets is defined as a distance between two closest pins, one from each set in the pair.
Claim 23
Dependent Claim
29 words
A method according to claim 17, further comprising a step of, for each pair of sets, assigning one of the two closest pins to both sets in the pair.
Claim 24
Dependent Claim
28 words
A method according to claim 15, further comprising a step of assigning each set to one of a plurality of processors for routing connections between the pins therein.
Claim 25
Dependent Claim
18 words
A method according to claim 15, further comprising a step of partitioning the sets into higher level sets.
Claim 26
Dependent Claim
38 words
A method according to claim 20, further comprising a step of repeating said step of partitioning sets into higher level sets until each higher level set has no more than approximately a predetermined number of lower level sets.
Claim 27
Dependent Claim
19 words
A method according to claim 15, wherein each set has no more than approximately a predetermined number of pins.
Claim 28
Dependent Claim
22 words
A method according to claim 15, wherein connections are routed between the pins in a set by constructing a minimum spanning tree.
References Cited (Backward Citations)
US4630219A
Cited
US4858143A
Cited
US4908772A
Cited
US5202840A
Cited
US5590063A
Cited
US5682321A
Cited
US5798936A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |