US6030110A — Advanced modular cell placement system with media…

Claim 1

Independent Claim 179 words

A method for reallocating cells assigned to a region of the surface of an integrated circuit device, said method comprising the steps of: a. dividing said region into a first subregion and a second subregion with a dividing line; b. with respect to cells located within said region, determining a desired allocation of cells between said first subregion and said second subregion; c. locating a cut line across said region such that said cut line cuts said region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion; d. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line; e. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and f. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 2

Independent Claim 179 words

A method for reallocating cells assigned to a region of the surface of an integrated circuit device, said method comprising the steps of: a. dividing said region into a first subregion and a second subregion with a dividing line; b. with respect to cells located within said region, determining a desired allocation of cells between said first subregion and said second subregion; c. locating a cut line across said region such that said cut line cuts said region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion; d. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line; e. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and f. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 3

Dependent Claim 40 words

The method of claim 1, wherein the allocation of the cells between said first part and said second part in step c matches said desired allocation of cells between said first subregion and said second subregion determined in step b.

Claim 4

Dependent Claim 34 words

The method of claim 1, wherein said region is rectangular and both the cut line and the dividing line are substantially parallel to each other and to two opposing sides of said rectangular region.

Claim 5

Dependent Claim 19 words

The method of claim 3, wherein the area of each subregion is half of the area of the region.

Claim 6

Dependent Claim 23 words

The method of claim 2, wherein said desired allocation of cells between said subregions is a function of the capacities of said subregions.

Claim 7

Dependent Claim 75 words

The method of claim 5, wherein (1) said first subregion has a first capacity and said second subregion has a second capacity, (2) each cell has an associated cell height, and (3) the desired allocation of cells between said subregions is such that the sum of the cell heights in the first subregion divided by the first capacity substantially equals the sum of the cell heights in the second region divided by the second capacity.

Claim 8

Dependent Claim 69 words

The method of claim 5, wherein (1) said first subregion has a first capacity and said second subregion has a second capacity, and (2) the desired allocation of cells between said subregions is such that the sum of the number of cells in the first subregion divided by the first capacity substantially equals the sum of the number of cells in the second region divided by the second capacity.

Claim 9

Dependent Claim 189 words

A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: a. assigning cells to a region of the surface of an integrated circuit device; b. dividing said region into a first subregion and a second subregion with a dividing line; c. with respect to cells located within said region, determining desired allocation of cells between said first subregion and said second subregion; d. locating a cut line across said region such that said cut line cuts said region in a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion; e. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line; f. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and g. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 10

Dependent Claim 189 words

A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: a. assigning cells to a region of the surface of an integrated circuit device; b. dividing said region into a first subregion and a second subregion with a dividing line; c. with respect to cells located within said region, determining desired allocation of cells between said first subregion and said second subregion; d. locating a cut line across said region such that said cut line cuts said region in a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between said first subregion and said second subregion; e. determining an offset representing the distance between a first point on the cut line and a second point on the dividing line; f. shifting cells assigned to said region said offset in the direction from the cut line toward the dividing line; and g. reassigning any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 11

Dependent Claim 24 words

A storage medium according to claim 8 wherein said storage medium is selected from a group consisting of floppy diskette, hard drive, and CD-ROM.

Claim 12

Independent Claim 283 words

A method for optimizing the placement of cells on a portion of the surface of an integrated circuit device, said method comprising the steps of: a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 13

Independent Claim 283 words

A method for optimizing the placement of cells on a portion of the surface of an integrated circuit device, said method comprising the steps of: a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 14

Dependent Claim 49 words

The method of claim 10, wherein, for each region within said first row of regions, the allocation of the cells between said first part and said second part in substep ii matches the desired allocation of cells between the region's first subregion and second subregion determined in substep i.

Claim 15

Dependent Claim 34 words

The method of claim 10, wherein, for each region within said first row of regions, the region's cut line and said first region dividing line of said first row of regions are substantially parallel.

Claim 16

Dependent Claim 49 words

The method of claim 12, wherein, for each region within said first row of regions, the shortest distance between the first point on the region's cut line and the region's second point on the first region dividing line is a line substantially perpendicular to the first region dividing line.

Claim 17

Dependent Claim 28 words

The method of claim 10, wherein, for each region in said first row of regions, the area of each subregion is half of the area of the region.

Claim 18

Dependent Claim 32 words

The method of claim 11, wherein, for each region within said first row of regions, said desired allocation of cells between said subregions is a function of the capacities of said subregions.

Claim 19

Dependent Claim 86 words

The method of claim 15, wherein, for each region within said first row of regions, (1) said first subregion has a first capacity and said second subregion has a second capacity, (2) each cell has an associated cell height, and (3) the desired allocation of cells between said subregions is such that the sum of the cell heights in the first subregion divided by the first capacity is substantially equal to the sum of the cell heights in the second region divided by the second capacity.

Claim 20

Dependent Claim 78 words

