US6070108A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for congestion driven placement
Assignee: Bell Semiconductor LLC
•
Filing: 1997-08-06
•
Granted: 2000-05-30
•
Expires: 2017-08-06
Abstract
Abstract Integrated circuit chips (IC's) require proper placement of many cells (groups of circuit components) and complex routing of wires to connect the pins of the cells. Because of the large number of the cells and the complex connections required, it is essential that wire routine be done correctly to avoid any congestion of wires. Placement of the cells and the routing of the wires to avoid congestion can be accomplished by determining congestion of various regions of the IC's after an initial placement of the cells and routing of the wires. The present invention discloses a method and apparatus to determine the congestion of the regions and a technique to increase the fictive heights (or, the "working height", or the "working size") of the cells for repeating the placement of the cells if the current placement and routing leads to congestion. The present invention provides for a method of defining regions and line segment. Then, each segment is analyzed to determine the ratio of the wire density of the segment to the wire capacity of the segment. If the ratio is greater than a predetermined value, then the fictive heights of the cells of the affected regions are increased and the placement is repeated.
Inventors
- 👤 Alexander E. Andreev
- 👤 Ivan Pavisic
- 👤 Ranko Scepanovic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:34
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
77 words
A method of placing cells on an integrated circuit device (IC) having cells with pins, nets to define connections between the pins, and columns and channels, said method comprising the steps of: (a) placing the cells on the device; (b) determining wire routing for the nets; (c) determining congested regions; (d) increasing fictive heights of cells of said congested regions; and (e) repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 2
Independent Claim
77 words
A method of placing cells on an integrated circuit device (IC) having cells with pins, nets to define connections between the pins, and columns and channels, said method comprising the steps of: (a) placing the cells on the device; (b) determining wire routing for the nets; (c) determining congested regions; (d) increasing fictive heights of cells of said congested regions; and (e) repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 3
Dependent Claim
28 words
A method according to claim 1 further comprising the step of repeating said steps (b), (c), (d), and (e) of claim 1 until no congested region is found.
Claim 4
Dependent Claim
57 words
A method according to claim 1 wherein said step of determining congested regions comprises steps: defining vertical segments, horizontal segments, and column segments, each segment having a capacity defining maximum number of wires and pins which can be fabricated across said segment; and determining density as the actual number of wires each segment is required to accommodate.
Claim 5
Dependent Claim
56 words
A method according to claim 3 wherein said step of determining congested regions further comprises steps: comparing, for each of said segments, said density with said capacity to obtain a ratio; selecting, for each region of the IC, the highest ration among five segments associated with the region; and comparing said ration to a predetermined value.
Claim 6
Dependent Claim
22 words
A method according to claim 4 wherein said steps of claim 4 are repeated for each of the regions of the IC.
Claim 7
Dependent Claim
18 words
A method according to claim 4 wherein the fictive heights of the cells of congested regions are increased.
Claim 8
Dependent Claim
84 words
A method according to claim 4 wherein the fictive heights of the cells of congested region are not increased if said ration is less than one, increased by eight microns if said ration is not less than one and is less than 1.5 increased by ten microns is said ration is not less than 1.5 increased by ten microns if said ratio is not less than 1.5 and is less than two, increased by twelve microns if said ratio is not less than two.
Claim 9
Dependent Claim
55 words
A method according to claim 3 wherein said column segments are defined by defining a vertical line along the middle of each channel of the IC and defining horizontal lines across the IC, said vertical lines and said horizontal lines orthogonally intersecting the other and dividing the others into vertical segments and horizontal segments respectively.
Claim 10
Dependent Claim
31 words
A method according to claim 8 wherein said horizontal lines are spaced apart by a distance approximately equal to the sum of width of a column and width of a channel.
Claim 11
Dependent Claim
48 words
A method according to claim 3 wherein said column segments are defined by defining a vertical line along the middle of each column of the IC and defining horizontal lines across the IC, said horizontal lines orthogonally intersecting said column lines dividing said column lines into column segments.
Claim 12
Dependent Claim
76 words
An integrated circuit device (IC) having cells with pins, nets to define connection between the pins, columns and channels, and having the cells optimally placed on said IC, said optimal placement method comprising the steps of: placing the cells on the device; determining wire routing for the nets; determining congested regions; increasing fictive heights of cells of said congested regions; and repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 13
Dependent Claim
76 words
An integrated circuit device (IC) having cells with pins, nets to define connection between the pins, columns and channels, and having the cells optimally placed on said IC, said optimal placement method comprising the steps of: placing the cells on the device; determining wire routing for the nets; determining congested regions; increasing fictive heights of cells of said congested regions; and repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 14
Independent Claim
85 words
An apparatus for placing cells on an integrated circuit device (IC) having cells with pins, nets to define connections between the pins, and columns and channels, said apparatus comprising: a processor; a memory connected to said processor; said memory having instructions for said processor to place the cells on the device; determine wire routing for the nets; determine congested regions; increase fictive heights of cells of said congested regions; and repeat the step of placing the cells on the device utilizing the increased fictive heights.
Claim 15
Independent Claim
85 words
An apparatus for placing cells on an integrated circuit device (IC) having cells with pins, nets to define connections between the pins, and columns and channels, said apparatus comprising: a processor; a memory connected to said processor; said memory having instructions for said processor to place the cells on the device; determine wire routing for the nets; determine congested regions; increase fictive heights of cells of said congested regions; and repeat the step of placing the cells on the device utilizing the increased fictive heights.
Claim 16
Dependent Claim
79 words
An apparatus according to claim 12 wherein said memory further comprises instruction to: define segments having a capacity defining maximum number of wires and pins which can be fabricated across said segment; determining density of each of said segments; comparing, for each of said segments, said density with said capacity to obtain a ratio; selecting, for each region of the IC, the highest ratio among five segments associated with the region; and comparing said ratio to a predetermined value.
Claim 17
Dependent Claim
26 words
An apparatus according to claim 12 wherein said memory further comprises instruction to: read cell lists and netlist; and write cell placement and wire routing information.
Claim 18
Dependent Claim
71 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: placing cells on a semiconductor device, said cells having pins requiring routing; determining routing for said pins; defining regions of said semiconductor device; identifying congested regions; increasing fictive heights of cells of said congested regions; and repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 19
Dependent Claim
71 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: placing cells on a semiconductor device, said cells having pins requiring routing; determining routing for said pins; defining regions of said semiconductor device; identifying congested regions; increasing fictive heights of cells of said congested regions; and repeating the step of placing the cells on the device utilizing the increased fictive heights.
Claim 20
Dependent Claim
39 words
A storage medium according to claim 15 wherein said storage medium is selected from a group consisting of semiconductor memory device, magnetic device, optical device, magneto-optical device, floppy diskette, hard drive, CD-ROM, magnetic tape, computer memory, and memory card.
References Cited (Backward Citations)
US5618744A
Cited
US5568322A
Cited
US5491641A
Cited
US5615128A
Cited
US5742510A
Cited
US5495419A
Cited
US5636125A
Cited
US5745363A
Cited
US5682322A
Cited
US5587923A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
Cited
US5661663A
Cited
US5712793A
Cited
US5737236A
Cited
US5808899A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |