Patent US3454397A successfully refreshed from Google Patents.
Patent FR714259A successfully refreshed from Google Patents.
Patent US3767271A successfully refreshed from Google Patents.
Patent US5757657A successfully refreshed from Google Patents.
US5757657A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive incremental placement of circuits on VLSI chip
Assignee: International Business Machines Corp
•
Filing: 1996-02-07
•
Granted: 1998-05-26
•
Expires: 2016-02-07
Abstract
Abstract A computer implemented method incrementally updates a design placement in a very large scale integrated (VLSI) chip. A data structure is generated which defines a chosen specification and initial placement of circuits is input to a computer aided design (CAD) system. The CAD system divides a design area into placement cells. Local constraint values and limits are computed and changes made in the design specification. Replacement regions are then identified, expanded, and replaced. Constraint values are recomputed and the steps of the method are repeated until no more changes are required.
Inventors
- 👤 David James Hathaway
- 👤 John Maxwell Cohn
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 19:59
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
179 words
A computer implemented method of incrementally placing circuits on a two dimensional design area comprising the steps of: a) inputting a specification of said circuits in a design and a connectivity for said circuits, and of said design area in which said circuits may be placed; b) performing an initial placement of said circuits in said design area; c) determining a set of placement cells into which said design area can be divided, and a set of cut line segments dividing adjacent pairs of these placement cells; d) determining a set of local constraints; e) accepting a list of at least one change in the design specification; f) determining new placements for each of the circuits directly affected by these accepted placement changes; g) identifying initial replacement regions for which said local constraints were violated; h) expanding said initial replacement regions according to a cost function until a stopping condition is met; i) replacing the circuits in each of the expanded replacement regions; and j) repeating steps e) through i) until no more changes in design specification are required.
Claim 2
Dependent Claim
179 words
A computer implemented method of incrementally placing circuits on a two dimensional design area comprising the steps of: a) inputting a specification of said circuits in a design and a connectivity for said circuits, and of said design area in which said circuits may be placed; b) performing an initial placement of said circuits in said design area; c) determining a set of placement cells into which said design area can be divided, and a set of cut line segments dividing adjacent pairs of these placement cells; d) determining a set of local constraints; e) accepting a list of at least one change in the design specification; f) determining new placements for each of the circuits directly affected by these accepted placement changes; g) identifying initial replacement regions for which said local constraints were violated; h) expanding said initial replacement regions according to a cost function until a stopping condition is met; i) replacing the circuits in each of the expanded replacement regions; and j) repeating steps e) through i) until no more changes in design specification are required.
Claim 3
Dependent Claim
30 words
The computer implemented method of claim 1, wherein the step of determining a set of local constraints comprises determining at least one constraint on each of the determined placement cells.
Claim 4
Dependent Claim
30 words
The computer implemented method of claim 1, wherein the step of determining a set of local constraints comprises determining at least one constraint on each of the determined cutline segments.
Claim 5
Dependent Claim
32 words
The computer implemented method of claim 2, wherein the placement cell constraint includes requiring the total area within the placement cell occupied by circuits to be between some minimum and maximum capacities.
Claim 6
Dependent Claim
30 words
The computer implemented method of claim 3, wherein the cut line segment constraint includes requiring the number of connections crossing each cut line segment to be less than some maximum.
Claim 7
Dependent Claim
52 words
The computer implemented method of claim 1, wherein said step of expansion generates a region which is a rectangle with an aspect ratio less than some maximum limit, or a partial rectangle in the event of an overlap with an inside corner of said design area, where said design area is nonrectangular.
Claim 8
Dependent Claim
50 words
The computer implemented method of claim 1, wherein said initial placement is done by a bisection method which determines a cut tree whose leaves are the placement cells, and in which the expansion step preferentially adds to a replacement region cells which complete a sub tree of this cut tree.
Claim 9
Dependent Claim
58 words
The computer implemented method of claim 4, wherein said stopping condition includes requiring that the sum of the areas occupied by the circuits in the replacement regions be between the sum of the minimum capacities of the placement cells in the replacement region and the sum of the maximum capacities of the placement cells in the replacement region.
Claim 10
Dependent Claim
62 words
The computer implemented method of claim 1, wherein said placement cells are determined by a rectangular grid, such that each placement cell has at most one placement cell immediately above it, at most one placement cell immediately below it, at most one placement cell immediately to the right of it, and at most one placement cell immediately to the left of it.
Claim 11
Dependent Claim
26 words
The computer implemented method of claim 1, wherein said expansion step preferentially expands a replacement region in such a way that the replacement regions are merged.
Claim 12
Dependent Claim
31 words
The computer implemented method of claim 2, wherein said cost function includes at least one term that is minimized by inclusion of placement cells that are closest to violating their constraints.
Claim 13
Dependent Claim
38 words
The computer implemented method of claim 3, wherein said cost function includes at least one term that is minimized by inclusion of placement cells on both sides of cut line segments that are closest to violating their constraints.
Claim 14
Dependent Claim
53 words
The computer implement method of claim 1, wherein the step of determining a set of local constraints comprises computing a set of local constraint values and the allowed limits on said local constraint values and the step of identifying initial replacement regions comprises determining whether said local constraint values exceed said allowed limits.
Claim 15
Dependent Claim
33 words
The computer implemented method of claim 13, wherein the step of determining new placements includes recomputing said local constraint values, and the step of replacing the circuits includes recomputing said local constraint values.
Claim 16
Dependent Claim
44 words
The computer implemented method of claim 13, wherein said expansion step preferentially expands a replacement region to keep the sum of said local constraint values for the replacement region as far as possible from the sum of said allowed limits for the replacement region.
Claim 17
Dependent Claim
55 words
A computer implemented method of modifying portion of an existing placement in response to changes in characteristics of the design which affect placement, including circuit selection and connectivity, and which includes a means to correct accumulated errors in global characteristics of the placement, including circuit density and wirability due to a series of placement changes.
Claim 18
Dependent Claim
55 words
A computer implemented method of modifying portion of an existing placement in response to changes in characteristics of the design which affect placement, including circuit selection and connectivity, and which includes a means to correct accumulated errors in global characteristics of the placement, including circuit density and wirability due to a series of placement changes.
Claim 19
Independent Claim
129 words
A method for designing a semiconductor chip, comprising the steps of: a) defining a global placement constraint that must not be violated; b) creating a netlist which identifies circuits and connections between the circuits to define a circuit network; c) assigning locations to the circuits in the circuit network onto a map of the semiconductor chip based upon the netlist; d) making local placement change to the circuit network; e) testing the semiconductor chip map to identify a global placement constraint violation; f) defining a solution region on the semiconductor chip map that contains the global constraint violation and an additional area sufficient to allow for a correction of the global constraint violation; and g) assigning new semiconductor chip map locations to the circuits located in the solution region.
Claim 20
Independent Claim
129 words
A method for designing a semiconductor chip, comprising the steps of: a) defining a global placement constraint that must not be violated; b) creating a netlist which identifies circuits and connections between the circuits to define a circuit network; c) assigning locations to the circuits in the circuit network onto a map of the semiconductor chip based upon the netlist; d) making local placement change to the circuit network; e) testing the semiconductor chip map to identify a global placement constraint violation; f) defining a solution region on the semiconductor chip map that contains the global constraint violation and an additional area sufficient to allow for a correction of the global constraint violation; and g) assigning new semiconductor chip map locations to the circuits located in the solution region.
Claim 21
Dependent Claim
124 words
A computer implemented method for incrementally updating the placement of circuits in a circuit network comprising the steps of; a) inputting a netlist describing the circuit network; b) placing all the circuits in said circuit network; c) accepting at least one local change to said circuit network placement, said change optionally to include changes to the circuits and connections of said circuit network; d) testing for global constraint violations on said circuit network placement which are now violated as a result of said local change in said circuit network placement; e) defining regions of said circuit network placement in which circuits need to be replaced in order to correct said identified global placement constraint violations; and f) replacing the circuits in said defining regions.
Claim 22
Dependent Claim
124 words
A computer implemented method for incrementally updating the placement of circuits in a circuit network comprising the steps of; a) inputting a netlist describing the circuit network; b) placing all the circuits in said circuit network; c) accepting at least one local change to said circuit network placement, said change optionally to include changes to the circuits and connections of said circuit network; d) testing for global constraint violations on said circuit network placement which are now violated as a result of said local change in said circuit network placement; e) defining regions of said circuit network placement in which circuits need to be replaced in order to correct said identified global placement constraint violations; and f) replacing the circuits in said defining regions.
Claim 23
Dependent Claim
78 words
A computer implemented semiconductor chip design method comprising the steps of: establishing a global constraint, wherein violation of said global constraint determines the need for replacing a portion of the chip; making a local change to the placement; determining whether said local change caused said global constraint to be violated; and if said global constraint is violated, identify a region of the chip whose replacement would cause said global constraint not to be violated and replace said region.
Claim 24
Dependent Claim
78 words
A computer implemented semiconductor chip design method comprising the steps of: establishing a global constraint, wherein violation of said global constraint determines the need for replacing a portion of the chip; making a local change to the placement; determining whether said local change caused said global constraint to be violated; and if said global constraint is violated, identify a region of the chip whose replacement would cause said global constraint not to be violated and replace said region.
References Cited (Backward Citations)
US4377849A
Cited
US4686629A
Cited
US5050091A
Cited
US4882690A
Cited
US4975854A
Cited
US5097422A
Cited
US4908772A
Cited
US4918614A
Cited
US5416720A
Cited
US5164907A
Cited
US5231590A
Cited
US5355322A
Cited
US5371684A
Cited
US5311443A
Cited
US5308798A
Cited
US5513119A
Cited
US5579237A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |