Method and apparatus for detail routing using obstacle carving around terminals

• US 20030009736A1
• Filed: 07/26/2002
• Published: 01/09/2003
• Est. Priority Date: 12/28/1999
• Status: Active Grant

• Current Assignee: Gyorgy Suto
• Original Assignee: Gyorgy Suto
• Inventors: Suto, Gyorgy
• Granted Patent: US 6,957,407 B2
• Time in Patent Office: Days
• US Class Current: 716/8
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Detail routing using obstacle carving around terminals. A terminal in an integrated circuit layout object that is separated from an obstacle by less than a spacing specified by a design rule is identified. The obstacle is carved to reduce an area of the obstacle by an overlap between the obstacle and the terminal bloated by the spacing.

Claims

1. A method comprising:

identifying a terminal in an integrated circuit layout object that is separated from an obstacle by less than a spacing specified by a design rule; and

carving the obstacle to reduce an area of the obstacle by an overlap between the obstacle and the terminal bloated by the spacing.

2. The method of claim 1 further comprising:

bloating the terminal by the spacing,

intersecting the bloated terminal with the obstacle, and

adding an area of intersection between the bloated terminal and the obstacle to the terminal as a second-class citizen terminal.

3. The method of claim 2 further comprising:

identifying an area of overlap between the second-class citizen terminal and a second-class citizen terminal associated with a different net; and

subtracting the area of overlap from both second-class citizen terminals.

4. The method of claim 1 further comprising:

identifying a route for a wire to be coupled to the terminal such that the wire is spaced from the carved obstacle by at least the specified distance at all points along the wire.

5. The method of claim 2 wherein the terminal and the second-class citizen terminal correspond to a first net, the method further comprising:

identifying a route for a wire of the first net to be coupled to the terminal such that the wire is spaced from the carved obstacle and second-class citizen terminals of other nets by at least the specified distance at all points along the wire.

6. The method of claim 1 further comprising:

identifying a pre-existing wire to be coupled to another wire as an obstacle.

7. The method of claim 1 wherein identifying the terminal includes

bloating the terminal by the spacing;

and

identifying the terminal as a terminal in violation if the bloated terminal overlaps with the obstacle.

8. A method comprising:

identifying a wire to be routed, the wire corresponding to a first net; and

if a destination terminal for the wire is a terminal in violation, determining a route for the wire to be connected to the destination terminal such that the wire is separated at all points along the wire from obstacles and first- and second-class citizen terminals of other nets by at least a specified design rule spacing determined from a design rule associated with one of the obstacle or the wire.

9. The method of claim 8 further comprising:

constructing a detail routing model from input data,

wherein determining the route for the wire is performed using the detail routing model.

10. The method of claim 9 wherein constructing a detail routing model includes

receiving input data that specifies at least the destination terminal and an obstacle that overlaps with the destination terminal;

identifying the destination terminal as a terminal in violation; and

carving the obstacle to reduce an area of the obstacle by an overlap between the obstacle and the terminal bloated by the specified design rule spacing.

11. The method of claim 10 wherein constructing the model further comprises:

bloating the destination terminal by the specified design rule spacing,

intersecting the bloated terminal with the obstacle, and

adding an area of intersection between the bloated terminal and the obstacle to the destination terminal as a second-class citizen terminal.

12. The method of claim 11 further wherein constructing the detail model further comprises:

identifying an area of overlap between the second-class citizen terminal and a second-class citizen terminal of a different net; and

subtracting the area of overlap from both second-class citizen terminals.

13. The method of claim 9 wherein constructing the detail model comprises:

identifying a pre-existing wire as an obstacle.

15. The method of claim 14 further comprising:

identifying an area of the bloated first terminal beyond the first terminal as a second-class citizen terminal wherein the first terminal, the wire and the second-class citizen terminal are each associated with a first net, and

wherein the route for the wire is further determined such that the wire is also separated from second-class citizen terminals of other nets by at least the design rule spacing.

16. The method of claim 15 further comprising:

subtracting an area of overlap between second-class citizen terminals of different nets from the overlapping second-class citizen terminals.

17. The method of claim 14 further comprising:

identifying a pre-existing wire as an obstacle.

19. The method of claim 18 further comprising:

