Advanced modular cell placement system with neighborhood system driven optimization

Claim 3

The method of claim 1, wherein the cells of said cluster are indexed such that each such cell receives an index value and each cell's individual-cluster weight is a function of said cell's index value.

Claim 4

The method of claim 2, wherein the cluster has a center cell and each cell in said cluster is indexed as a function of a predetermined relationship between the cell and the center cell.

Claim 5

The method of claim 3, wherein said relationship between the cell and the center cell is the proximity of the two cells in said netlist.

Claim 6

The method of claim 2, wherein no cell in said cluster has an individual-cluster weight identical to the individual-cluster weight of another cell in said cluster.

Claim 7

The method of claim 1, wherein a cell's individual-cluster weight is not a function of the cell's size.

Claim 8

The method of claim 1, wherein said cluster comprises a center cell and each cell which shares at least one net with said center cell.

Claim 9

The method of claim 7, wherein said cluster further comprises at least one cell which does not share a net with said center cell.

Claim 12

The method of claim 9, wherein said first portion weight is a function of the sum of the individual-cluster weights of the cells of said cluster assigned to said first portion.

Claim 13

The method of claim 9, wherein (i) said plurality of portions further comprises a second portion which does not comprise the region and does not overlap said first portion, and (ii) the portion to which the first cell is moved is further a function of a second cluster affinity, said second cluster affinity being determined by a method comprising the following steps: (a) calculating a second portion weight, wherein said second portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said second portion; and (b) calculating a second cluster affinity, wherein said second cluster affinity is a function of the second portion weight.

Claim 14

The method of claim 11, wherein said second portion weight is a function of the sum of the individual-cluster weights of the cells assigned to said second portion.

Claim 15

The method of claim 9, wherein the greater a cell's index value, the less the cell's individual-cluster weight.

Claim 16

The method of claim 13, wherein a cell's individual-cluster weight is a function of the number of cells in the cluster less the index value.

Claim 17

The method of claim 14, wherein a cell's individual-cluster weight is proportional to the following: The number of cells in the cell's cluster less the following value: The index value plus a constant.

Claim 18

The method of claim 15, wherein said constant is zero.

Claim 19

The method of claim 9, wherein the number of cells in the cluster is between 15 and 30.

Claim 20

The method of claim 11, wherein: (a) A region portion weight is calculated wherein said region portion weight is a function of the sum of the individual-cluster weights of the cells assigned to the region portion; and (b) the first cluster affinity is a function of said region portion weight and a function of the second portion weight.

Claim 21

The method of claim 18, wherein the first cluster affinity is a function of the following: The first portion weight less the following value: The second portion weight plus the region portion weight.

Claim 22

The method of claim 19, wherein said region is rectangular.

Claim 23

The method of claim 20, wherein said region is one of a plurality of rectangular regions of said surface such that (a) said plurality of rectangular regions is arranged in a rectangular grid with horizontal rows of rectangular regions and vertical rows of rectangular regions, (b) each region shares an edge with each adjacent region within its horizontal row of regions, and (c) each region shares an edge with each adjacent region within its vertical row of regions.

Claim 24

The method of claim 21, wherein the region portion comprises a row of rectangular regions.

Claim 25

The method of claim 22, wherein the region portion is rectangular.

Claim 26

The system of claim 23, wherein (a) said first portion comprises a first row of rectangular regions parallel to the row comprising the region portion and said second portion comprises a second row of rectangular regions parallel to the row comprising the region portion and (b) said first portion is on one side of the region portion and said second portion is on the opposite side of the region portion.

Claim 27

The method of claim 9, wherein said cluster has a center cell and the cells of said cluster are ordered as a function of the cells' distance from the center cell within the netlist.

Claim 28

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) An encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for forming a cluster of cells from said netlist, said cluster not comprising all cells from the netlist; (c) an encoded instruction on said storage medium for assigning each cell within said cluster an individual-cluster weight; (d) an encoded instruction on said storage medium for dividing an abstract of the surface of the integrated circuit device into a plurality of regions, said plurality of regions comprising a first region and a second region; (e) an encoded instruction on said storage medium for locating cells on the surface of said integrated circuit device, such that the cells placed comprise each of the cells of the cluster as well as other cells; (f) an encoded instruction on said storage medium for calculating a first sum of individual-cluster weights for all cells of said cluster located within said first region; (g) an encoded instruction on said storage medium for calculating a first cluster affinity based on said first sum of individual-cluster weights; (h) an encoded instruction on said storage medium for calculating a second sum of individual-cluster weights for all cells of said cluster located within a second region; (i) an encoded instruction on said storage medium for calculating a second cluster affinity based on said second sum of individual-cluster weights; and (l) an encoded instruction on said storage medium for determining whether to relocate a cell from said cluster from one region to another as a function of both said first cluster affinity and of said second cluster affinity and assigning said cell in accordance with said determination.

