Advanced modular cell placement system with wire length driven affinity system

• US 5,831,863 A
• Filed: 06/28/1996
• Issued: 11/03/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): Teska, Kevin J.
• Assistant Examiner(s): GARBOWSKI, LEIGH M
• Application Number:
  US08/672,725
• Time in Patent Office: 858 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A system for determining an affinity associated with relocating a cell located on a surface of a semiconductor chip to a different location on the surface is disclosed herein. Each cell may be part of a cell net containing multiple cells. The system initially defines a bounding box containing all cells in the net which contains the cell. The system then establishes a penalty vector based on the bounding box and borders of a region containing the cell, computes a normalized sum of penalties for all nets having the cell as a member, and calculates the affinity based on the normalized sum of penalties.

Claims

1. A method for calculating a total penalty for relocating an element in a region on a surface to an alternate region on said surface, said element being part of a group of at least one element, comprising the steps of:

(a) locating maximum and minimum positions of the group on the surface;

(b) computing a penalty vector for the element based on said maximum and minimum positions and edges of said region; and

(c) computing a total penalty as a normalized sum of penalties for all groups having the element as a member of the group.

2. The method of claim 1, further comprising the step of calculating an affinity based on said total penalty.

3. The method of claim 1, wherein the penalty vector is a function of a left penalty vector representing movement of the element to the left, a function of a stationary penalty vector representing nonmovement of the element, and a function of a right penalty vector representing movement of the element to the right.

4. The method of claim 1, wherein the penalty vector is a function of an up penalty vector representing movement of the element upward, a function of a stationary penalty vector representing nonmovement of the element, and a function of a down penalty vector representing movement of the element downward.

5. A method for determining an affinity associated with relocating a cell located on a surface of a semiconductor chip to a different location on the surface, wherein each cell may be part of a net containing cells, comprising the steps of:

(a) defining a bounding box containing all cells in the net which contains the cell;

(b) establishing a penalty vector based on the bounding box and borders of a region containing the cell;

(c) computing a normalized sum of penalties for all nets having the cell as a member; and

(d) calculating the affinity based on the normalized sum of penalties.

6. A system for determining a propensity value associated with relocating an element in a bordered region on a surface to another location on the surface, wherein each element may be associated with a group of elements, said system comprising:

(a) means for defining a positional relationship between all elements in the group containing the element;

(b) means for establishing a vector based on the positional relationship and the borders of the region containing the element;

(c) means for computing a penalty value for all groups having the element as a member; and

(d) means for calculating the propensity value based on the penalty value.

7. A computer storage device containing instructions for determining an affinity associated with relocating a cell located on a surface abstract of a semiconductor chip to a different location on the surface abstract, wherein each cell may be part of a net containing cells, said instructions comprising instructions for a computer to take the following steps:

(a) defining a bounding box containing all cells in the net which contains the cell;

(b) establishing a penalty vector based on the bounding box and borders of a region containing the cell;

(c) computing a normalized sum of penalties for all nets having the cell as a member; and

(d) calculating the affinity based on the normalized sum of penalties.

8. A computer storage device having located thereon a computer program for determining a propensity value associated with relocating an element in a bordered region on a surface to another location on the surface, wherein each element may be associated with a group of elements, comprising the following steps:

(a) defining a positional relationship between all elements in a group containing an element;

(b) establishing a penalty vector based on the positional relationship and the borders of the region containing the element;

(c) computing a penalty value for all groups having the element as a member; and

(d) calculating a propensity value based on the penalty value.