Method and apparatus for assigning nets to metal layers during circuit routing

• US 20040025134A1
• Filed: 08/02/2002
• Published: 02/05/2004
• Est. Priority Date: 08/02/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Jung, Dae Suk, Pai, Yet-Ping, Cho, Seong Rai
• Granted Patent: US 6,738,959 B2
• Time in Patent Office: Days
• US Class Current: 716/13
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

One embodiment of the present invention provides a system that facilitates routing nets between cells in a circuit layout. During operation, the system receives a circuit design to be routed, wherein the circuit design includes multiple circuit blocks that have been placed at specific locations within the circuit layout. Next, the system determines estimated lengths for nets that couple these circuit blocks together. The system then calculates the delay for the nets that couple the circuit blocks using a class one rule. If the delay in a given net is greater than a specified delay, the system inserts a virtual repeater into the given net to decrease the delay.

Claims

1. A method for routing nets between cells in a circuit layout, comprising:

receiving a circuit design for circuit routing, wherein the circuit design includes a plurality of circuit blocks that have been placed at specific locations in the circuit layout;

determining estimated lengths for nets coupling the plurality of circuit blocks;

calculating a delay for nets coupling the plurality of circuit blocks using a class one rule; and

if the delay in a given net is greater than a specified delay, inserting a virtual repeater in the given net to decrease the delay.

2. The method of claim 1, wherein determining estimated lengths for nets coupling the plurality of circuit blocks involves computing a Steiner tree.

3. The method of claim 1, wherein determining estimated lengths for nets involves assigning nets to metal layers.

4. The method of claim 1, wherein the class one rule assigns the given net to a first through fourth metal layer.

5. The method of claim 1, wherein if the delay is less than one cycle of a clock, the method further comprises assigning the given net to a first group.

6. The method of claim 5, wherein if the delay is not less than one clock cycle the method further comprises:

calculating the delay for nets coupling the plurality of circuit blocks using a class two rule; and

if the delay in the given net is greater than the specified delay, inserting the virtual repeater in the given net to decrease the delay.

7. The method of claim 6, wherein the class two rule assigns the given net to a fifth through sixth metal layer.

8. The method of claim 6, wherein if the delay is less than one clock cycle, the method further comprises assigning the given net to a second group.

9. The method of claim 8, wherein if the delay is not less than one clock cycle the method further comprises:

calculating the delay for nets coupling the plurality of circuit blocks using a class three rule; and

if the delay in the given net is greater than the specified delay, inserting the virtual repeater in the given net to decrease the delay.

10. The method of claim 9, wherein the class three rule assigns the given net to a seventh through eighth metal layer.

11. The method of claim 9, wherein if the delay is less than one clock cycle, the method further comprises assigning the given net to a third group.

12. The method of claim 11, further comprising reporting the first group, the second group, and the third group, whereby reporting these groups provides a starting assignment of nets to metal layers for a subsequent routing process.

13. The method of claim 9, wherein if the delay is not less than one clock cycle, the method further comprises:

inserting a virtual flip-flop in the given net;

changing a delay criterion from greater than one clock cycle to greater than two clock cycles; and

repeating the method from calculating the delay for nets coupling the plurality of circuit blocks using the class one rule.

14. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for routing nets between cells in a circuit layout, comprising:

receiving a circuit design for circuit routing, wherein the circuit design includes a plurality of circuit blocks that have been placed at specific locations in the circuit layout;

determining estimated lengths for nets coupling the plurality of circuit blocks;

calculating a delay for nets coupling the plurality of circuit blocks using a class one rule; and

if the delay in a given net is greater than a specified delay, inserting a virtual repeater in the given net to decrease the delay.

15. The computer-readable storage medium of claim 14, wherein determining estimated lengths for nets coupling the plurality of circuit blocks involves computing a Steiner tree.

16. The computer-readable storage medium of claim 14, wherein determining the estimated length for the nets involves assigning the nets to metal layers.

