Advanced modular cell placement system with iterative one dimensional preplacement optimization

• US 5,892,688 A
• Filed: 06/28/1996
• Issued: 04/06/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): Teska, Kevin J.
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/672,335
• Time in Patent Office: 1,012 Days
• Field of Search: 364/488-491, 364/578, 364/275.6, 364/971.96
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for providing an optimal preplacement of cells on a bounded surface of a semiconductor chip is disclosed herein. A percentage of the cells have predetermined interconnections with other cells. The system initially locates the cells on said surface, then computes coordinates for interconnected cells, determines a weight associated with each cell, and calculates a new cell coordinate for each cell based on the coordinates and weights from said determining step.

Claims

1. A method for placing elements on a surface, wherein elements may be associated in groups, comprising the steps of:

(a) locating each element at a predetermined position on said surface;

(b) computing a group coordinate for each group of elements based on the positions of all elements in the group;

(c) determining a weight for each element depending on a first parameter of the element; and

(d) calculating an element placement position from the weight received from said determining step and a sum of group coordinates for all groups with which the element is associated.

2. The method of claim 1, further comprising the step of iterating said computing and calculating steps until a predetermined threshold is achieved.

3. The method of claim 1, further comprising the step of iterating said computing and calculating steps for a predetermined number of times. the related element positions from said computing step and the element weight from said determining step.

4. A method for efficiently positioning a plurality of elements on a region of a surface, wherein said elements may be related in a particular manner, and wherein each element has associated therewith a number of subelements, comprising the steps of:

(a) initializing element positions on the surface;

(b) computing a related element position for each of plural sets of related elements;

(c) separately determining a weight for each element; and

(d) calculating a new element position for each element based on a function of the related element positions from said computing step multiplied by the weight determined for said each element.

5. The method of claim 4, further comprising the step of iterating said computing and calculating steps until a predetermined threshold is achieved.

6. The method of claim 4, further comprising the step of iterating said computing and calculating steps for a predetermined number of times.

7. The method of claim 4, wherein said computing step comprises summing positions of each set of related elements and dividing said sum by the number of subelements in the set of related elements.

8. The method of claim 7, wherein said determining step comprises computing the weight of each element based on the number of subelements associated with said element.

9. The method of claim 7, wherein said calculating step comprises multiplying the element weight received from said determining step by the sum of positions of each set of related elements received from said computing step.

10. The method of claim 4, wherein said method further comprises the step of establishing a revised position of related elements following said computing step, wherein said establishing step situates related elements, located outside said region as a result of said computing step, to be within said region.

22. The method of claim 4, wherein said method further comprises the step of establishing a revised position of related elements following said computing step, wherein said established step situates related elements, located outside said region as a result of said computing step, to be at a border of said region.

11. A method for providing an optimal preplacement of cells on a bounded surface of a semiconductor chip, wherein a percentage of said cells have predetermined interconnections with other cells, comprising the steps of:

(a) initially locating the cells on said surface;

(b) computing coordinates for each of plural sets of interconnected cells;

(c) separately determining a weight for each cell; and

(d) calculating a new cell coordinate for each cell based on a function of the coordinates from said computing step multiplied by the weight determined for said each cell.

12. The method of claim 11, further comprising the step of iterating said computing and calculating steps until a predetermined threshold is achieved.

13. The method of claim 11, further comprising the step of iterating said computing and calculating steps for a predetermined number of times.

14. The method of claim 11, wherein each cell has a number of pins associated therewith.

15. The method of claim 14, wherein each set of associated cells form a net, and wherein said computing step comprises summing the positions of all cells in each net and dividing the resulting sum by the number of pins in all cells in the net.

16. The method of claim 14, wherein said determining step comprises determining the weight associated with each cell based on the inverse of the sum of the inverse of the number of pins in all cells in the net.

17. The method of claim 14, wherein said calculating step comprises multiplying the cell weight received from said determining step by the sum of positions of each net received from said computing step.

18. The method of claim 11, further comprising the step of establishing a revised position of nets following said computing step, wherein said establishing step positions nets located outside said region to be on said region.

19. A computer storage device having located thereon a computer program comprising the following steps:

(a) locating elements at a predetermined position on a surface, wherein said elements may be associated in groups;

(b) computing a group coordinate for each group of elements based on the positions of all elements in the group;

(c) determining a weight for each element depending on a first parameter of the element;

(d) calculating an element placement position from the weight received from said determining step and a sum of group coordinates for all groups with which the element is associated.

20. The computer storage device of claim 19, wherein said computer program further comprises the step of:

iterating said computing and calculating steps until a predetermined threshold is achieved.

21. The computer storage device of claim 19, wherein said computer program further comprises the step of iterating said computing and calculating steps for a predetermined number of times.

23. A method for placing elements on a surface, wherein elements may be associated in groups, comprising the steps of:

locating each element at a predetennined position on said surface;

determining a group coordinate z q! for each cell v in net q wherein said group coordinate is ##EQU30## determining a weight for each element wherein said weight for cell v is ##EQU31## calculating an element placement position from said group coordinate and from said weight wherein said element placement position is ##EQU32##