Timing-driven placement method utilizing novel interconnect delay model

• US 6,901,571 B1
• Filed: 01/21/1998
• Issued: 05/31/2005
• Est. Priority Date: 01/21/1998
• Status: Expired due to Fees

• Current Assignee: Bell Semiconductor, LLC (Hilco Inc. (d/b/a Hilco Global))
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Pavisic, Ivan, Petranovic, Dusan, Scepanovic, Ranko
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/010,396
• Time in Patent Office: 2,687 Days
• Field of Search: 395/500.11, 39550002-50019, 716/10, 716/4
• US Class Current: 716/113
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for optimal placement of cells on a surface of an integrated circuit, comprising the steps of comparing a placement of cells to predetermined cost criteria and moving cells to alternate locations on the surface if necessary to satisfy the cost criteria. The cost criteria include a timing criterion based upon interconnect delay, where interconnect delay is modeled as a RC tree expressed as a function of pin-to-pin distance. The method accounts for driver to sink interconnect delay at the placement level, a novel aspect resulting from use of the RC tree model, which maximally utilizes available net information to produce an optimal timing estimate. Preferred versions utilize a RC tree interconnect delay model that is consistent with timing models used at design levels above placement, such as synthesis, and below placement, such as routing. Additionally, preferred versions can utilize either a constructive placement or iterative improvement placement method.

Claims

1. A method for placement of a plurality of cells on a surface of an integrated circuit, said method comprising the steps of:

comparing a placement of the cells to predetermined cost criteria; and

moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon an interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INT}}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\frac{r_0<br><br>c_0}{2}<br><br>\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>l_i^2$

2. A method for placement of a plurality of cells on a surface of an integrated circuit, said method comprising the steps of:

comparing a placement of the cells to predetermined cost criteria; and

moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon an interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein an upper bound for the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INTi}}\le <br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_i<br><br>\left(l_i+1\right)+r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\underset{j=1,j\ne <br><br>i}{\overset{k}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_j^2$

3. An integrated circuit comprising:

a silicon base having a plurality of cells and associated interconnections fabricated thereon; and

a package containing the silicon base, wherein the package has a plurality of contacts which provide external output and input for the cells,

wherein the cells have been placed within the integrated circuit to satisfy predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect was modeled as a network of distributed resistors and capacitors, and

wherein the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INT}}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\frac{r_0<br><br>c_0}{2}<br><br>\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>l_i^2$

4. An integrated circuit comprising:

a silicon base having a plurality of cells and associated interconnections fabricated thereon; and

a package containing the silicon base, wherein the package has a plurality of contacts which provide external output and input for the cells,

wherein the cells have been placed within the integrated circuit to satisfy predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect was modeled as a network of distributed resistors and capacitors, and

wherein an upper bound for the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INTi}}\le <br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_i<br><br>\left(l_i+1\right)+r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\underset{j=1,j\ne <br><br>i}{\overset{k}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_j^2$

5. An apparatus for determining a placement of a plurality of cells within an integrated circuit (IC) chip, said apparatus comprising:

a processor; and

memory connected to said processor,

said memory having instructions for comparing a placement of the cells to predetermined cost criteria, and moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INT}}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\frac{r_0<br><br>c_0}{2}<br><br>\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>l_i^2$

6. An apparatus for determining a placement of a plurality of cells within an integrated circuit (IC) chip, said apparatus comprising:

a processor; and

memory connected to said processor,

said memory having instructions for comparing a placement of the cells to predetermined cost criteria, and moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein an upper bound for the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INTi}}\le <br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_i<br><br>\left(l_i+1\right)+r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\underset{j=1,j\ne <br><br>i}{\overset{k}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_j^2$

7. A computer storage medium containing instructions for a processor to determine a placement of a plurality of cells on a surface of an integrated circuit, said instructions comprising the steps of:

comparing a placement of the cells to predetermined cost criteria; and

moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay, the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INT}}=\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\frac{r_0<br><br>c_0}{2}<br><br>\underset{i=1}{\overset{k}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>l_i^2$

8. A computer storage medium containing instructions for a processor to determine a placement of a plurality of cells on a surface of an integrated circuit, said instructions comprising the steps of:

comparing a placement of the cells to predetermined cost criteria; and

moving cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein to determine the delay the interconnect is modeled as a network of distributed resistors and capacitors, and

wherein an upper bound for the interconnect delay is calculated according to the equation ${\mathrm{\Delta <br><br>}}_{\mathrm{INTi}}\le <br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_i<br><br>\left(l_i+1\right)+r_0<br><br>l_i<br><br>C_{\mathrm{Si}}+\underset{j=1,j\ne <br><br>i}{\overset{k}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_j<br><br>\frac{r_0<br><br>c_0}{2}<br><br>l_j^2$

9. A method for placement of a plurality of cells on a surface of an integrated circuit, said method comprising the steps of:

calculating an interconnect delay, defined as a delay for an interconnect between a driver and a sink in a placement of cells;

comparing the placement of the cells to predetermined cost criteria which include a timing criterion based upon the interconnect delay; and

moving cells in the placement of cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the interconnect is part of a net, and wherein calculation of the interconnect delay comprises determining a first delay that accounts for a contribution of a direct path between the driver and the sink and determining a second delay that accounts for a contribution of a portion of the net that does not include the direct path to the interconnect delay, and

wherein modeling the interconnect comprises utilizing a term that corresponds to a length of an overlapping wire.

10. An integrated circuit comprising:

a silicon base having a plurality of cells and associated interconnections fabricated thereon; and

a package containing the silicon base, wherein the package has a plurality of contacts which provide external output and input for the cells,

wherein the cells have been placed within the integrated circuit to satisfy predetermined cost criteria,

wherein the predetermined cost criteria include a timing criterion based upon interconnect delay, which is defined as a delay associated with an interconnect,

wherein the interconnect is part of a net, and wherein calculation of the interconnect delay comprises determining a first delay that accounts for a contribution of a direct path between the driver and the sink and determining a second delay that accounts for a contribution of a portion of the net that does not include the direct path to the interconnect delay, and

wherein modeling the interconnect comprised utilizing a term that corresponds to a length of an overlapping wire.

11. An apparatus for determining a placement of a plurality of cells within an integrated circuit (IC) chip, said apparatus comprising:

a processor; and

memory connected to said processor,

said memory having instructions for calculating an interconnect delay, defined as a delay for an interconnect between a driver and a sink in a placement of cells, comparing the placement of cells to predetermined cost criteria which include a timing criterion based upon the interconnect delay, and moving cells in the placement of cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the interconnect is part of a net, and wherein calculation of the interconnect delay comprises determining a first delay that accounts for a contribution of a direct path between the driver and the sink and determining a second delay that accounts for a contribution of a portion of the net that does not include the direct path to the interconnect delay, and

wherein modeling the interconnect comprises utilizing a term that corresponds to a length of an overlapping wire.

12. A computer storage medium containing instructions for a processor to determine a placement of a plurality of cells on a surface of an integrated circuit, said instructions comprising the steps of:

calculating an interconnect delay, defined as a delay for an interconnect between a driver and a sink in a placement of cells;

comparing the placement of the cells to predetermined cost criteria which include a timing criterion based upon the interconnect delay; and

moving cells in the placement of cells to alternate locations on the surface if necessary to satisfy the predetermined cost criteria,

wherein the interconnect is part of a net, and wherein calculation of the interconnect delay comprises determining a first delay that accounts for a contribution of a direct path between the driver and the sink and determining a second delay that accounts for a contribution of a portion of the net that does not include the direct path to the interconnect delay, and

wherein modeling the interconnect comprises utilizing a term that corresponds to a length of an overlapping wire.