Method and apparatus for solving an optimization problem in an integrated circuit layout

• US 7,216,308 B2
• Filed: 12/31/2002
• Issued: 05/08/2007
• Est. Priority Date: 11/18/2002
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Frankle, Jonathan
• Primary Examiner(s): Garbowski; Leigh M.
• Application Number:
  US10/335,239
• Publication Number:
  US 20040098678A1
• Time in Patent Office: 1,589 Days
• Field of Search: 716/2, 716/12, 702/123
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Some embodiments of the invention provide a method of solving an optimization problem. The problem includes a plurality of elements, and one or more solutions have been previously identified for each element. The method specifies a first solution set that has one identified solution for each element. In some embodiments, the method then iteratively examines all the elements of the problem. During the examination of each particular element, the method iteratively examines all the identified solutions for the particular element. During the examination of each particular solution, the method replaces the current solution for the particular element in the first solution set with a previously unexamined solution for the particular element if the replacement would improve the first set.

Claims

1. A method of solving an optimization problem that includes a plurality of elements in an integrated circuit (“

IC”

) layout, wherein one or more solutions are identified for each element in the plurality of elements, the method comprising;

a) specifying a first solution set that has one identified solution for each element in the plurality of elements, wherein each element is a net in the IC layout;

b) selecting a first element; and

c) in the first solution set, replacing a current solution for the first element with another identified solution for the first element if the replacement would improve the first solution set.

2. The method of claim 1, wherein the problem is a routing problem, and each solution is a route.

3. The method of claim 1, wherein the replacement would improve the first solution set if the replacement would improve a metric score that is computed for the first solution set.

4. The method of claim 3 further comprising:

a) computing a first metric score for the first solution set;

b) computing a second metric score for the first solution set when the current solution in the first solution set is replaced by the other identified solution for the first element; and

c) replacing the current solution with the other identified solution if the second metric score is better than the first metric score.

5. The method of claim 4, wherein the first and second metric scores are computed based on an objective function.

6. The method of claim 5, wherein a lower metric score is better than a higher metric score.

7. The method of claim 1 further comprising:

identifying a plurality of solution sets for the problem, wherein each solution set includes a solution for each element.

8. The method of claim 1, wherein the first solution set includes solutions for different elements that are taken from a second solution set and a third solution set.

9. The method of claim 1 further comprising:

iteratively examining all the identified solutions for the first element, and

during each examination of a particular identified solution for the first element, replacing the current solution for the first element in the first solution set with the particular identified solution if the replacement would improve the first solution set.

10. The method of claim 9 further comprising:

a) selecting a second element, the second element having an initial solution in the first solution set;

b) iteratively examining all the identified solutions for the second element, and during each examination of a particular identified solution for the second element, replacing the current solution for the second element in the first solution set with the particular identified solution if the replacement would improve the first solution set.

11. The method of claim 1 further comprising:

a) iteratively examining all elements in the plurality of elements; and

b) during the examination of each particular element, iteratively examining all the identified solutions for the particular element, wherein the iterative examination farther comprises replacing the current solution for the particular element in the first solution set with a particular identified solution if the replacement would improve the first solution set.

12. The method of claim 11, wherein each solution for a particular element has a computed occurrence frequency, wherein the elements are examined based on an order that depends on the occurrence frequencies of the identified solutions of the elements.

13. The method of claim 12, wherein the elements that have solutions with the higher occurrence frequencies are examined first.

14. The method of claim 11 further comprising:

a) iteratively specifying solution sets and improving the specified solution sets, wherein each solution set has one identified solution for each element;

b) during each iteration for a particular solution set, iteratively examining all elements in the plurality of elements;

i) during the examination of each particular element, iteratively examining all the identified solutions for the particular element, wherein the iterative examination farther comprises replacing the current solution for the particular element in the particular solution set with a particular identified solution if the replacement would improve the particular solution set.

15. A computer readable medium that stores a computer program which when executed by a processor solves an optimization problem that includes a plurality of elements in an integrated circuit (“

IC”

) layout, wherein one or more solutions are identified for each element in the plurality of elements, the computer program comprising executable sets of instructions that perform the steps of;

a) specifying a first solution set that has one identified solution for each element in the plurality of elements, wherein each element is a net in the IC layout;

b) selecting a first element; and

c) in the first solution set, replacing a current solution for the first element with another identified solution for the first element if the replacement would improve the first solution set.

16. The computer readable medium of claim 15, wherein the computer program further comprises executable sets of instructions that perform the steps of:

iteratively examining all the identified solutions for the first element; and

replacing, during each iteration, the current solution for the first element in the first solution set with a previously unexamined solution for the first element if the replacement would improve the first solution set.

17. The computer readable medium of claim 16, wherein the computer program further comprises executable sets of instructions that perform the steps of:

a) iteratively examining all elements in the plurality of elements;

b) during the examination of each particular element;

(i) iteratively examining all the identified solutions for the particular element; and

(ii) during each iteration, replacing the current solution for the particular element in the first solution set with a previously unexamined solution for the particular element if the replacement would improve the first solution set.

18. The computer readable medium of claim 17, wherein the computer program further comprises executable sets of instructions that perform the steps of:

a) iteratively specifying solution sets and attempting to improve the specified solution sets, wherein each solution set that has one identified solution for each element;

b) iteratively examining, during each iteration for a particular solution set, all elements in the plurality of elements;

i) during the examination of each particular element;

(1) iteratively examining all the identified solutions for the particular element; and

(2) during each iteration, replacing the current solution for the particular element in the particular solution set with a previously unexamined solution for the particular element if the replacement would improve the particular solution set.