Advanced modular cell placement system with universal affinity driven discrete placement optimization

• US 5,844,811 A
• Filed: 06/28/1996
• Issued: 12/01/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): Voeltz, Emanuel Todd
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/671,656
• Time in Patent Office: 886 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for improving the position of cells located on a surface of a semiconductor chip having at least one region located thereon is disclosed herein. The system calculates affinities for relocating the cell to an alternate region, computes a first threshold, and repositions all cells having a maximum affinity greater than the first threshold to the region providing the maximum affinity for the cell.

Claims

1. A method for improving a placement of elements on a region located on a surface, comprising the steps of:

a. calculating a maximal affinity for movement of the elements to any other region;

b. locating all elements having a maximum movement affinity greater than a first predetermined value;

c. selecting a first threshold such that the first threshold is less than a second predetermined value;

d. recalculating movement affinities for all elements to adjacent regions where maximum affinity is achieved; and

e. relocating any element having a maximum relocation affinity greater than the first threshold.

2. The method of claim 1, wherein the first threshold is a global threshold dependent on all elements located on the surface.

3. The method of claim 2, wherein the global threshold is calculated such that the number of elements whose maximum affinity is greater than the global threshold is less than a predetermined quantity multiplied by the original number of elements.

4. The method of claim 1, wherein the first threshold is a local threshold dependent on all elements located in the region.

5. The method of claim 1, wherein the first threshold is a combination of both a local threshold and a global threshold, and the maximal affinity of each element must be above both thresholds for the element to be moved.

6. The method of claim 1, wherein said calculating, locating, selecting, recalculating, and relocating steps form a minor step, and said method further comprises repeating said minor step a predetermined number of times.

7. The method of claim 1, wherein said calculating, locating, selecting, recalculating, and relocating steps form a minor step, and said method further comprises repeating said minor step until a predetermined accuracy is attained.

8. A method for improving a placement of elements initially positioned on a region on a surface, comprising the steps of:

a. computing an affinity for relocating each element to any adjacent region;

b. determining the maximum affinity for each element;

c. calculating a first threshold; and

d. relocating any element having its maximum affinity greater than said first threshold to the region providing said maximum affinity.

9. The method of claim 8, wherein said first threshold is a global threshold for all elements on the surface.

10. The method of claim 9, wherein the global threshold is calculated such that the number of elements whose maximum affinity is greater than the global threshold is less than a predetermined quantity multiplied by the original number of elements.

11. The method of claim 8, wherein said first threshold is a local threshold for all elements in the region.

12. The method of claim 8, wherein said computing, determining, calculating, and relocating steps form a minor step, and said method further comprises repeating said minor step a predetermined number of times.

13. The method of claim 8, wherein said computing, determining, calculating, and relocating steps form a minor step, and said method further comprises repeating said minor step until a predetermined accuracy is attained.

14. The method of claim 13, further comprising calculating a cost function after each minor step.

15. The method of claim 13, further comprising the step of updating a data structure when each element is moved as a result of said relocating step.

16. The method of claim 8, wherein said computing step further comprises computing an affinity for maintaining the element within its current region.

17. A method for determining an improved location for an element in a region on a surface, said system comprising:

a. calculating affinities for relocating the element to an alternate region;

b. computing a first threshold; and

c. repositioning any element having a maximum affinity greater than said first threshold to the region providing the maximum affinity for the element.

18. The method of claim 17, wherein said first threshold is a global threshold for all elements on the surface.

19. The method of claim 18, wherein the global threshold is calculated such that the number of elements whose maximum affinity is greater than the global threshold is less than a predetermined quantity multiplied by the original number of elements.

20. The method of claim 17, wherein said first threshold is a local threshold for all elements in the region.

21. The method of claim 17, wherein said calculating, computing, and repositioning steps form a minor step, and said system further comprises repeating said minor step a predetermined number of times.

22. The method of claim 17, wherein said calculating, computing, and repositioning steps form a minor step, and said system further comprises repeating said minor step until a predetermined accuracy is attained.

23. The method of claim 22, further comprising calculating a cost function after each minor step.

24. The method of claim 22, further comprising the step of updating a data structure when each element is moved as a result of said relocating step.

25. The method of claim 17, wherein said calculating step further comprises computing an affinity for maintaining the element within its current region.

26. A method for improving the position of cells located on a surface of a semiconductor chip having at least one region located thereon, comprising the steps of:

a. calculating affinities for relocating a cell to an alternate region;

b. computing a first threshold;

c. repositioning all cells having a maximum affinity greater than said first threshold to the region providing the maximum affinity for the cell.

27. The method of claim 26, wherein said first threshold is a global threshold for all cells on the surface of the chip.

28. The method of claim 27, wherein the global threshold is calculated such that the number of cells whose maximum affinity is greater than the global threshold is less than a predetermined quantity multiplied by the original number of cells.

29. The method of claim 26, wherein said first threshold is a local threshold for all cells in the region.

30. The method of claim 26, wherein said calculating, computing, and repositioning steps form a minor step, and said method further comprises repeating said minor step a predetermined number of times.

31. The method of claim 26, wherein said calculating, computing, and repositioning steps form a minor step, and said method further comprises repeating said minor step until a predetermined accuracy is attained.

32. The method of claim 31, further comprising calculating a cost function after each minor step.

33. The method of claim 31, further comprising the step of updating a data structure when each element is moved as a result of said relocating step.

34. The method of claim 26, wherein said calculating step further comprises computing an affinity for maintaining the cell within its current region.

35. A computer storage device having located thereon a computer program for improving the position of elements located on a surface having at least one region located thereon, comprising the following steps:

a. calculating affinities for relocating an element to an alternate region;

b. computing a first threshold; and

c. repositioning any element having a maximum affinity greater than said first threshold to the region providing the maximum affinity for the element.