Advanced modular cell placement system with neighborhood system driven optimization

• US 5,812,740 A
• Filed: 06/28/1996
• Issued: 09/22/1998
• Est. Priority Date: 06/28/1996
• Status: Expired due to Term

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Scepanovic, Ranko, Andreev, Alexander E., Koford, James S.
• Primary Examiner(s): Downs, Robert W.
• Assistant Examiner(s): Smith, Jeffrey S.
• Application Number:
  US08/674,605
• Time in Patent Office: 816 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 395/10
• US Class Current: 706/45
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: Y10S 706/921 Layout, e.g. circuit, construction

Abstract

A system for computing an affinity for relocating a cell on a surface of a semiconductor chip is disclosed herein. The cell is located within a region and belongs to a net of cells. The system initially computes a weight associated with all cells in the net. The sytem then sums the weights of all cells in the net containing the cell for all cells located inside the region and at positions greater than and less than edges of the region and computes the affinity for moving the cell to points on the surface greater than, equal to, and less than the current position of the cell based on the weight sums from said summing function. The computing function further comprises combining the affinities determined based on weight sums with other affinities. The summing function further comprises computing a relationship between the amount of rows and columns of regions on the semiconductor chip surface, and the affinity computation function comprises combining the relationship with the weight sums.

Claims

1. A method for optimizing the placement of cells on the surface of an integrated circuit device, said method comprising:

(a) Supplying 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.

2. 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.

3. 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.

4. 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.

5. 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.

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

7. 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.

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

9. A method for optimizing the placement of interrelated cells on the surface of an integrated circuit device, wherein said surface has a region thereon, said method comprising:

(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;

(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 an 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.

10. 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.

11. 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.

12. 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.

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

14. 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.

15. 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.

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

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

18. 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.

19. 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.

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

21. 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.

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

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

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. A method for optimizing the placement of interrelated cells on the surface of an integrated circuit device, wherein said surface has a region thereon, said method comprising:

(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.

31. 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.

32. 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.

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

34. 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.

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

36. 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.

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

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

39. 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.

40. 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.

41. 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.