Patent US5416720A successfully refreshed from Google Patents.
US5416720A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for optimizing block shape in hierarchical IC design
Assignee: Panasonic Holdings Corp
•
Filing: 1994-07-08
•
Granted: 1995-05-16
•
Expires: 2014-07-08
Abstract
Abstract A whole process is divided into a rough floor plan and a detailed floor plan. In the rough floor plan, locations and shapes of blocks are roughly determined. In the detailed floor plan; an estimation of shapes of shape-variable blocks and sizes of wiring areas between blocks is simplified by listing all of slicing structures and optimizing block shapes for respective channel structures without greatly changing a block placement and pin locations. A combination of a hierarchical technique and a heuristic technique is used to allow block shapes to be optimized by selecting only suitable channel structures without listing all of an exponential number of the channel structures. In this way, the block shape optimization is simplified. The time spent in the simplified block shape optimization generally has a linear order with respect to the number of the blocks.
Inventors
- 👤 Masahiro Fukui
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 13:23
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
209 words
A computer implemented method of optimizing the shapes of blocks on an integrated circuit chip wherein blocks Ai (i=1,2, . . . ,k) are placed in an area A on the integrated circuit chip in a non-slicing configuration on the chip, at least some of the blocks having variable shapes, the method comprising the steps of: using computer means to: perform, with respect to at least one block having a variable shape, a step of varying the shape thereof by randomly performing one of the steps of (a) increasing a selected value for the width of a block Ai (i=1,2, . . . ,k), and (b) increasing a selected value for the height of the block; then, to evaluate one of (a) the area size and width of the area and (b) the area size and height of the area A after the performing step; to accept or reject the increase of (a) or (b) in accordance with the evaluation; to determine a relation between a shape of the area A and shapes of the blocks Ai (i=1,2, . . . ,k) in the area A on the basis of the previously mentioned steps; and to determine a combination of optimal block shapes by use of the shape relation.
Claim 2
Dependent Claim
209 words
A computer implemented method of optimizing the shapes of blocks on an integrated circuit chip wherein blocks Ai (i=1,2, . . . ,k) are placed in an area A on the integrated circuit chip in a non-slicing configuration on the chip, at least some of the blocks having variable shapes, the method comprising the steps of: using computer means to: perform, with respect to at least one block having a variable shape, a step of varying the shape thereof by randomly performing one of the steps of (a) increasing a selected value for the width of a block Ai (i=1,2, . . . ,k), and (b) increasing a selected value for the height of the block; then, to evaluate one of (a) the area size and width of the area and (b) the area size and height of the area A after the performing step; to accept or reject the increase of (a) or (b) in accordance with the evaluation; to determine a relation between a shape of the area A and shapes of the blocks Ai (i=1,2, . . . ,k) in the area A on the basis of the previously mentioned steps; and to determine a combination of optimal block shapes by use of the shape relation.
Claim 3
Dependent Claim
103 words
A computer implemented method of optimizing shapes of blocks including standard cells in a block placement of a slicing channel structure on a semiconductor chip, at least some of the blocks having variable shapes, comprising the steps of using a computer means for: preliminarily positioning unit size representations of the blocks; estimating final shapes of the blocks; listing a plurality of different slicing channel structures, less than all possible slicing channel structures, in accordance with the estimated final shapes of the blocks; providing optimal block shapes for each listed structure; and selecting an optimal configuration of blocks for placement on the semiconductor chip.
Claim 4
Dependent Claim
103 words
A computer implemented method of optimizing shapes of blocks including standard cells in a block placement of a slicing channel structure on a semiconductor chip, at least some of the blocks having variable shapes, comprising the steps of using a computer means for: preliminarily positioning unit size representations of the blocks; estimating final shapes of the blocks; listing a plurality of different slicing channel structures, less than all possible slicing channel structures, in accordance with the estimated final shapes of the blocks; providing optimal block shapes for each listed structure; and selecting an optimal configuration of blocks for placement on the semiconductor chip.
Claim 5
Dependent Claim
41 words
The method of claim 2 wherein said step of providing optimal block shapes comprises incrementally varying a shape of at least one variable shape block by incrementing a length dimension of one side thereof thereby providing a proposed block shape therefor.
Claim 6
Dependent Claim
44 words
The method of claim 3, wherein said step of incrementing a length dimension of one side of said variable shape block comprises changing said length dimension of said one side in accordance with a number of rows of standard cells included in the block.
Claim 7
Dependent Claim
69 words
The method of claim 3, wherein said step of incrementing a length dimension of one side of said variable shape block comprises changing said length dimension of said one side in accordance with at least one of a plurality of characteristics of standard cells included in the block, including: a height of a standard cell, a sum of cell widths, and a number of standard cells in the block.
Claim 8
Dependent Claim
70 words
The method of claim 3, wherein said step of incrementing a length dimension of one side comprises incrementally varying either a width or a height dimension of said at least one variable block, comparing a resulting aspect ratio of said at least one variable block with a predetermined upper limit for acceptable aspect ratio, and rejecting the proposed block shape if the resulting aspect ratio exceeds said predetermined upper limit.
Claim 9
Dependent Claim
44 words
The method of claim 6, wherein said step of incrementing a length dimension further comprises varying the other of said width or height dimension of said at least one variable block to maintain an area of said at least one variable block substantially constant.
Claim 10
Dependent Claim
49 words
The method of claim 3, wherein said step of incrementally varying a shape of at least one variable shape block comprises changing a length dimension of a second side of said at least one variable block to maintain an area of said at least one variable block substantially constant.
Claim 11
Dependent Claim
107 words
The method of claim 2, wherein said step of estimating final shapes of the blocks comprises, for at least one block having a variable shape: selecting a number, R, of rows of standard cells for inclusion in said at least one block; defining parameters "a", "b", "c", and "d"; and defining a height dimension Y and a width dimension X of said at least one variable shape block; varying an estimated shape of said at least one variable shape block by setting said height dimension Y and said width dimension X of said at least one variable shape block in accordance with a relation "Y=a*R+b" and "X=c/R+d".
Claim 12
Dependent Claim
133 words
The method of claim 2, wherein said step of estimating final shapes of the blocks comprises: selecting a number, R, of rows of standard cells for inclusion in a block; defining parameters "a", "b", "c", and "d"; and defining a height dimension Y and a width dimension X of said block; establishing an estimated shape of said block by setting said height dimension Y and said width dimension X thereof in accordance with a relation "Y=a*R+b" and "X=c/R+d"; actually placing standard cells on the chip and wiring the cells in R rows in accordance with said relation; and determining values of the parameters "a", "b", "c", and "d" in accordance with the height and width of blocks obtained as a result of the actual placement and wiring of the blocks on the chip.
Claim 13
Dependent Claim
37 words
The method of claim 2 wherein said step of listing of a plurality of different slicing channel structures comprises identifying a minimal number of slicing channel structures for non-overlapping placement of blocks having the estimated final shapes.
Claim 14
Dependent Claim
44 words
The method of claim 11 wherein said step of providing optimal block shapes comprises incrementally varying a shape of at least one variable shape block by incrementing one of a length dimension and a width dimension thereof thereby providing a proposed block shape therefor.
Claim 15
Dependent Claim
37 words
The method of claim 12, wherein said step of incrementing one of a length dimension and a width dimension comprises changing the dimension in accordance with a number of rows of standard cells included in the block.
Claim 16
Dependent Claim
62 words
The method of claim 12, wherein said step of incrementing one of a length dimension and a width dimension comprises changing the dimension in accordance with at least one of a plurality of characteristics of standard cells included in the block, including: a height of a standard cell, a sum of cell widths, and a number of standard cells in the block.
Claim 17
Dependent Claim
47 words
The method of claim 12, wherein said step of providing optimal block shapes further comprises changing the other of a said length dimension and said width dimension of said at least one variable block to maintain an area of said at least one variable block substantially constant.
Claim 18
Dependent Claim
52 words
The method of claim 12, wherein said step of providing optimal block shapes further comprises comparing a resulting aspect ratio of said at least one variable block with a predetermined upper limit for acceptable aspect ratio, and rejecting the proposed block shape if the resulting aspect ratio exceeds said predetermined upper limit.
Claim 19
Dependent Claim
149 words
A computer implemented method of optimizing shapes of blocks including standard cells in a block placement of a slicing channel structure on a semiconductor chip, at least some of the blocks having variable shapes, comprising the steps of: preliminarily positioning unit size blocks; and providing optimal block shapes for said unit size blocks to minimize a resultant chip size, wherein said step of providing optimal block shapes comprises eliminating dead space on the chip by varying a shape of at least one block Ai (i=1,2, . . . ,k) having a variable shape, by randomly performing one of the steps of (a) increasing a selected value for a width of said at least one block, and (b) increasing a selected value for a height of said at least one block, thereby repeatedly changing an aspect ratio of said at least one block to eliminate dead space on the chip.
Claim 20
Dependent Claim
149 words
A computer implemented method of optimizing shapes of blocks including standard cells in a block placement of a slicing channel structure on a semiconductor chip, at least some of the blocks having variable shapes, comprising the steps of: preliminarily positioning unit size blocks; and providing optimal block shapes for said unit size blocks to minimize a resultant chip size, wherein said step of providing optimal block shapes comprises eliminating dead space on the chip by varying a shape of at least one block Ai (i=1,2, . . . ,k) having a variable shape, by randomly performing one of the steps of (a) increasing a selected value for a width of said at least one block, and (b) increasing a selected value for a height of said at least one block, thereby repeatedly changing an aspect ratio of said at least one block to eliminate dead space on the chip.
Claim 21
Dependent Claim
99 words
A method in accordance with claim 17 wherein said step of providing optimal block shapes further comprises providing optimal placement of said blocks by moving said unit size blocks in horizontal and vertical directions to establish different location combinations thereof; for each of the different location combinations, optimizing the sizes and shapes of the unit size blocks to minimize chip area to provide a proposed final placement; from the proposed final placements including optimized sizes and shapes for each of the different location combinations, selecting as a final placement the proposed final placement having the smallest total chip area.
Claim 22
Dependent Claim
32 words
A method in accordance with claim 18, comprising the further step of depositing on the chip the blocks with the optimized sizes and shapes at the locations selected in the selecting step.
Claim 23
Dependent Claim
24 words
The method of claim 18 wherein said step of optimizing includes rotating one of the blocks having an optimized size and shape by 90°.
Claim 24
Dependent Claim
87 words
The method of claim 18, wherein said step of providing optimal block shapes further comprises changing the other of said length dimension and said width dimension of said at least one block to maintain an area of said at least one block substantially constant by, upon randomly performing said one of the steps (a) and (b), correspondingly performing one of the steps of (a1) decreasing a selected value for a height of the block and (b1) decreasing a selected value for a width of the block, respectively.
Claim 25
Dependent Claim
29 words
The method of claim 18 wherein said step of optimizing includes moving one of the blocks having an optimized size in at least one of horizontal and vertical directions.
References Cited (Backward Citations)
US3654615A
Cited
US4495559A
Cited
US4630219A
Cited
US4686629A
Cited
US4890238A
Cited
US4815003A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-15 | 1998-11-14 | 1999-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-15 | 2002-11-14 | 2003-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-15 | 2006-11-14 | 2007-05-16 | $7700.00 | Window Closed / Lapsed |