US5870312A — Advanced modular cell placement system with dispe…

Claim 1

Independent Claim 130 words

A method for levelizing the density of elements located in a plurality of regions on a surface having a core area, said regions having associated therewith a set of nodes identified by coordinates, comprising the steps of: (a) calculating region densities based on parameters of elements overlapping regions; (b) computing region areas; (c) determining total density for the surface; (d) figuring a density dispersion cost function based on total available core area of the surface and total density; (e) moving the coordinates of nodes to an updated nodal position based on local average density for all regions adjacent to said node; (f) computing a local cost function based on densities of regions adjacent said node and local average density such that the updated nodal position minimizes the local cost function.

Claim 2

Independent Claim 130 words

A method for levelizing the density of elements located in a plurality of regions on a surface having a core area, said regions having associated therewith a set of nodes identified by coordinates, comprising the steps of: (a) calculating region densities based on parameters of elements overlapping regions; (b) computing region areas; (c) determining total density for the surface; (d) figuring a density dispersion cost function based on total available core area of the surface and total density; (e) moving the coordinates of nodes to an updated nodal position based on local average density for all regions adjacent to said node; (f) computing a local cost function based on densities of regions adjacent said node and local average density such that the updated nodal position minimizes the local cost function.

Claim 3

Dependent Claim 20 words

The method of claim 1, wherein the updated nodal position minimizes the local cost function based on a greedy algorithm.

Claim 4

Dependent Claim 25 words

The method of claim 1, further comprising the steps of: (g) defining fixed nodes and movable nodes; and (h) evaluating and moving only movable nodes.

Claim 5

Dependent Claim 26 words

The method of claim 3, wherein a fixed node is one located coincident with a blockage and a movable node is not coincident with any blockages.

Claim 6

Dependent Claim 25 words

The method of claim 3, further comprising the step of sequentially repeating said method for all movable nodes until a predetermined stopping criteria is achieved.

Claim 7

Dependent Claim 20 words

The method of claim 5, further comprising the step of repeating all aforementioned steps for all subsequent levels of hierarchy.

Claim 8

Dependent Claim 36 words

The method of claim 1, wherein for regions located on a border of said surface, a plurality of fictive regions are created having zero density and zero capacity to be used for nodes on said border.

Claim 9

Dependent Claim 20 words

The method of claim 1, wherein said total density represents the sum of densities for all regions on the surface.

Claim 10

Dependent Claim 35 words

The method of claim 1, wherein the density dispersion cost function is a function of total available core area, density of all regions on the surface, and area of all available regions on the surface.

Claim 11

Independent Claim 115 words

A system for dispersing the density of elements located on a surface divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising: (a) means for computing an average local density for regions adjacent to each node; (b) means for deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the deformed regions bordering the nodes that have been relocated; and (c) means for figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 12

Independent Claim 115 words

A system for dispersing the density of elements located on a surface divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising: (a) means for computing an average local density for regions adjacent to each node; (b) means for deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the deformed regions bordering the nodes that have been relocated; and (c) means for figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 13

Dependent Claim 18 words

The method of claim 10, wherein the relocated nodes minimize the cost function based on a greedy algorithm.

Claim 14

Dependent Claim 24 words

The system of claim 10, wherein said nodes evaluated and moved in said computing and deforming steps do not coincide with relatively immovable blockages.

Claim 15

Dependent Claim 19 words

The system of claim 10, further comprising means for calculating region densities based on parameters of elements overlapping regions.

Claim 16

Dependent Claim 31 words

The system of claim 10, further comprising means for defining those elements located in the deformed regions to correspond to regions bounded by the same nodes before said nodes were repositioned.

Claim 17

Dependent Claim 23 words

The system of claim 14, further comprising means for repeating the aforementioned system stages for all subsequent levels of hierarchy on the surface.

Claim 18

Dependent Claim 24 words

The system of claim 10, wherein the nodes are divided into fixed nodes and movable nodes and only movable nodes are evaluated and repositioned.