Claim 29

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) An encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for forming a cluster of cells from said netlist, said cluster not comprising all cells from the netlist; (c) an encoded instruction on said storage medium for assigning each cell within said cluster an individual-cluster weight; (d) an encoded instruction on said storage medium for dividing an abstract of the surface of the integrated circuit device into a plurality of regions, said plurality of regions comprising a first region and a second region; (e) an encoded instruction on said storage medium for locating cells on the surface of said integrated circuit device, such that the cells placed comprise each of the cells of the cluster as well as other cells; (f) an encoded instruction on said storage medium for calculating a first sum of individual-cluster weights for all cells of said cluster located within said first region; (g) an encoded instruction on said storage medium for calculating a first cluster affinity based on said first sum of individual-cluster weights; (h) an encoded instruction on said storage medium for calculating a second sum of individual-cluster weights for all cells of said cluster located within a second region; (i) an encoded instruction on said storage medium for calculating a second cluster affinity based on said second sum of individual-cluster weights; and (l) an encoded instruction on said storage medium for determining whether to relocate a cell from said cluster from one region to another as a function of both said first cluster affinity and of said second cluster affinity and assigning said cell in accordance with said determination.

Claim 30

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) an encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for organizing a plurality of interrelated cells from said netlist into a cluster; (c) an encoded instruction on said storage medium for ordering the cells of said cluster, wherein the resulting order is not necessarily in order of cell size; (d) an encoded instruction on said storage medium for indexing said cells in accordance with said ordering such that each cell is assigned its own index value; (e) an encoded instruction on said storage medium for assigning each cell of said cells an individual-cluster weight, wherein a cell's individual-cluster weight is a function of the cell's index value; (f) an encoded instruction on said storage medium for locating said cluster on an abstract of the surface of the integrated circuit device such that at least one of the cells is assigned to said region; (g) an encoded instruction on said storage medium for selecting a first cell from said cluster which is assigned to said region; (h) an encoded instruction on said storage medium for dividing the surface abstract into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, and a first portion which does not comprise the region; (i) an encoded instruction on said storage medium for calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (j) an encoded instruction on said storage medium for calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight; and (k) an encoded instruction on said storage medium for moving the first cell from the region portion to another portion, wherein the portion to which the first cell is moved is a function of said first cluster affinity.

Claim 31

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) an encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for organizing a plurality of interrelated cells from said netlist into a cluster; (c) an encoded instruction on said storage medium for ordering the cells of said cluster, wherein the resulting order is not necessarily in order of cell size; (d) an encoded instruction on said storage medium for indexing said cells in accordance with said ordering such that each cell is assigned its own index value; (e) an encoded instruction on said storage medium for assigning each cell of said cells an individual-cluster weight, wherein a cell's individual-cluster weight is a function of the cell's index value; (f) an encoded instruction on said storage medium for locating said cluster on an abstract of the surface of the integrated circuit device such that at least one of the cells is assigned to said region; (g) an encoded instruction on said storage medium for selecting a first cell from said cluster which is assigned to said region; (h) an encoded instruction on said storage medium for dividing the surface abstract into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, and a first portion which does not comprise the region; (i) an encoded instruction on said storage medium for calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (j) an encoded instruction on said storage medium for calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight; and (k) an encoded instruction on said storage medium for moving the first cell from the region portion to another portion, wherein the portion to which the first cell is moved is a function of said first cluster affinity.

Claim 32

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) forming a cluster of cells from said netlist, said cluster not comprising all cells from the netlist; (c) for each cell within said cluster, assigning the cell an individual-cluster weight; (d) dividing an abstract of the surface of the integrated circuit device into a plurality of regions, said plurality of regions comprising a first region and a second region; (e) locating cells on the abstract of the surface of said integrated circuit device, such that the cells so located comprise each of the cells of the cluster as well as other cells; (f) calculating a first sum of individual-cluster weights for all cells of said cluster located within said first region; (g) calculating a first cluster affinity based on said first sum of individual-cluster weights; (h) calculating a second sum of individual-cluster weights for all cells of said cluster located within a second region; (i) calculating a second cluster affinity based on said second sum of individual-cluster weights; and (j) determining whether to relocate a cell from said cluster from one region to another as a function of both said first cluster affinity and of said second cluster affinity, reassigning said cell in accordance with said determination, and placing said cell on at least one integrated circuit device as a function of said reassignment.

