Patent US6058254A successfully refreshed from Google Patents.
US6058254A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for vertical congestion removal
Assignee: Bell Semiconductor LLC
•
Filing: 1997-08-06
•
Granted: 2000-05-02
•
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. The present invention discloses method and apparatus to reduce or to eliminate cell placement and wire routing congestion. To reduce vertical congestion, the cells are moved from congested regions to uncongested regions. The present invention discloses techniques of defining regions as pieces and columns, determining the level of congestion in the regions, and the methods of moving the cells to different columns to reduce congestion while minimizing affects to wire routing. The movement of the cells to other columns may create overlapping of the cells or overloading of the columns. The present invention also discloses the methods to resolve the overlapping and overloading problems.
Inventors
- 👤 Ranko Scepanovic
- 👤 Alexander E. Andreev
- 👤 Ivan Pavisic
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 02:01
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
99 words
A method of reducing congestion on an integrated circuit device (IC) having columns of cells and channels between the columns, said method comprising the steps of: defining pieces and segments of the IC surface, said each of said pieces having an original location and original width; determining density of said pieces; resizing said widths of said pieces depending upon said density of said pieces, said resizing step assigning a new location and a new width to each of said pieces; and modifying placement of the cells depending upon the new locations and the new widths of said resized pieces.
Claim 2
Independent Claim
99 words
A method of reducing congestion on an integrated circuit device (IC) having columns of cells and channels between the columns, said method comprising the steps of: defining pieces and segments of the IC surface, said each of said pieces having an original location and original width; determining density of said pieces; resizing said widths of said pieces depending upon said density of said pieces, said resizing step assigning a new location and a new width to each of said pieces; and modifying placement of the cells depending upon the new locations and the new widths of said resized pieces.
Claim 3
Dependent Claim
50 words
A method according to claim 1 wherein said step of defining pieces and segments 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
30 words
A method accordingly to claim 2 wherein said horizontal lines are approximately 100 grid units apart from each other wherein grid units are the unit of measurement on the IC.
Claim 6
Dependent Claim
68 words
A method according to claim 1 wherein said step of determining density of each of said pieces, P(i, j), comprises the steps of: determining cell density of said piece, denoted cell -- den(i, j); determining block density of said piece, denoted block -- den(i, j); determining horizontal density of said piece, denoted hor -- den(i, j); and determining vertical density of said piece, denoted vert -- den(i, j).
Claim 7
Dependent Claim
25 words
A method according to claim 5 wherein said cell density is the su m of the heights of cells located in each of said pieces.
Claim 8
Dependent Claim
35 words
A method according to claim 5 wherein s aid block density is th e 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
21 words
A method according to claim 5 wherein said horizontal density is an expected number of horizontal routing wires through said piece.
Claim 10
Dependent Claim
20 words
A method according to claim 5 wherein said horizontal density is the sum of probabilities of wires through a piece.
Claim 11
Dependent Claim
42 words
A method according to claim 5 where said step of determining horizontal density comprises the steps of: determining routing of wires of the IC to connect the pins of the IC; and summing the number of wires traversing each of said pieces.
Claim 12
Dependent Claim
43 words
A method according to claim 5 where said step of determining horizontal 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 piece.
Claim 13
Dependent Claim
17 words
A method according to claim 11 wherein probability of a horizontal 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
60 words
A method according to claim 11 wherein probability of a superedge having pins (i1, y1) and (i2, y2) crossing a piece(i, j) at grid unit y is pr(i, y) and is calculated ##EQU14## said y cross being the horizontal grid line crossed by the straight line (i 2 , y 2 )-(i 1 , y 1 ) in column i.
Claim 16
Dependent Claim
28 words
A method according to claim 5 wherein said vertical density of a piece is an expected number of vertical wires through the horizontal grid lines of said piece.
Claim 17
Dependent Claim
35 words
A method according to claim 15 wherein horizontal density of a piece, P(i, j), is determined by a method comprising the steps of summing probability, pr(i, y), of all grid lines located within said piece.
Claim 18
Dependent Claim
33 words
A method according to claim 5 wherein said vertical density, vert -- den(i, j), of a piece, P(i, j), is increased value (y.sub.max -y.sub.min +1)/(top(i, j)-bottom(i, j)+1) to account for a vertical edge.
Claim 19
Dependent Claim
123 words
A method according to claim 5 wherein the probability of a superedge, defined by two pins (i1, y1) and (i2, y2), crossing a piece, for the purposes of increasing said vertical density, vert -- den(i, j), of a piece, P(i, j), is determined by a method comprising the steps of: defining a number of halves by multiplying two and i2 less i1; defining a factor, factor(i), as a division of one by said number of halves if i=i1 or if i=i2, or as a division of two by said number of halves if i1<i<i2; summing probability, pr(i, y), of all grid lines located within said piece, denoted d(i, j); and increasing the vertical density of said piece by a value calculated as ##EQU15##
Claim 20
Dependent Claim
108 words
A method according to claim 5 wherein said step of resizing of said pieces comprises the steps of: for each piece P(i, j), identifying the row, j, of pieces to which said piece belongs; determining the total width of said row j, denoted W(j); defining a desired width of row j by multiplying W(j) with a predefined value Q norm , denoting the product W norm (j); and assigning a new width, denoted w(i, j, q j ), to said piece by finding q j such that the sum of width(i, j, q j ) of each of the pieces of said identified row equals W norm (j).
Claim 21
Dependent Claim
84 words
A method according to claim 19 wherein said width(i, j, q j ) is defined as the greater of hor -- limit or ver -- limit; said hor -- limit defined as ##EQU16## said ver -- limit defined as ##EQU17## said q h is a predetermined value; said column -- only -- width is width of a column of the IC; and said column -- width is the sum of the width of a column and the width of a channel of the IC.
Claim 22
Dependent Claim
105 words
A method according to claim 1 wherein said step of modifying cell placement of cells of a piece comprises the steps of: comparing the new location and the new width of said piece to the original location and the original widths of all the pieces; identifying the pieces, using the original location and the original widths, assigned to the area covered by said piece, the new location and the new width; assigning the cells of said piece to said identified pieces in proportion to the amount of area each of said identified pieces occupy in the new location and the new width of said piece.
Claim 23
Dependent Claim
23 words
A method according to claim 1 further comprising the step of smoothing columns of said pieces prior to modifying placement of the cells.
Claim 24
Dependent Claim
83 words
A method according to claim 22 wherein said step of smoothing columns comprises the steps: a. traversing each column of pieces from bottom to top; b. comparing the left position of a first piece to the left position of a second piece wherein said second piece is immediately before said first piece; c. modifying the left position of said first piece if the left position of said first piece is less than the left position of said second piece less a predetermined value.
Claim 25
Dependent Claim
24 words
A method according to claim 23 further comprising the step of repeating steps b and c while traversing each column from top to bottom.
Claim 26
Dependent Claim
16 words
A method according to claim 24 wherein said steps are repeated until no modification are made.
Claim 27
Dependent Claim
25 words
A method according to claim 23 wherein said predetermined value is determined by a predetermined factor multiplied by the predetermined initial width of said pieces.
Claim 28
Dependent Claim
12 words
A method according to claim 26 wherein said predetermined factor is 0.05.
Claim 29
Dependent Claim
25 words
A method according to claim 26 wherein said predetermined width is the sum of the width of a column and the width of a channel.
Claim 30
Dependent Claim
14 words
A method according to claim 1 further comprising the step of resolving cell overlaps.
Claim 31
Dependent Claim
13 words
A method according to claim 1 further comprising the step of removing overload.
Claim 32
Dependent Claim
41 words
A method according to claim 30 wherein said step of removing overload comprises the steps of: defining column segments and rows of segments; determining new density distribution of said column segments; and modifying placements of the cells of said column segments.
Claim 33
Independent Claim
76 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 and segments of the IC surface; determine density of said pieces; resize said widths of said pieces depending upon said density of said pieces; and modify placement of the cells depending upon the sizes of said resized pieces.
Claim 34
Independent Claim
76 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 and segments of the IC surface; determine density of said pieces; resize said widths of said pieces depending upon said density of said pieces; and modify placement of the cells depending upon the sizes of said resized pieces.
Claim 35
Dependent Claim
24 words
An apparatus according to claim 32 wherein said memory further comprises instruction for said processor to smooth columns of the pieces of the IC.
Claim 36
Dependent Claim
23 words
An apparatus according to claim 32 wherein said memory further comprises instruction for said processor to optimize density of column of the IC.
Claim 37
Dependent Claim
26 words
An apparatus according to claim 32 wherein said memory further comprises instruction for said processor to: read cell list and netlist; and write new cell placement.
Claim 38
Dependent Claim
93 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: defining pieces and segments of the IC surface, said each of said pieces having an original location and original width; determining density of said pieces; resizing said widths of said pieces depending upon said density of said pieces, said resizing step assigning a new location and a new width to each of said pieces; and modifying placement of the cells depending upon the new location and the new width of said resized pieces.
Claim 39
Dependent Claim
93 words
A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: defining pieces and segments of the IC surface, said each of said pieces having an original location and original width; determining density of said pieces; resizing said widths of said pieces depending upon said density of said pieces, said resizing step assigning a new location and a new width to each of said pieces; and modifying placement of the cells depending upon the new location and the new width of said resized pieces.
Claim 40
Dependent Claim
39 words
A storage medium according to claim 36 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)
US5210701A
Cited
US5311443A
Cited
US5568322A
Cited
US5615128A
Cited
US5491641A
Cited
US5636125A
Cited
US5495419A
Cited
US5682322A
Cited
US5742510A
Cited
US5745363A
Cited
US5568636A
Cited
US5638293A
Cited
US5578840A
Cited
US5822214A
Cited
US5661663A
Cited
US5712793A
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-02 | 2003-11-01 | 2004-05-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-02 | 2007-11-01 | 2008-05-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-02 | 2011-11-01 | 2012-05-02 | $7700.00 | Window Closed / Lapsed |