Claim 19

Dependent Claim 26 words

The system of claim 16, wherein a fixed node is one located coincident with a blockage and a movable node is not coincident with any blockages.

Claim 20

Dependent Claim 20 words

The system of claim 10, wherein said total density represents the sum of densities for all regions on the surface.

Claim 21

Dependent Claim 35 words

The system of claim 10, wherein the density dispersion cost function is a function of total available core area, density of all regions on the surface, and area of all available regions on the surface.

Claim 22

Dependent Claim 36 words

The system of claim 10, wherein for regions located on a border of said surface, a plurality of fictive regions are created having zero density and zero capacity to be used for nodes on said border.

Claim 23

Dependent Claim 125 words

A computer storage device having located thereon a computer program for optimizing the density of cells located on a surface of a semiconductor chip divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising the following steps: (a) computing an average local density for regions adjacent to nodes; and (b) deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the new deformed regions bordering the nodes that have been relocated; and (c) figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 24

Dependent Claim 125 words

A computer storage device having located thereon a computer program for optimizing the density of cells located on a surface of a semiconductor chip divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising the following steps: (a) computing an average local density for regions adjacent to nodes; and (b) deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the new deformed regions bordering the nodes that have been relocated; and (c) figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 25

Independent Claim 114 words

A method for optimizing the density of cells located on a surface of a semiconductor chip divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising: (a) computing an average local cell density for regions adjacent to each node; (b) deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the deformed regions bordering the nodes that have been relocated; and (c) figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 26

Independent Claim 114 words

A method for optimizing the density of cells located on a surface of a semiconductor chip divided into a plurality of rectangular regions and having a core area, wherein the corners of said regions define nodes, comprising: (a) computing an average local cell density for regions adjacent to each node; (b) deforming said regions so as to form deformed regions by relocating nodes to positions that minimize a cost function associated with the densities of the deformed regions bordering the nodes that have been relocated; and (c) figuring a density dispersion cost function based on the core area of the surface and a density of each rectangular region in said plurality of rectangular regions.

Claim 27

Dependent Claim 36 words

The method of claim 22, wherein for regions located on a border of said surface, a plurality of fictive regions are created having zero density and zero capacity to be used for nodes on said border.

Claim 28

Dependent Claim 35 words

The method of claim 22, wherein the density dispersion cost function is a function of total available core area, density of all regions on the surface, and area of all available regions on the surface.

Claim 29

Dependent Claim 24 words

The method of claim 22, wherein said nodes evaluated and moved in said computing and deforming steps do not coincide with relatively immovable blockages.

Claim 30

Dependent Claim 20 words

The method of claim 22, wherein step (b) further comprises calculating region densities based on parameters of cells overlapping regions.

Claim 31

Dependent Claim 20 words

The method of claim 22, wherein said total density represents the sum of densities for all regions on the surface.

Claim 32

Dependent Claim 18 words

The method of claim 22, wherein the relocated nodes minimize the cost function based on a greedy algorithm.

Claim 33

Dependent Claim 24 words

The method of claim 22, wherein the nodes are divided into fixed nodes and movable nodes and only movable nodes are evaluated and repositioned.

Claim 34

Dependent Claim 26 words

The method of claim 29, wherein a fixed node is one located coincident with a blockage and a movable node is not coincident with any blockages.

Claim 35

Dependent Claim 25 words

The method of claim 29, further comprising the step of sequentially repeating said method for all movable nodes until a predetermined stopping criteria is achieved.

Claim 36

Dependent Claim 33 words

The method of claim 31, further comprising the step of: (d) defining those elements located in the deformed regions to correspond to regions bounded by the same nodes before said nodes were repositioned.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-02-08	2002-08-10	2003-02-09	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-02-08	2006-08-10	2007-02-09	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-02-08	2010-08-10	2011-02-09	$7700.00	Window Closed / Lapsed

Advanced modular cell placement system with dispersion-driven levelizing system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag