Method and apparatus for computing minimum wirelength position (MWP) for cell in cell placement for integrated circuit chip

• US 5,859,781 A
• Filed: 08/01/1996
• Issued: 01/12/1999
• Est. Priority Date: 09/13/1994
• 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: D'Haeseleer, Patrik, Scepanovic, Ranko
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/690,942
• Time in Patent Office: 894 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 method and apparatus for positioning a cell in a cell placement for an integrated circuit chip such that a total wirelength for interconnect nets that are connected to said cell is substantially minimum includes constructing bounding boxes around the interconnect nets with the cell excluded respectively. A median interval of the bounding boxes within which the total wirelength is substantially invariant is computed, and the cell is positioned in the median interval. Another optimization methodology, such as for minimizing interconnect congestion, is then applied to compute and position the cell in an optimum location in the median interval.

Claims

1. A method of positioning a cell in a cell placement for an integrated circuit chip such that a total wirelength for interconnect nets that are connected to said cell is substantially minimum, comprising steps of:

(a) constructing bounding boxes around said interconnect nets with said cell excluded respectively;

(b) computing vertical and horizontal median intervals of said bounding boxes within which said total wirelength is substantially invariant; and

(c) positioning said cell in said median intervals.

2. A method as in claim 1, in which step (b) comprises computing said median interval as having coordinates x,y in first and second orthogonal directions respectively given by ##EQU5## where i designates said interconnect nets respectively;

xia and xib are edges of bounding box for interconnect net i in said first direction;

yia and yib are edges of bounding box for interconnect net i in said second direction;

x≠

xia≠

xib, y≠

yia≠

yib;

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=+1 for (x-xia), (x-xib), (y-yia), (y-yib)>

0 respectively; and

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=-1 for (x-xia), (x-xib), (y-yia), (y-yib)<

0 respectively.

3. A method as in claim 1, further comprising the step of:

(d) calculating an optimal position for said cell within said median interval using a predetermined optimization criteria; and

(e) moving said cell to said optimal position.

4. A method as in claim 3, in which step (d) comprises calculating said optimal position as corresponding to minimum cell interconnect congestion.

5. A computing apparatus for optimizing a cell placement for an integrated circuit chip such that a total wirelength for interconnect nets that are connected to a cell in said placement is substantially minimum, comprising:

a bounder for constructing bounding boxes around said interconnect nets with said cell excluded respectively;

a processor for computing vertical and horizontal median intervals of said bounding boxes within which said total wirelength is substantially invariant; and

a positioner for positioning said cell in said median intervals.

6. An apparatus as in claim 5, in which the processor computes said median interval as having coordinates x,y in first and second orthogonal directions respectively given by ##EQU6## where i designates said interconnect nets respectively;

xia and xib are edges of bounding box for interconnect net i in said first direction;

yia and yib are edges of bounding box for interconnect net i in said second direction;

x≠

xia≠

xib, y≠

yia≠

yib;

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=+1 for (x-xia), (x-xib), (y-yia), (y-yib)>

0 respectively; and

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=-1 for (x-xia), (x-xib), (y-yia), (y-yib)<

0 respectively.

7. An apparatus as in claim 5, in which:

the processor further calculates an optimal position for said cell within said median interval using a predetermined optimization criteria; and

the positioner moves said cell to said optimal position.

8. An apparatus as in claim 7, in which the processor calculates said optimal position as corresponding to minimum cell interconnect congestion.

9. A computing apparatus for optimizing a cell placement for an integrated circuit chip such that total wirelengths for interconnect nets that are connected to selected cells in said placement are substantially minimum respectively, comprising:

a plurality of processing units for simultaneously operating on said selected cells in parallel, each processing unit including;

a bounder for constructing bounding boxes around said interconnect nets with said cell excluded respectively;

a processor for computing vertical and horizontal median intervals of said bounding boxes within which said total wirelength is substantially invariant; and

a positioner for positioning said cell in said median intervals.

10. An apparatus as in claim 9, in which the processors compute said median intervals as having coordinates x,y in first and second orthogonal directions respectively given by ##EQU7## where i designates said interconnect nets respectively;

xia and xib are edges of bounding box for interconnect net i in said first direction;

yia and yib are edges of bounding box for interconnect net i in said second direction;

x≠

xia≠

xib, y≠

yia≠

yib;

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=+1 for (x-xia), (x-xib), (y-yia), (y-yib)>

0 respectively; and

sgn(x-xia), sgn(x-xib), sgn(y-yia), sgn(y-yib)=-1 for (x-xia), (x-xib), (y-yia), (y-yib)<

0 respectively.

11. A method of positioning a cell on an integrated circuit (IC) chip to minimize total rectilinear distance to a set of interconnect nets, said method comprising steps of:

constructing rectangular bounding boxes around each of the interconnect nets, each of said bounding boxes having left and right (X-axis) and top and bottom (Y-axis) boundaries;

determining orthogonal positional values of said boundaries of each of the bounding boxes;

determining vertical and horizontal median intervals of said bounding boxes by computing median values of said bounding boxes for each of two orthogonal directions; and

positioning the cell in said median intervals.

12. The method of positioning a cell according to claim 11 wherein when the number of interconnect nets is even, said median interval is defined by, for each of the orthogonal directions, the two middle boundary values for that orthogonal direction.

13. The method of positioning a cell according to claim 12 further comprising the step of determining an optimal position for said cell within or on said median interval using predetermined criteria.

14. The method of positioning a cell according to claim 11 wherein when the number of interconnect nets is odd, said median interval is defined by a single point which is the median boundary value of each of the orthogonal directions.