Claim 33

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) forming a cluster of cells from said netlist, said cluster not comprising all cells from the netlist; (c) for each cell within said cluster, assigning the cell an individual-cluster weight; (d) dividing an abstract of the surface of the integrated circuit device into a plurality of regions, said plurality of regions comprising a first region and a second region; (e) locating cells on the abstract of the surface of said integrated circuit device, such that the cells so located comprise each of the cells of the cluster as well as other cells; (f) calculating a first sum of individual-cluster weights for all cells of said cluster located within said first region; (g) calculating a first cluster affinity based on said first sum of individual-cluster weights; (h) calculating a second sum of individual-cluster weights for all cells of said cluster located within a second region; (i) calculating a second cluster affinity based on said second sum of individual-cluster weights; and (j) determining whether to relocate a cell from said cluster from one region to another as a function of both said first cluster affinity and of said second cluster affinity, reassigning said cell in accordance with said determination, and placing said cell on at least one integrated circuit device as a function of said reassignment.

Claim 34

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) organizing a plurality of interrelated cells from said netlist into a cluster; (c) ordering the cells of said cluster, wherein the resulting order is not necessarily in order of cell size; (d) indexing said cells in accordance with said ordering such that each cell is assigned its own index value; (e) for each cell of said cells, assigning the cell an individual-cluster weight, wherein said individual-cluster weight is a function of the cell's index value; (f) locating said cluster on the abstract of a surface of the integrated circuit device such that at least one of the cells is assigned to said region; (g) selecting a first cell from said cluster which is assigned to said region; (h) dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, and a first portion which does not comprise the region; (i) calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (j) calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight; (k) reassigning the first cell from the region portion to another portion, wherein the portion to which the first cell is reassigned is a function of said first cluster affinity; and (l) placing said first cell on at least one integrated circuit device as a function of said reassignment.

Claim 35

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) organizing a plurality of interrelated cells from said netlist into a cluster; (c) ordering the cells of said cluster, wherein the resulting order is not necessarily in order of cell size; (d) indexing said cells in accordance with said ordering such that each cell is assigned its own index value; (e) for each cell of said cells, assigning the cell an individual-cluster weight, wherein said individual-cluster weight is a function of the cell's index value; (f) locating said cluster on the abstract of a surface of the integrated circuit device such that at least one of the cells is assigned to said region; (g) selecting a first cell from said cluster which is assigned to said region; (h) dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, and a first portion which does not comprise the region; (i) calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (j) calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight; (k) reassigning the first cell from the region portion to another portion, wherein the portion to which the first cell is reassigned is a function of said first cluster affinity; and (l) placing said first cell on at least one integrated circuit device as a function of said reassignment.

Claim 38

The method of claim 30, wherein said first portion weight is a function of the sum of the individual-cluster weights of the cells of said cluster assigned to said first portion.

Claim 39

The method of claim 31, wherein said second portion weight is a function of the sum of the individual-cluster weights of the cells assigned to said second portion.

Claim 40

The method of claim 30, wherein the number of cells in the cluster is between 15 and 30.

Claim 41

The method of claim 30, wherein the first cluster affinity is a function of the following: The first portion weight less the following value: The second portion weight plus the region portion weight.

Claim 42

The method of claim 30, wherein said region is rectangular.

Claim 43

The method of claim 35, wherein said region is one of a plurality of rectangular regions of said surface such that (a) said plurality of rectangular regions is arranged in a rectangular grid with horizontal rows of rectangular regions and vertical rows of rectangular regions, (b) each region shares an edge with each adjacent region within its horizontal row of regions, and (c) each region shares an edge with each adjacent region within its vertical row of regions.

Claim 44

The method of claim 36, wherein the region portion comprises a row of rectangular regions.

Claim 45

The method of claim 37, wherein the region portion is rectangular.

Claim 46

The system of claim 38, wherein (a) said first portion comprises a first row of rectangular regions parallel to the row comprising the region portion and said second portion comprises a second row of rectangular regions parallel to the row comprising the region portion and (b) said first portion is on one side of the region portion and said second portion is on the opposite side of the region portion.

Claim 47

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) an encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for organizing a plurality of interrelated cells from said netlist into a cluster, wherein said cluster does not comprise all of the cells in the netlist; (c) an encoded instruction on said storage medium for, for each cell of said plurality of interrelated cells, assigning the cell an individual-cluster weight; (d) an encoded instruction on said storage medium for locating said cluster on an abstract of the surface of an integrated circuit device such that at least one of the cells is assigned to said region; (e) an encoded instruction on said storage medium for selecting a first cell from said cluster which is assigned to said region; (f) an encoded instruction on said storage medium for dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, a first portion which does not comprise the region, and a second portion which does not comprise the region and does not overlap said first portion; (g) an encoded instruction on said storage medium for calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (h) an encoded instruction on said storage medium for calculating a second portion weight, wherein said second portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said second portion; (i) an encoded instruction on said storage medium for calculating a region portion weight wherein said region portion weight is a function of the sum of the individual-cluster weights of the cells assigned to the region portion; (j) an encoded instruction on said storage medium for calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight and of the region portion weight; (k) an encoded instruction on said storage medium for calculating a second cluster affinity, wherein said second cluster affinity is a function of the second portion weight and the region portion weight; and (l) an encoded instruction on said storage medium for either leaving the first cell in the region portion or moving the first cell from the region portion to another portion as a function of said first cluster affinity and said second cluster affinity.