subtracting areas of intersection between second-class citizen terminals associated with different nets from the overlapping second-class citizen terminals.

14. A method comprising:

carving an obstacle to reduce its area by an amount equal to an overlap between the obstacle and a first terminal bloated by a design rule spacing; and

determining a route for a wire to be connected to the first terminal such that the wire is separated from the carved obstacle at all points along the wire by at least the design rule spacing.

18. A method comprising:

receiving input data to a detail router;

bloating each terminal indicated by the input data by a design rule spacing;

intersecting the bloated terminals with obstacles indicated by the input data;

adding an area of intersection between the bloated terminals and one or more obstacles to the terminals indicated by the input data, the added area being indicated as second-class citizen terminals; and

area-subtracting terminals indicated by the input data and second-class citizen terminals that overlap with one or more obstacles from the obstacles.

20. A detail router comprising:

a pre-processing module to carve obstacles indicated by input data to reduce an area of the obstacles by an overlap between the obstacles and one or more terminals in violation bloated by a design rule spacing; and

a search and route module to identify a route for a first wire of a first net to be coupled to a first terminal of the terminals in violation, the search and route module to identify the route such that the first wire is separated from obstacles at all points along the wire by at least the design rule spacing.

21. The detail router of claim 20 wherein the pre-processing module is further to identify an area of the bloated terminals beyond the terminals in violation as second-class citizen terminals, the terminals in violation and the second-class citizen terminals each corresponding to a particular net, and

wherein the search and route module is further to identify the route such that the first wire is also separated from second-class citizens corresponding to nets other than the first net by at least the design rule spacing.

22. The detail router of claim 20 wherein the pre-processing module is further to identify pre-existing wires as obstacles.

24. The computer-readable storage medium of claim 23 further storing instructions which, when executed cause a computer system to perform the method further comprising:

bloating the terminal by the spacing,

intersecting the bloated terminal with the obstacle, and

adding an area of intersection between the bloated terminal and the obstacle to the terminal as a second-class citizen terminal.

25. The computer-readable storage medium of claim 24 further storing instructions which, when executed cause a computer system to perform the method further comprising:

identifying an area of overlap between the second-class citizen terminal and a second-class citizen terminal associated with a different net; and

subtracting the area of overlap from both second-class citizen terminals.

26. The computer-readable storage medium of claim 23 further storing instructions which, when executed cause a computer system to perform the method further comprising:

identifying a route for a wire to be coupled to the terminal such that the wire is spaced from the carved obstacle by at least the specified distance at all points along the wire.

27. The computer-readable storage medium of claim 24 wherein the terminal and the second-class citizen terminal correspond to a first net, the computer-readable storage medium further storing instructions which, when executed cause a computer system to perform the method further comprising:

identifying a route for a wire of the first net to be coupled to the terminal such that the wire is spaced from the carved obstacle and second-class citizen terminals of other nets by at least the specified distance at all points along the wire.

29. The computer-readable storage medium of claim 28 further storing instructions which, when executed cause a computer system to perform the method further comprising:

constructing a detail routing model from input data,

wherein determining the route for the wire is performed using the detail routing model.

30. The computer-readable storage medium of claim 29 wherein constructing the detail routing model includes

receiving input data that specifies at least the destination terminal and an obstacle that overlaps with the destination terminal;

identifying the destination terminal as a terminal in violation; and

carving the obstacle to reduce an area of the obstacle by an overlap between the obstacle and the terminal bloated by the specified design rule spacing.

23. A computer-readable storage medium to store instructions which, when executed cause a computer system to perform a method comprising:

identifying a terminal in an integrated circuit layout object that is separated from an obstacle by less than a spacing specified by a design rule; and

carving the obstacle to reduce an area of the obstacle by an overlap between the obstacle and the terminal bloated by the spacing.

28. A computer-readable storage medium to store instructions which, when executed cause a computer system to perform a method comprising:

identifying a wire to be routed, the wire corresponding to a first net; and

if a destination terminal for the wire is a terminal in violation, determining a route for the wire to be connected to the destination terminal such that the wire is separated at all points along the wire from obstacles and first- and second-class citizen terminals of other nets by at least a specified design rule spacing determined from a design rule associated with one of the obstacle or the wire.