Method and apparatus for performing geometric routing

• US 6,892,371 B1
• Filed: 08/28/2002
• Issued: 05/10/2005
• Est. Priority Date: 01/22/2002
• Status: Active Grant

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Jacques, Etienne
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): LEVIN, NAUM B
• Application Number:
  US10/230,504
• Time in Patent Office: 986 Days
• Field of Search: 716 7- 14, 257/401
• 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 for generating a route for a net in an integrated circuit (“IC”) layout. The method receives a previously defined route. From the received route, it generates several constraining points for specifying a geometric route that is based on a particular wiring model. The method then uses the constraining points to generate a geometric route that traverses diagonal and Manhattan directions.

Claims

1. A method of generating a geometric route for a net in an integrated circuit (“

IC”

) layout, the method comprising;

a) receiving previously defined route for the net;

b) from the received route, generating a plurality of constraining points in the layout for generating a the geometric route that is based on a particular wiring model; and

c) using the constraining points in the layout to generate the geometric route, wherein the geometric route traverses diagonal and Manhattan directions and wherein generating the plurality of constraining points comprises;

identifying path defining edges that the previously defined route intersects; and

identifying constraining points that specify segments of path defining edges that the geometric route intersects.

2. The method of claim 1, wherein the layout has multiple layers, wherein the geometric route traverses diagonal and Manhattan directions on the same layer of the layout.

3. The method of claim 1 further comprising generating a topological route that connects routable elements of the net, wherein the topological route is the previously defined route.

4. The method of claim 3, wherein the topological route includes at least one topological path that begins and ends at two vertices, wherein generating the constraining points further comprises:

using the constraining points to identify a shortest geometric path that connects the two vertices while using paths specified by the wiring model.

5. The method of claim 4, wherein identifying constraining points comprises defining the constraining points so that the boundary of geometric paths using the constraining points will be on a manufacturing grid used to manufacture IC'"'"'s according to the layout.

6. The method of claim 4, wherein identifying constraining points comprises defining the constraining points so that the center line of geometric paths using the constraining points will be on a manufacturing grid used to manufacture IC'"'"'s according to the layout.

7. The method of claim 4,

wherein the topological path is on a particular layer of the layout,

wherein the particular layer has at least two preferred wiring directions,

wherein generating constraining points further comprises:

for each preferred wiring direction

defining a plurality of path defining edges,

identifying path defining edges that the topological path intersects;

identifying constraining points that specify segments of path defining edges that the geometric route can intersect;

identifying a shortest geometric path based on the constraining points;

the method further comprising;

merging the identified shortest geometric paths to obtain a final geometric path between the two vertices.

8. The method of claim 3 further comprising specifying coordinates for points that represent the topological route before identifying path defining edges that the topological route intersects.

9. The method of claim 1, wherein the layout represents the design of a portion of a single IC chip.

10. The method of claim 1, wherein the layout represents the design of an entire IC chip.

11. A computer readable medium storing a computer program for generating a geometric route for a net in an integrated circuit (“

IC”

) layout, the computer program comprising instructions for;

a) receiving a previously defined route for the net;

b) from the received route, generating a plurality of constraining points in the layout for generating the geometric route that is based on a particular wiring model; and

c) using the constraining points in the layout to generate the geometric route, wherein the geometric route traverses diagonal and Manhattan directions and

wherein generating the plurality of constraining points comprises;

identifying path defining edges that the previously defined route intersects; and

identifying constraining points that specify segments of path defining edges that the geometric route intersects.

12. The computer readable medium of claim 11, wherein the layout has multiple layers, wherein the geometric route traverses diagonal and Manhattan directions on the same layer of the layout.

13. The computer readable medium of claim 11, wherein the computer program further comprises instructions for generating a topological route that connects routable elements of the net, wherein the topological route is the previously defined route.

14. The computer readable medium of claim 13, wherein the topological route includes at least one topological path that begins and ends at two vertices, wherein the instructions for generating the constraining points further comprise instructions for:

using the constraining points to identify a shortest geometric path that connects the two vertices while using paths specified by the wiring model.

15. The computer readable medium of claim 14, wherein the instructions for identifying constraining points comprise instructions for defining the constraining points so that the boundary of geometric paths using the constraining points will be on a manufacturing grid used to manufacture IC'"'"'s according to the layout.

16. The computer readable medium of claim 14, wherein instructions for identifying constraining points comprise instructions for defining the constraining points so that the center line of geometric paths using the constraining points will be on a manufacturing grid used to manufacture IC'"'"'s according to the layout.

17. The computer readable medium of claim 14,

wherein the topological path is on a particular layer of the layout,

wherein the particular layer has at least two preferred wiring directions,

wherein the instructions for generating constraining points further comprises instructions for:

for each preferred wiring direction

defining a plurality of path defining edges,

identifying path defining edges that the topological path intersects;

identifying constraining points that specify segments of path defining edges that the geometric route can intersect;

identifying a shortest geometric path based on the constraining points;

the computer program further comprising instructions for;

merging the identified shortest geometric paths to obtain a final geometric path between the two vertices.

18. The computer readable medium of claim 14 further comprising instructions for specifying coordinates for points that represent the topological route before identifying path defining edges that the topological route intersects.