Method and system for implementing an analytical wirelength formulation

US 7,797,649 B1
Filed: 01/22/2007
Issued: 09/14/2010
Est. Priority Date: 12/29/2004
Status: Expired due to Fees

First Claim

Patent Images

1. A computer implemented method of estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“

IC”

) layout, the net representing interconnections between a set of circuit elements in the IC layout, the method comprising;

using a processor configured for;

identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;

determining a bounding box that encompasses the plurality of circuit elements of the net, whereinat least a part of boundaries of the bounding box is determined by a continuous formulation rather than by a point-by-point comparison of coordinates for locations of a plurality of points to route for the plurality of circuit elements; and

using the bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and

using a computer readable storage medium or a computer storage device for storing at least the bounding box or using a display apparatus configured for displaying the bounding box.

View all claims

0 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

Disclosed are methods and systems for specifying an analytical wirelength formulation that is continuous along with its derivative. One approach performs a wirelength estimate in which a continuous formulation is employed to identify and use a bounding box to enclose circuit elements of a net, and in which an attribute of the bounding box may be completely or partially diagonal. Such formulations are used for optimizing the wirelength using numerical approaches.

14 Citations

View as Search Results

26 Claims

1. A computer implemented method of estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the method comprising;
  
  using a processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining a bounding box that encompasses the plurality of circuit elements of the net, whereinat least a part of boundaries of the bounding box is determined by a continuous formulation rather than by a point-by-point comparison of coordinates for locations of a plurality of points to route for the plurality of circuit elements; and
  
  using the bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and
  
  using a computer readable storage medium or a computer storage device for storing at least the bounding box or using a display apparatus configured for displaying the bounding box.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 14)
