US5638293A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimal pad location method for microelectronic circuit cell placement
Assignee: Bell Semiconductor LLC
•
Filing: 1994-09-13
•
Granted: 1997-06-10
•
Expires: 2014-09-13
Abstract
Abstract A cell placement is generated for a microelectronic circuit chip. Interconnect points for cell nets are calculated, for example, as gravity points of the cells of the respective nets. Optimal positions for external connection terminals or pads along the border of the circuit are calculated as being the closest positions to the respective interconnect points. The total wirelength of the placement is calculated as including the distances between the interconnect points and the respective pads. Where initial location of the pads results in overlap thereof, clusters of pads are identified and expanded to remove the overlap. Concatenated overlapping clusters resulting from expansion are treated as new clusters and subsequently expanded until all overlap is eliminated. The centers of gravity of the clusters are preserved. During the overlap removal process, initial rectangular coordinates of the pad positions are converted into linear coordinates along the border. After the overlap is eliminated, the linear coordinates are converted back to rectangular coordinates.
Inventors
- 👤 Ranko Scepanovic
- 👤 Patrik D'Haeseleer
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 01:45
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
184 words
A method for optimally locating a plurality of electrical terminals on a border of a microelectronic circuit that includes a plurality of cells, comprising the steps of: (a) performing a placement of said cells; (b) calculating cell interconnect points in said placement corresponding to the electrical terminals respectively; (c) calculating positions on said border at which distances between said positions and said interconnect points are minimum respectively; and (d) locating the terminals at said positions respectively, in which: step (c) enables said positions to be calculated such that the terminals can overlap after performing step (d); and the method further comprises the steps, performed after step (d), of: (e) calculating adjusted positions for said terminals respectively in accordance with a predetermined function such that said overlap is eliminated; and (f) locating the terminals at said adjusted positions respectively; step (c) comprises calculating said positions in two-dimensional coordinates respectively; and step (e) comprises the substeps of: (g) converting said positions into one-dimensional coordinates measured along said border respectively; (h) calculating said adjusted positions in one-dimensional coordinates; and (i) converting said adjusted positions into two-dimensional coordinates.
Claim 2
Independent Claim
184 words
A method for optimally locating a plurality of electrical terminals on a border of a microelectronic circuit that includes a plurality of cells, comprising the steps of: (a) performing a placement of said cells; (b) calculating cell interconnect points in said placement corresponding to the electrical terminals respectively; (c) calculating positions on said border at which distances between said positions and said interconnect points are minimum respectively; and (d) locating the terminals at said positions respectively, in which: step (c) enables said positions to be calculated such that the terminals can overlap after performing step (d); and the method further comprises the steps, performed after step (d), of: (e) calculating adjusted positions for said terminals respectively in accordance with a predetermined function such that said overlap is eliminated; and (f) locating the terminals at said adjusted positions respectively; step (c) comprises calculating said positions in two-dimensional coordinates respectively; and step (e) comprises the substeps of: (g) converting said positions into one-dimensional coordinates measured along said border respectively; (h) calculating said adjusted positions in one-dimensional coordinates; and (i) converting said adjusted positions into two-dimensional coordinates.
Claim 3
Independent Claim
184 words
A method for optimally locating a plurality of electrical terminals on a border of a microelectronic circuit that includes a plurality of cells, comprising the steps of: (a) performing a placement of said cells; (b) calculating cell interconnect points in said placement corresponding to the electrical terminals respectively; (c) calculating positions on said border at which distances between said positions and said interconnect points are minimum respectively; and (d) locating the terminals at said positions respectively, in which: step (c) enables said positions to be calculated such that the terminals can overlap after performing step (d); and the method further comprises the steps, performed after step (d), of: (e) calculating adjusted positions for said terminals respectively in accordance With a predetermined function such that said overlap is eliminated; and (f) locating the terminals at said adjusted positions respectively; step (c) comprises calculating said positions in rectangular coordinates respectively; and step (e) comprises the substeps of: (g) converting said positions into linear coordinates measured along said border respectively; (h) calculating said adjusted positions in linear coordinates; and (i) converting said adjusted positions into rectangular coordinates.
Claim 4
Independent Claim
184 words
A method for optimally locating a plurality of electrical terminals on a border of a microelectronic circuit that includes a plurality of cells, comprising the steps of: (a) performing a placement of said cells; (b) calculating cell interconnect points in said placement corresponding to the electrical terminals respectively; (c) calculating positions on said border at which distances between said positions and said interconnect points are minimum respectively; and (d) locating the terminals at said positions respectively, in which: step (c) enables said positions to be calculated such that the terminals can overlap after performing step (d); and the method further comprises the steps, performed after step (d), of: (e) calculating adjusted positions for said terminals respectively in accordance With a predetermined function such that said overlap is eliminated; and (f) locating the terminals at said adjusted positions respectively; step (c) comprises calculating said positions in rectangular coordinates respectively; and step (e) comprises the substeps of: (g) converting said positions into linear coordinates measured along said border respectively; (h) calculating said adjusted positions in linear coordinates; and (i) converting said adjusted positions into rectangular coordinates.
Claim 5
Independent Claim
122 words
A method for removing overlap between electrical terminals on a border of a microelectronic circuit resulting from initial location of the terminals at positions that allow said overlap, comprising the steps of: (a) identifying overlapping clusters of terminals; (b) calculating adjusted positions for said terminals of said clusters respectively in accordance with a predetermined function such that said overlap is eliminated; and (c) locating the terminals at said adjusted positions respectively, in which: said positions are specified in two-dimensional coordinates prior to performing step (a) respectively; and step (b) comprises the substeps of: (d) converting said positions into one-dimensional coordinates measured along said border respectively; (e) calculating said adjusted positions in one-dimensional coordinates; and (f) converting said adjusted positions into two-dimensional coordinates.
Claim 6
Independent Claim
122 words
A method for removing overlap between electrical terminals on a border of a microelectronic circuit resulting from initial location of the terminals at positions that allow said overlap, comprising the steps of: (a) identifying overlapping clusters of terminals; (b) calculating adjusted positions for said terminals of said clusters respectively in accordance with a predetermined function such that said overlap is eliminated; and (c) locating the terminals at said adjusted positions respectively, in which: said positions are specified in two-dimensional coordinates prior to performing step (a) respectively; and step (b) comprises the substeps of: (d) converting said positions into one-dimensional coordinates measured along said border respectively; (e) calculating said adjusted positions in one-dimensional coordinates; and (f) converting said adjusted positions into two-dimensional coordinates.
Claim 7
Dependent Claim
47 words
A method as in claim 3, in which step (b) comprises calculating said adjusted positions such that centers of gravity of said clusters of terminals after performing step (c) are substantially the same as said centers of gravity of said clusters of terminals before performing step (a).
Claim 8
Dependent Claim
59 words
A method as in claim 3, in which: said clusters of terminals can be concatenated to form overlapping new clusters of terminals after performing step (c); and the method further comprises the steps, performed after step (c), of: (g) identifying said new overlapping clusters of terminals; and (h) calculating new adjusted positions to expand said new clusters of terminals.
Claim 9
Independent Claim
122 words
A method for removing overlap between electrical terminals on a border of a microelectronic circuit resulting from initial location of the terminals at positions that allow said overlap, comprising the steps of: (a) identifying overlapping clusters of terminals; (b) calculating adjusted positions for said terminals of said clusters respectively in accordance with a predetermined function such that said overlap is eliminated; and (c) locating the terminals at said adjusted positions respectively, in which: said positions are specified in rectangular coordinates prior to performing step (a) respectively; and step (b) comprises the substeps of: (d) converting said positions into linear coordinates measured along said border respectively; (e) calculating said adjusted positions in linear coordinates; and (f) converting said adjusted positions into rectangular coordinates.
Claim 10
Independent Claim
122 words
A method for removing overlap between electrical terminals on a border of a microelectronic circuit resulting from initial location of the terminals at positions that allow said overlap, comprising the steps of: (a) identifying overlapping clusters of terminals; (b) calculating adjusted positions for said terminals of said clusters respectively in accordance with a predetermined function such that said overlap is eliminated; and (c) locating the terminals at said adjusted positions respectively, in which: said positions are specified in rectangular coordinates prior to performing step (a) respectively; and step (b) comprises the substeps of: (d) converting said positions into linear coordinates measured along said border respectively; (e) calculating said adjusted positions in linear coordinates; and (f) converting said adjusted positions into rectangular coordinates.
Claim 11
Dependent Claim
32 words
A method as in claim 6, in which step (b) further comprises the substep, performed between steps (d) and (e), of: (g) sorting said positions in accordance with said linear coordinates thereof.
References Cited (Backward Citations)
US3603771A
Cited
US4577276A
Cited
US5119313A
Cited
US5267176A
Cited
US5404313A
Cited
US5072402A
Cited
US5231590A
Cited
US5267177A
Cited
US5303161A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-09 | 2000-12-09 | 2001-06-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-09 | 2004-12-09 | 2005-06-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-09 | 2008-12-09 | 2009-06-10 | $7700.00 | Window Closed / Lapsed |