US6123736A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for horizontal congestion removal
Assignee: Bell Semiconductor LLC
•
Filing: 1997-08-06
•
Granted: 2000-09-26
•
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 placement of the cell and the 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, or pieces, 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 define the regions, or pieces, of the IC, determine various density measurement of the pieces, and adjust the sizes of the pieces to reduce congestion of congested pieces by reallocating space from uncongested pieces to congested pieces. In addition, the present invention discloses the technique of adjusting the sizes of the piece to minimize disturbing the placement and wire routing while the congestion is being reduced. This is accomplished by comparing the vertical location of each of the pieces to the vertical location of the pieces next to it.
Inventors
- 👤 Ivan Pavisic
- 👤 Ranko Scepanovic
- 👤 Alexander E. Andreev
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:02
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
59 words
A method of reducing congestion on an integrated circuit device (IC) having cells, and columns and channels, said method comprising the steps of: defining pieces of the IC surface, each piece having a bottom and a top; determining density of said pieces; resizing said pieces depending upon said density of said pieces; and smoothing rows of said resized pieces.
Claim 2
Independent Claim
59 words
A method of reducing congestion on an integrated circuit device (IC) having cells, and columns and channels, said method comprising the steps of: defining pieces of the IC surface, each piece having a bottom and a top; determining density of said pieces; resizing said pieces depending upon said density of said pieces; and smoothing rows of said resized pieces.
Claim 3
Dependent Claim
48 words
A method according to claim 1 where said step of defining pieces comprises the steps of: defining a vertical line in each channel of said IC; and defining horizontal lines across the surface of the IC, such that said vertical lines and said horizontal lines delimiting rectangular pieces.
Claim 4
Dependent Claim
12 words
A method according to claim 2 where said horizontal lines are equidistant.
Claim 5
Dependent Claim
29 words
A method accordingly to claim 2 wherein said horizontal lines are 100 grid units apart from each other wherein grid units are the unit of measurement on the IC.
Claim 6
Dependent Claim
41 words
A method according to claim 1 wherein said step of determining density of each of said pieces comprises the steps of: determining cell density of said pieces; determining block density of said pieces; and determining horizontal routing density of said pieces.
Claim 7
Dependent Claim
24 words
A method according to claim 5 wherein said cell density is the sum of the heights of cells located in each of said pieces.
Claim 8
Dependent Claim
33 words
A method according to claim 5 wherein said block density is the sum of the heights of cell blocks for each of said pieces, said cell blocks comprising pins, vias, and obstacle wires.
Claim 9
Dependent Claim
24 words
A method according to claim 5 wherein said horizontal routing density is the sum of heights of the wires crossing each of said pieces.
Claim 10
Dependent Claim
21 words
A method according to claim 5 wherein said horizontal routing density is the sum of all the wires traversing said piece.
Claim 11
Dependent Claim
42 words
A method according to claim 5 wherein said step of determining horizontal routing density comprises the steps of: determining routing of wires of the IC to connect pins of the IC; and summing the number of wires traversing each of said pieces.
Claim 12
Dependent Claim
44 words
A method according to claim 5 where said step of determining horizontal routing density comprises the steps of: producing an edgelist having a list of edges describing wire routing of the IC; and summing the probabilities of the edges crossing each of said pieces.
Claim 13
Dependent Claim
17 words
A method according to claim 11 wherein probability of a normal edge crossing a piece is one.
Claim 14
Dependent Claim
29 words
A method according to claim 11 wherein probability of a superedge crossing a piece is inverse of the number of vertical pieces said superedge traverses for each affected column.
Claim 15
Dependent Claim
138 words
A method according to claim 11 wherein probability of a superedge crossing a piece is determined by a linear function comprising the steps of: identifying horizontal grid line, in each column, having highest probability; assigning zero probability to all grid lines lying above and lying below the superedge boundary; forming a linear probability function having said identified grid line with the highest probability and extending on one side of said identified grid line to the high boundary of the superedge and on the other side of said identified grid line to the low boundary of the superedge and having the property that the sum of the probabilities for all horizontal grid line is one; determining probability of each of grid lines lying within the superedge; and summing probability of all grid lines lying within each of the pieces.
Claim 16
Dependent Claim
129 words
A method according to claim 5 wherein said step of resizing of said pieces comprises the steps of: defining a value H as the size of a column segment in grid units; defining a function, size(i, j, q), as representing the greater value between cell density and a sum of block density and horizontal routing density multiplied by a first factor q, wherein i represents the column, j represents the pieces of the column, and q is said first factor; adjusting said H by multiplying said H by a predetermined piece size factor Q; determining the value of said first factor q satisfying the following equation: ##EQU16## wherein j min is the first piece of the column i, and i max is the last piece of the column i.
Claim 17
Dependent Claim
19 words
A method according to claim 15 wherein said predetermined piece size factor Q is a desired piece size factor.
Claim 18
Dependent Claim
19 words
A method according to claim 15 wherein said predetermined piece size factor Q is a maximum piece size factor.
Claim 19
Dependent Claim
19 words
A method according to claim 15 wherein said predetermined piece size factor Q is a minimum piece size factor.
Claim 20
Dependent Claim
17 words
A method according to claim 15 wherein said predetermined piece size factor Q is between 0.80and 1.20.
Claim 21
Dependent Claim
87 words
A method according to claim 1 wherein said step of smoothing said resized pieces comprises the steps of: a. traversing each of the rows of pieces from left to right; b. comparing bottom position of a first piece to bottom position of a second piece wherein said second piece is immediately before said first piece; and c. modifying the bottom position of said first piece if the bottom position of said first piece is less than the bottom position of said second piece less a predetermined value.
Claim 22
Dependent Claim
29 words
A method according to claim 20, further comprising the step of: d. repeating steps b and c while traversing each of the rows of pieces from right to left.
Claim 23
Dependent Claim
19 words
A method according to claim 21 wherein said steps a to d are repeated until no modifications are made.
Claim 24
Dependent Claim
25 words
A method according to claim 20 wherein said predetermined value is determined by a predetermined factor ε multiplied by predetermined initial size of said pieces.
Claim 25
Dependent Claim
16 words
A method according to claim 23 wherein said predetermined factor ε is between 0.05 and 0.10.
Claim 26
Dependent Claim
18 words
A method according to claim 23 wherein said predetermined initial size of said pieces is 100 grid units.
Claim 27
Dependent Claim
27 words
A method of reducing congestion on an integrated circuit device according to claim 1 further comprising the step of removing excess heights from pieces of over-allocated segments.
Claim 28
Dependent Claim
66 words
A method according to claim 26 wherein said step of removing excess height comprises the steps of: determining shortage of space by subtracting column segment height from sum of heights of said pieces of the column; and regaining heights from said pieces of said over-allocated segments by reclaiming space allocated to said pieces over and above maximal heights of said pieces, said maximal height being predetermined.
Claim 29
Dependent Claim
40 words
A method according to claim 27 further comprising the step of regaining heights from said pieces of said over-allocated segments by reclaiming space allocated to said pieces over and above desired heights of said pieces, said desired height being predetermined.
Claim 30
Dependent Claim
41 words
A method according to claim 28 further comprising the step of regaining heights from said pieces of said over-allocated segments by reclaiming space allocated to said pieces over and above a minimal height of said pieces, said minimal height being predetermined.
Claim 31
Dependent Claim
27 words
A method of reducing congestion on an integrated circuit device according to claim 1 further comprising the step of adding extra heights to pieces of under-allocated segments.
Claim 32
Dependent Claim
51 words
A method according to claim 30 wherein said step of adding extra heights to cells comprises the steps of: determining excess space by subtracting sum of heights of said pieces of column segment from column segment height; and uniformly distributing said excess space to each of pieces of said column segment.
Claim 33
Dependent Claim
41 words
A method according to claim 31 wherein said step of uniformly distributing comprises the steps of: determining maximum height of each of said pieces of the column segment; and adding space to each of said pieces up to its maximum height.
Claim 34
Dependent Claim
26 words
A method according to claim 32 wherein said step of uniformly distributing comprises the steps of adding excess space to an arbitrary piece of said segment.
Claim 35
Dependent Claim
20 words
A method according to claim 1 further comprising a step of modifying placement of cells within each of said pieces.
Claim 36
Dependent Claim
38 words
A method according to claim 34 wherein said step of modifying placement of cells comprises the step of uniformly adding excess space of said pieces to gaps between the cells of said pieces until no excess space remains.
Claim 37
Dependent Claim
39 words
A method according to claim 34 wherein said step of modifying placement of cells comprises the step of uniformly removing space from gaps between the cells of said pieces until there is no shortage of space within said pieces.
Claim 38
Dependent Claim
19 words
A method according to claim 1, wherein said step of smoothing rows reduces variations in sizes of row-wise-adjacent pieces.
Claim 39
Independent Claim
72 words
An apparatus for reducing congestion on an integrated circuit device (IC) having cells, and columns and channels, said apparatus comprising: a processor; a memory connected to said processor; said memory having instructions for said processor to define pieces of columns on the IC surface, each piece having a bottom and a top; determine density of said pieces; resize said pieces depending upon said density of said pieces; and smooth said resized pieces.
Claim 40
Independent Claim
72 words
An apparatus for reducing congestion on an integrated circuit device (IC) having cells, and columns and channels, said apparatus comprising: a processor; a memory connected to said processor; said memory having instructions for said processor to define pieces of columns on the IC surface, each piece having a bottom and a top; determine density of said pieces; resize said pieces depending upon said density of said pieces; and smooth said resized pieces.
Claim 41
Dependent Claim
27 words
An apparatus according to claim 38 wherein said memory further comprises instruction for said processor to: adjust size of said prices; and modify placement of the cells.
Claim 42
Dependent Claim
26 words
An apparatus according to claim 38 wherein said memory further comprises instruction for said processor to: read cell lists and netlist; and write new cell placement.
Claim 43
Dependent Claim
19 words
An apparatus according to claim 38, wherein said step of smoothing rows reduces variations in sizes of row-wise-adjacent pieces.
Claim 44
Dependent Claim
53 words
A machine-readable storage medium containing instructions for a processor, said instructions comprising steps of: defining pieces of columns of an integrated circuit chip (IC) surface, each piece having a bottom and a top; determining density of said pieces; resizing said pieces depending upon said density of said pieces; and smoothing said resized pieces.
Claim 45
Dependent Claim
53 words
A machine-readable storage medium containing instructions for a processor, said instructions comprising steps of: defining pieces of columns of an integrated circuit chip (IC) surface, each piece having a bottom and a top; determining density of said pieces; resizing said pieces depending upon said density of said pieces; and smoothing said resized pieces.
Claim 46
Dependent Claim
39 words
A storage medium according to claim 42 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.
Claim 47
Dependent Claim
21 words
A machine-readable storage medium according to claim 42, wherein said step of smoothing rows reduces variations in sizes of row-wise-adjacent pieces.
References Cited (Backward Citations)
US5568322A
Cited
US5491641A
Cited
US5615128A
Cited
US5742510A
Cited
US5495419A
Cited
US5636125A
Cited
US5745363A
Cited
US5682322A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
Cited
US5661663A
Cited
US5712793A
Cited
US5835378A
Cited
US5808899A
Cited
US5870312A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-26 | 2004-03-27 | 2004-09-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-26 | 2008-03-27 | 2008-09-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-26 | 2012-03-27 | 2012-09-26 | $7700.00 | Window Closed / Lapsed |