- - 2. The method of claim 1 in which the boundaries of the bounding box are determined using at least one of the following functions:
    - Xmin(x(1),y(1), . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      x(i)/scale))
      Xmax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(x(i)/scale)))
      Ymin(x(1),y(1), . . . x(n),y(n))=−
      
      scale*log(Sum(e**(y(i)/scale))
      Ymax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(y(i)/scale)))
      SW(x(1),y(1) . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      (x(i)+y(i))/scale)))
      NE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)+y(i))/scale)))
      NW(x(1),y(1) . . . x(n),y(n))=−
      
      scale*log(Sum(e**(−
      
      (x(i)−
      
      y(i))/scale)))
      SE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)−
      
      y(i))/scale))).
  - 3. The method of claim 2 in which the bounding box length is determined using the following function:
    - $B BOX (x (1), y (1) \dots x (n), y (n)) == sqrt (2) * (SW (x (1), y (1) \dots x (n), y (n)) - X \min (x (1), y (1) \dots x (n), y (n)) - Y \min (x (1), y (1) \dots x (n), y (n))) + (SE (x (1), y (1) \dots x (n), y (n)) - SW (x (1), y (1) \dots x (n), y (n)) + 2 * Y \min (x (1), y (1) \dots x (n), y (n))) + sqrt (2) * (X \max (x (1), y (1) \dots x (n), y (n)) - Y \min (x (1), y (1) \dots x (n), y (n)) - SE (x (1), y (1) \dots x (n), y (n)) + (NE (x (1), y (1) \dots x (n), y (n)) + SE (x (1), y (1) \dots x (n), y (n)) - 2 * X \max (x (1), y (1) \dots x (n), y (n))) + sqrt (2) * (NE (x (1), y (1) \dots x (n), y (n)) - X \max (x (1), y (1) \dots x (n), y (n)) - Y \max (x (1), y (1) \dots x (n), y (n))) + (NE (x (1), y (1) \dots x (n), y (n)) - NW (x (1), y (1) \dots x (n), y (n)) - 2 * Y \max (x (1), y (1) \dots x (n), y (n))) + sqrt (2) * (NW (x (1), y (1) \dots x (n), y (n)) - X \min (x (1), y (1) \dots x (n), y (n)) + Y \max (x (1), y (1) \dots x (n), y (n))) + (2 * X \min (x (1), y (1), \dots x (n), y (n)) - NW (x (1), y (1) \dots x (n), y (n)) - SW (x (1), y (1), \dots x (n), y (n))) .$
  - 4. The method of claim 2 in which the bounding box length is determined using the following function:
    - $\frac{1}{2} X Bounding Box length = (sqrt (2) - 1) (X \max (x (1), y (1) \dots x (n), y (n)) - X \min (x (1), y (1) \dots x (n), y (n)) + Y \max (x (1), y (1) \dots x (n), y (n)) - Y \min (x (1), y (1) \dots x (n), y (n))) + (1 - (1 / sqrt (2))) (NE (x (1), y (1) \dots x (n), y (n)) - SW (x (1), y (1) \dots x (n), y (n)) + SE (x (1), y (1) \dots x (n), y (n)) - NW (x (1), y (1) \dots x (n), y (n))) .$
  - 5. The method of claim 1, in which the interconnect line length cost is estimated as half of a length of the boundaries of the bounding box.
  - 6. The method of claim 1, wherein the estimate of the interconnect line length cost is measured to obtain a placement cost of an initial placement configuration.
  - 7. The method of claim 1 further comprising:
    - modifying the position of at least one of the plurality of circuit elements of the net;
      
      after said modification,constructing a second bounding box that encompasses the plurality of circuit elements of the net; and
      
      obtaining a second estimate of the interconnect line length cost needed to connect at least some of the plurality of circuit elements of the net.
  - 8. The method of claim 1, wherein the at least one diagonal routing direction forms a 45, 60, or 120 degree angle with respect to a side of the IC layout.
  - 9. The method of claim 1, wherein the plurality of circuit elements include one or more pins of one or more circuit modules.
  - 10. The method of claim 1 in which the bounding box is determined using a formulation that is continuous along with its derivative.
  - 14. The computer program product of claim 1 further comprising:
    - modifying the position of at least one of the plurality of circuit elements of the net;
      
      constructing a second bounding box that encompasses the plurality of circuit elements of the net; and
      
      obtaining a second estimate of the interconnect line length cost needed to connect the plurality of circuit elements of the net.

11. A computer program product comprising a computer usable storage medium having executable code which, when executed by a processor, causes the processor to execute a process for estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the process comprising;
  
  using the processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining a bounding box that encompasses the plurality of circuit elements of the net, whereinat least a part of boundaries of the bounding box is determined by a continuous formulation rather than by a point-by-point comparison of coordinates for locations of a plurality of points to route for the plurality of circuit elements; and
  
  using the bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net.
- View Dependent Claims (12, 13)
- - 12. The computer program product of claim 11 in which the boundaries of the bounding box are determined using at least one of the following functions:
    - Xmin(x(1),y(1), . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      x(i)/scale))
      Xmax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(x(i)/scale)))
      Ymin(x(1),y(1), . . . x(n),y(n))=−
      
      scale*log(Sum(e**(y(i)/scale))
      Ymax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(y(i)/scale)))
      SW(x(1),y(1) . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      (x(i)+y(i))/scale)))
      NE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)+y(i))/scale)))
      NW(x(1),y(1) . . . x(n),y(n))=−
      
      scale*log(Sum(e**(−
      
      (x(i)−
      
      y(i))/scale)))
      SE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)−
      
      y(i))/scale))).
  - 13. The computer program product of claim 11, in which the interconnect line length cost is estimated as half of length of the boundaries of the bounding box.

15. A system for estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the system comprising;
  
  a processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining a bounding box that encompasses the plurality of circuit elements of the net, whereinat least a part of boundaries of the bounding box is determined by a continuous formulation rather than by a point-by-point comparison of coordinates for locations of a plurality of points to route for the plurality of circuit elements; and
  
  using the bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and
  
  a computer readable storage medium or a computer storage device for storing at least the bounding box or a display apparatus configured for displaying the bounding box.
- View Dependent Claims (16, 17, 18)
- - 16. The system of claim 15 in which the boundaries of the bounding box are determined using at least one of the following functions:
    - Xmin(x(1),y(1), . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      x(i)/scale))
      Xmax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(x(i)/scale)))
      Ymin(x(1),y(1), . . . x(n),y(n))=−
      
      scale*log(Sum(e**(y(i)/scale))
      Ymax(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**(y(i)/scale)))
      SW(x(1),y(1) . . . x(n),y(n)=−
      
      scale*log(Sum(e**(−
      
      (x(i)+y(i))/scale)))
      NE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)+y(i))/scale)))
      NW(x(1),y(1) . . . x(n),y(n))=−
      
      scale*log(Sum(e**(−
      
      (x(i)−
      
      y(i))/scale)))
      SE(x(1),y(1) . . . x(n),y(n))=scale*log(Sum(e**((x(i)−
      
      y(i))/scale))).
  - 17. The system of claim 15, in which the interconnect line length cost is estimated as ½
    - the length of the boundaries of the bounding box.
  - 18. The system of claim 15, in which the processor is further configured for:
    - modifying the position of at least one circuit elements of the net;
      
      constructing a second bounding box that encompasses the circuit elements of the net; and
      
      obtaining a second estimate of the interconnect line length needed to connect the circuit elements of the net.