17. The computer-readable storage medium of claim 14, wherein the class one rule assigns the given net to a first through fourth metal layer.

18. The computer-readable storage medium of claim 14, wherein if the delay is less than one cycle of a clock, the method further comprises assigning the given net to a first group.

19. The computer-readable storage medium of claim 18, wherein if the delay is not less than one clock cycle the method further comprises:

calculating the delay for nets coupling the plurality of circuit blocks using a class two rule; and

if the delay in the given net is greater than the specified delay, inserting the virtual repeater in the given net to decrease the delay.

20. The computer-readable storage medium of claim 19, wherein the class two rule assigns the given net to a fifth through sixth metal layer.

21. The computer-readable storage medium of claim 19, wherein if the delay is less than one clock cycle, the method further comprises assigning the given net to a second group.

22. The computer-readable storage medium of claim 21, wherein if the delay is not less than one clock cycle the method further comprises:

calculating the delay for nets coupling the plurality of circuit blocks using a class three rule; and

if the delay in the given net is greater than the specified delay, inserting the virtual repeater in the given net to decrease the delay.

23. The computer-readable storage medium of claim 22, wherein the class three rule assigns the given net to a seventh through eighth metal layer.

24. The computer-readable storage medium of claim 22, wherein if the delay is less than one clock cycle, the method further comprises assigning the given net to a third group.

25. The computer-readable storage medium of claim 24, further comprising reporting the first group, the second group, and the third group, whereby reporting these groups provides a starting assignment of nets to metal layers for a subsequent routing process.

26. The computer-readable storage medium of claim 22, wherein if the delay is not less than one clock cycle, the method further comprises:

inserting a virtual flip-flop in the given net;

changing a delay criterion from greater than one clock cycle to greater than two clock cycles; and

repeating the method from calculating the delay for nets coupling the plurality of circuit blocks using the class one rule.

27. An apparatus for routing nets between cells in a circuit layout, comprising:

a receiving mechanism that is configured to receive a circuit design for circuit routing, wherein the circuit design includes a plurality of circuit blocks that have been placed at specific locations in the circuit layout;

a determining mechanism that is configured to determine estimated lengths for nets coupling the plurality of circuit blocks;

a calculating mechanism that is configured to calculate a delay for nets coupling the plurality of circuit blocks using a class one rule; and

an inserting mechanism that is configured to insert a virtual repeater in a given net to decrease the delay.

28. The apparatus of claim 27, wherein determining estimated lengths for nets coupling the plurality of circuit blocks involves computing a Steiner tree.

29. The apparatus of claim 27, wherein determining estimated lengths for the nets involves assigning nets to layers.

30. The apparatus of claim 27, wherein the class one rule assigns the given net to a first through fourth metal layer.

31. The apparatus of claim 27, further comprising an assigning mechanism that is configured to assign the given net to a first group.

32. The apparatus of claim 31, wherein:

the calculating mechanism is further configured to calculate the delay for nets coupling the plurality of circuit blocks using a class two rule; and

the inserting mechanism is further configured to insert the virtual repeater in the given net to decrease the delay.

33. The apparatus of claim 32, wherein the class two rule assigns the given net to a fifth through sixth metal layer.

34. The apparatus of claim 32, wherein the assigning mechanism is further configured to assign the given net to a second group.

35. The apparatus of claim 34, wherein:

the calculating mechanism is further configured to calculate the delay for nets coupling the plurality of circuit blocks using a class three rule; and

the inserting mechanism is further configured to insert the virtual repeater in the given net to decrease the delay.

36. The apparatus of claim 35, wherein the class three rule assigns the given net to a seventh through eighth metal layer.

37. The apparatus of claim 35, wherein the assigning mechanism is further configured to assign the given net to a third group.

38. The apparatus of claim 37, further comprising a reporting mechanism that is configured to report the first group, the second group, and the third group, whereby reporting these groups provides a starting assignment of nets to metal layers for a subsequent routing process.