The method of claim 15, wherein, for each region within said first row of regions, (1) said first subregion has a first capacity and said second subregion has a second capacity, and (2) the desired allocation of cells between said subregions is such that the sum of the number of cells in the first subregion divided by the first capacity substantially equals the sum of the number of cells in the second region divided by the second capacity.

Claim 21

Dependent Claim 37 words

The method of claim 10, wherein steps (c) and (d) are repeated for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

Claim 22

Dependent Claim 145 words

The method of claim 18, wherein the following additional steps are taken: e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and f. for each subregion in said first row of subregions, performing the following substeps: i. locating a cut line across the subregion; ii. determining an offset representing the distance between a first point on the subregion's cut line and a second point on the first subregion dividing line, said second point being within the subregion; iii. shifting cells assigned to said subregion said distance; and iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.

Claim 23

Dependent Claim 37 words

The method of claim 19, wherein steps (e) and (f) are repeated for the rows of subregions which are parallel to said first row of subregions with each parallel row of subregions having its own dividing line.

Claim 24

Dependent Claim 15 words

The method of claim 10, wherein the number of regions in said grid is 4.

Claim 25

Dependent Claim 15 words

The method of claim 10, wherein the number of regions in said grid is 8.

Claim 26

Dependent Claim 15 words

The method of claim 10, wherein the number of regions in said grid is 16.

Claim 27

Dependent Claim 286 words

A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: a. dividing a portion of the surface of a integrated circuit device into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 28

Dependent Claim 286 words

A machine-readable storage medium containing instructions for a processor, said instructions being the steps for the processor, said steps comprising: a. dividing a portion of the surface of a integrated circuit device into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 29

Dependent Claim 43 words

The machine-readable storage medium of claim 24, wherein the instructions thereon further comprise repeating steps (c) and (d) for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

Claim 30

Dependent Claim 152 words

The machine-readable storage medium of claim 25, wherein the instructions contained therein further comprise taking the following additional steps: e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and f. for each subregion in said first row of subregions, performing the following substeps: i. locating a cut line across the subregion; ii. determining an offset representing the distance between a first point on the subregion's cut line and a second point on the first subregion dividing line, said second point being within the subregion; iii. shifting cells assigned to said subregion said distance; and iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.

Claim 31

Dependent Claim 24 words

A storage medium according to claim 24 wherein said storage medium is selected from a group consisting of floppy diskette, hard drive, and CD-ROM.

Claim 32

Dependent Claim 286 words

An integrated circuit device having cells placed on a portion of its surface, wherein said cells are allocated on said portion with a method comprising the following steps: a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 33

Dependent Claim 286 words

An integrated circuit device having cells placed on a portion of its surface, wherein said cells are allocated on said portion with a method comprising the following steps: a. dividing said portion into rectangular regions such that the regions are arranged in a rectangular grid with horizontal rows of regions and vertical rows of regions such that each region (a) shares an edge with each adjacent region within its horizontal row of regions and (b) shares an edge with each adjacent region within its vertical row of regions; b. assigning to each of the regions a plurality of cells; c. dividing a first row of regions with a first region dividing line such that each region in said first row of regions is divided into a first subregion and a second subregion; and d. for each region in said first row of regions, performing the following substeps: i. with respect to cells located within the region, determining a desired allocation of cells between the region's first subregion and second subregion; ii. locating a cut line across the region such that said cut line cuts the region into a first part and a second part and an allocation of cells between said first part and said second part substantially matches said desired allocation of cells between the region's first subregion and second subregion; iii. determining an offset representing the distance between a first point on the region's cut line and a second point on said first region dividing line, said second point being within the region; iv. shifting cells assigned to said region said offset; and v. relocating any cells located outside the region as a result of said shifting step to an edge of said region.

Claim 34

Dependent Claim 42 words

The integrated circuit device of claim 28 wherein said method further comprises repeating steps (c) and (d) for the rows of regions which are parallel to said first row of regions with each parallel row of regions having its own dividing line.

Claim 35

Dependent Claim 149 words

The integrated circuit device of claim 29 wherein said method further comprises the following additional steps: e. dividing a first row of subregions, said first row of subregions being perpendicular to said first row of regions, with a first subregion dividing line such that each subregion in said first row of subregions is divided into a first sub-subregion and a second sub-subregion; and f. for each subregion in said first row of subregions, performing the following substeps: i. locating a cut line across the subregion; ii. determining an offset representing the distance between a first point on the subregion's cut line and a second point on the first subregion dividing line, said second point being within the subregion; iii. shifting cells assigned to said subregion said distance; and iv. relocating any cells located outside the subregion as a result of said shifting step to an edge of said subregion.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-02-28	2003-08-30	2004-02-29	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-02-28	2007-08-30	2008-02-29	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-02-28	2011-08-30	2012-02-29	$7700.00	Window Closed / Lapsed

Advanced modular cell placement system with median control and increase in resolution

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag