Layout quality analyzer

• US 20040015805A1
• Filed: 07/22/2002
• Published: 01/22/2004
• Est. Priority Date: 07/22/2002
• Status: Active Grant

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Kidd, David A., Page, Matthew J., Dias, Nathan D.
• Granted Patent: US 6,877,147 B2
• Time in Patent Office: Days
• US Class Current: 716/12
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

In one embodiment, a computer readable medium comprises at least first instructions and second instructions. The first instructions, when executed, compute a first plurality of routes. Each route of the first plurality of routes corresponds to a respective net of a plurality of nets in an integrated circuit layout, and represents a theoretically optimal route of the respective net according to a graph theory based algorithm. The second instructions, when executed, compare each of the first plurality of routes to a corresponding route of a current plurality of routes, each of the current plurality of routes corresponding to the respective net of the plurality of nets and currently existing in the integrated circuit layout. A method is also contemplated.

Claims

1. A method comprising:

computing a first plurality of routes, each route of the first plurality of routes corresponding to a respective net of a plurality of nets in an integrated circuit layout, and each route representing a theoretically optimal route of the respective net according to a graph theory based algorithm; and

comparing each of the first plurality of routes to a corresponding route of a current plurality of routes, each of the current plurality of routes corresponding to the respective net of the plurality of nets and currently existing in the integrated circuit layout.

2. The method as recited in claim 1 wherein the comparing comprises computing a metric for each net of the plurality of nets, the metric for a first net of the plurality of nets representing a difference between a first route of the first plurality of routes and a second route of the current plurality of routes, wherein the first route and the second route correspond to the first net.

3. The method as recited in claim 2 wherein the comparing further comprises:

computing an attribute of the first route as an input to computing the metric; and

computing the attribute of the second route as an input to computing the metric.

4. The method as recited in claim 3 wherein the metric comprises a ratio of the attribute of the second route to the attribute of the first route.

5. The method as recited in claim 3 wherein the metric comprises a percentage difference of the attribute of the second route from the attribute of the first route.

6. The method as recited in claim 3 wherein the metric comprises a difference of the attribute of the first route from the attribute of the second route.

7. The method as recited in claim 3 wherein the attribute comprises a total length.

8. The method as recited in claim 3 wherein the attribute comprises a total capacitance.

9. The method as recited in claim 3 wherein the attribute comprises a total resistance.

10. The method as recited in claim 2 further comprising identifying one or more nets of the plurality of nets, the one or more nets having a greatest deviation, as indicated by the metric, between the corresponding route of the first plurality of routes and the corresponding route of the current plurality of routes.

11. The method as recited in claim 10 wherein identifying comprises sorting a list of the plurality of nets according to the metric.

12. The method as recited in claim 10 wherein identifying comprises listing a subset of the plurality of nets for which the metric exceeds a threshold.

13. The method as recited in claim 1 wherein the computing comprises omitting at least a first net from the plurality of nets.

14. The method as recited in claim 13 wherein the comparing comprising omitting the at least the first net.

15. The method as recited in claim 13 wherein the omitting comprises reading a list of nets to be omitted, the list comprising the first net.

16. The method as recited in claim 13 wherein the omitting comprises detecting a timeout while attempting to compute a route corresponding to the first net.

17. The method as recited in claim 1 further comprising deriving the plurality of nets from a second plurality of nets, the second plurality of nets comprises the plurality of nets and at least one net in addition to the plurality of nets, the at least one net having a positive timing margin.

34. The computer readable medium as recited in claim 17 further comprising fifth instructions which, when executed, derive the plurality of nets from a second plurality of nets, the second plurality of nets comprises the plurality of nets and at least one net in addition to the plurality of nets, the at least one net having a positive timing margin.

18. A computer readable medium comprising:

first instructions which, when executed, compute a first plurality of routes, each route of the first plurality of routes corresponding to a respective net of a plurality of nets in an integrated circuit layout, and each route representing a theoretically optimal route of the respective net according to a graph theory based algorithm; and

second instructions which, when executed, compare each of the first plurality of routes to a corresponding route of a current plurality of routes, each of the current plurality of routes corresponding to the respective net of the plurality of nets and currently existing in the integrated circuit layout.

19. The computer readable medium as recited in claim 18 wherein the second instructions comprise instructions which, when executed, compute a metric for each net of the plurality of nets, the metric for a first net of the plurality of nets representing a difference between a first route of the first plurality of routes and a second route of the current plurality of routes, wherein the first route and the second route correspond to the first net.

20. The computer readable medium as recited in claim 19 wherein the second instructions comprise instructions which, when executed:

compute an attribute of the first route as an input to computing the metric; and

compute the attribute of the second route as an input to computing the metric.

21. The computer readable medium as recited in claim 20 wherein the metric comprises a ratio of the attribute of the second route to the attribute of the first route.

22. The computer readable medium as recited in claim 20 wherein the metric comprises a percentage difference of the attribute of the second route from the attribute of the first route.

23. The computer readable medium as recited in claim 20 wherein the metric comprises a difference of the attribute of the first route from the attribute of the second route.

24. The computer readable medium as recited in claim 20 wherein the attribute comprises a total length.

25. The computer readable medium as recited in claim 20 wherein the attribute comprises a total capacitance.

26. The computer readable medium as recited in claim 20 wherein the attribute comprises a total resistance.

27. The computer readable medium as recited in claim 19 further comprising third instructions which, when executed, identify one or more nets of the plurality of nets, the one or more nets having a greatest deviation, as indicated by the metric, between the corresponding route of the first plurality of routes and the corresponding route of the current plurality of routes.

28. The computer readable medium as recited in claim 27 wherein the third instructions comprise instructions which, when executed, sort a list of the plurality of nets according to the metric.

29. The computer readable medium as recited in claim 27 wherein the third instructions comprises instructions which, when executed, list a subset of the plurality of nets for which the metric exceeds a threshold.

30. The computer readable medium as recited in claim 18 wherein the first instructions comprise fourth instructions which, when executed, omit at least a first net from the plurality of nets.

31. The computer readable medium as recited in claim 30 wherein the second instructions comprise instructions which, when executed omit the at least the first net.

32. The computer readable medium as recited in claim 30 wherein the fourth instructions comprise instructions which, when executed, read a list of nets to be omitted, the list comprising the first net.

33. The computer readable medium as recited in claim 30 wherein the fourth instructions comprise instructions which, when executed, detect a timeout while attempting to compute a route corresponding to the first net.