Claim 48

A machine-readable storage medium having instructions for a computer to process a netlist encoded therein, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit, in order to optimize placement of cells on an integrated circuit device, comprising: (a) an encoded instruction on said storage medium for accepting a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) an encoded instruction on said storage medium for organizing a plurality of interrelated cells from said netlist into a cluster, wherein said cluster does not comprise all of the cells in the netlist; (c) an encoded instruction on said storage medium for, for each cell of said plurality of interrelated cells, assigning the cell an individual-cluster weight; (d) an encoded instruction on said storage medium for locating said cluster on an abstract of the surface of an integrated circuit device such that at least one of the cells is assigned to said region; (e) an encoded instruction on said storage medium for selecting a first cell from said cluster which is assigned to said region; (f) an encoded instruction on said storage medium for dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, a first portion which does not comprise the region, and a second portion which does not comprise the region and does not overlap said first portion; (g) an encoded instruction on said storage medium for calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (h) an encoded instruction on said storage medium for calculating a second portion weight, wherein said second portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said second portion; (i) an encoded instruction on said storage medium for calculating a region portion weight wherein said region portion weight is a function of the sum of the individual-cluster weights of the cells assigned to the region portion; (j) an encoded instruction on said storage medium for calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight and of the region portion weight; (k) an encoded instruction on said storage medium for calculating a second cluster affinity, wherein said second cluster affinity is a function of the second portion weight and the region portion weight; and (l) an encoded instruction on said storage medium for either leaving the first cell in the region portion or moving the first cell from the region portion to another portion as a function of said first cluster affinity and said second cluster affinity.

Claim 49

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Supplying a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) organizing a plurality of interrelated cells from said netlist into a cluster, wherein said cluster does not comprise all of the cells in the netlist; (c) for each cell of said plurality of interrelated cells, assigning the cell an individual-cluster weight; (d) locating said cluster on an abstract of the surface of the integrated circuit device such that at least one of the cells is assigned to said region; (e) selecting a first cell from said cluster which is assigned to said region; (f) dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, a first portion which does not comprise the region, and a second portion which does not comprise the region and does not overlap said first portion; (g) calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (h) calculating a second portion weight, wherein said second portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said second portion; (i) calculating a region portion weight wherein said region portion weight is a function of the sum of the individual-cluster weights of the cells assigned to the region portion; (j) calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight and of the region portion weight; (k) calculating a second cluster affinity, wherein said second cluster affinity is a function of the second portion weight and the region portion weight; and (l) either leaving the first cell in the region portion or relocating the first cell from the region portion to another portion as a function of said first cluster affinity and said second cluster affinity and placing said first cell on at least one integrated circuit device as a function of its location on said surface abstract.

Claim 50

An integrated circuit device having its cell placement optimized with a method comprising the following steps: (a) Supplying a netlist, said netlist comprising cells and nets connected in a predetermined manner so as to define an integrated circuit; (b) organizing a plurality of interrelated cells from said netlist into a cluster, wherein said cluster does not comprise all of the cells in the netlist; (c) for each cell of said plurality of interrelated cells, assigning the cell an individual-cluster weight; (d) locating said cluster on an abstract of the surface of the integrated circuit device such that at least one of the cells is assigned to said region; (e) selecting a first cell from said cluster which is assigned to said region; (f) dividing the abstract of the surface of the integrated circuit device into a plurality of portions, said plurality of portions comprising a region portion which comprises the region, a first portion which does not comprise the region, and a second portion which does not comprise the region and does not overlap said first portion; (g) calculating a first portion weight, wherein said first portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said first portion; (h) calculating a second portion weight, wherein said second portion weight is a function of the individual-cluster weights of the cells of said cluster assigned to said second portion; (i) calculating a region portion weight wherein said region portion weight is a function of the sum of the individual-cluster weights of the cells assigned to the region portion; (j) calculating a first cluster affinity, wherein said first cluster affinity is a function of the first portion weight and of the region portion weight; (k) calculating a second cluster affinity, wherein said second cluster affinity is a function of the second portion weight and the region portion weight; and (l) either leaving the first cell in the region portion or relocating the first cell from the region portion to another portion as a function of said first cluster affinity and said second cluster affinity and placing said first cell on at least one integrated circuit device as a function of its location on said surface abstract.