Advanced modular cell placement system with dispersion-driven levelizing system

• US 5,870,312 A
• Filed: 06/28/1996
• Issued: 02/09/1999
• 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): Trans, Vincent N.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/672,652
• Time in Patent Office: 956 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/122
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for optimizing the density of cells located on a surface of a semiconductor chip divided into a plurality of rectangular regions is provided herein. The corners of these regions define nodes. The system comprises computing an average local cell density for regions adjacent to each node and deforming these regions by relocating nodes to positions that minimize a cost function associated with the densities of the new deformed regions bordering the relocated nodes.

Claims

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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