19. A computer implemented method of estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the method comprising;
  
  using a processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining an octagonal bounding box that encompasses the plurality of circuit elements of the net, wherein at least a part of boundaries of the octagonal bounding box is determined by a continuous formulation rather than by a point-by-point comparison of locations of a plurality of points to route for at least some of the plurality of circuit elements; and
  
  using the octagonal bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and
  
  using a computer readable storage medium or a computer storage device for storing at least the bounding box or using a display apparatus configured for displaying the bounding box.
- View Dependent Claims (20)
- - 20. The method of claim 19 in which the interconnect line length is estimated by calculating one-half of a length of the octagonal bounding box.

21. A computer program product comprising a computer usable storage medium having executable code which, when executed by a processor, causes the processor to execute a process for estimating an interconnect line length cost to connect circuit, elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the process comprising;
  
  using a processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining an octagonal bounding box that encompasses the plurality of circuit elements of the net, wherein at least a part of boundaries of the octagonal bounding box is determined by a continuous formulation rather than by a point-by-point comparison of locations of a plurality of points to route for at least some of the plurality of circuit elements; and
  
  using the octagonal bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and
  
  using a computer readable storage medium or a computer storage device for storing at least the bounding box or using a display apparatus configured for displaying the bounding box.
- View Dependent Claims (22, 23)
- - 22. The computer program product of claim 21, wherein the process further comprises:
    - modifying the position of at least one of the plurality of circuit elements of the net;
      
      after said modification,constructing a second bounding box that encompasses the plurality of circuit elements of the net; and
      
      obtaining a second estimate of the interconnect line length cost needed to connect at least some of the plurality of circuit elements of the net.
  - 23. The computer program product of claim 21, wherein the interconnect line length is estimated by calculating one-half of a length of the octagonal bounding box.

24. A system for estimating an interconnect line length cost to connect circuit elements of a net in an integrated circuit (“
- IC”
  
  ) layout, the net representing interconnections between a set of circuit elements in the IC layout, the system comprising;
  
  a processor configured for;
  
  identifying a plurality of circuit elements for the net, wherein at least one diagonal routing direction is available to route at least one of the interconnections between at least two of the plurality of circuit elements;
  
  determining an octagonal bounding box that encompasses the plurality of circuit elements of the net, wherein at least a part of boundaries of the octagonal bounding box is determined by a continuous formulation rather than by a point-by-point comparison of locations of a plurality of points to route for at least some of the plurality of circuit elements; and
  
  using the octagonal bounding box to estimate the interconnect line length cost to connect the plurality of circuit elements of the net; and
  
  a computer readable storage medium or a computer storage device for storing at least the bounding box or a display apparatus configured for displaying the bounding box.
- View Dependent Claims (25, 26)
- - 25. The system of claim 24, wherein the processor is further configured for:
    - modifying the position of at least one of the plurality of circuit elements of the net;
      
      after said modification,constructing a second bounding box that encompasses the plurality of circuit elements of the net; and
      
      obtaining a second estimate of the interconnect line length cost needed to connect at least some of the plurality of circuit elements of the net.
  - 26. The system of claim 24, wherein the interconnect line length is estimated by calculating one-half of a length of the octagonal bounding box.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Cadence Design Systems Incorporated (Cadence Group)
Original Assignee
Cadence Design Systems Incorporated (Cadence Group)
Inventors
Belkhale, Krishna, Etawil, Hussein
Primary Examiner(s)
DO, THUAN V

Application Number

US11/656,791
Time in Patent Office

1,331 Days
Field of Search

716/2, 716/4, 716/11, 716/14
US Class Current

716/130
CPC Class Codes

G06F 30/392 Floor-planning or layout, e...

Method and system for implementing an analytical wirelength formulation

First Claim

0 Assignments

0 Petitions

Accused Products

Abstract

14 Citations

26 Claims

Specification

Solutions

Use Cases

Quick Links

Method and system for implementing an analytical wirelength formulation

First Claim

0 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

14 Citations

26 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links