Method and apparatus for accurate crosspoint allocation in VLSI area routing

• US 6,519,751 B2
• Filed: 03/31/2000
• Issued: 02/11/2003
• Est. Priority Date: 03/31/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Huang, May, Sriram, Mysore
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/539,978
• Publication Number:
  US 20020170029A1
• Time in Patent Office: 1,047 Days
• Field of Search: 716/1-21, 703/2
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

In one embodiment the invention is a method. The method includes finding costs to route a net to a set of crosspoints on a boundary. The method also includes propagating the costs to a succeeding set of nodes.

Claims

1. A method comprising:

defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal;

selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary;

selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary;

repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached;

for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and

identifying a signal route through the selected lowest-cost nodes.

2. The method of claim 1, wherein the cost of a route depends on a distance the route covers.

3. The method of claim 1, further comprising:

defining valid crosspoints as crosspoints on either side of where a previously routed signal crosses a boundary.

4. The method of claim 3, further comprising:

further defining, on a boundary adjacent to a terminator node, valid crosspoints as crosspoints limited to an area one design-rule width less than the area of the terminator node, within an area leading directly to the terminator node.

5. The method of claim 1, wherein the lowest-cost route is a route including a group of horizontal and vertical routing segments.

6. The method of claim 1, wherein the lowest-cost node is a terminator node.

7. The method of claim 1, further comprising:

defining valid crosspoints as crosspoints free from shadows of obstructions.

8. The method of claim 1, wherein the cost of a route between nodes of successive boundaries is increased if the route is routed around an obstruction.

9. The method of claim 1, wherein the cost of a route through a particular area is dependent on the presence of pre-routed signals that have already been routed through the same particular area.

10. The method of claim 9, wherein the cost of a route which creates a L-overlap configuration with the pre-routed signal is increased.

11. The method of claim 9, wherein the cost of a route which creates an X-overlap configuration with the pre-routed signal is increased.

12. The method of claim 1, wherein the cost of a route is dependent on the type of signal to be routed.

13. A machine-readable medium embodying instructions which, when executed by a machine, cause a processor to perform a method comprising:

defining a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of successive boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal;

selecting from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary;

selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary;

repeating the selecting from a successive boundary for each successive boundary until a successive boundary of the last area is reached;

for each preceding boundary having more than one lowest-cost node, changing, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from the lowest-cost node of the successive boundary to the preceding boundary; and

identifying a signal route through the selected lowest-cost nodes.

14. The machine-readable medium of claim 13, wherein the cost of a route is dependent on a distance the route covers.

15. The machine-readable medium of claim 13 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising:

defining valid crosspoints as crosspoints on either side of where a previously routed signal crosses a boundary.

16. The machine-readable medium of claim 15 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising:

further defining, on a boundary adjacent to a terminator node, valid crosspoints as crosspoints limited to an area one design-rule width less than the area of the terminator node, within an area leading directly to the terminator node.

17. The machine-readable medium of claim 13, wherein the lowest-cost route is a route including a group of horizontal and vertical routing segments.

18. The machine-readable medium of claim 13, wherein the lowest-cost node is a terminator node.

19. The machine-readable medium of claim 13 further embodying instructions which, when executed by a processor, cause the processor to perform the method further comprising:

defining valid crosspoints as crosspoints free from shadows of obstructions.

20. The machine-readable medium of claim 13, wherein the cost of a route between nodes of successive boundaries is increased if the route is routed around an obstruction.

21. The machine-readable medium of claim 13, wherein the cost of a route is dependent on the presence of pre-routed signals that have already been routed through a corresponding area.

22. The machine-readable medium of claim 21, wherein the cost of a route which creates a L-overlap configuration with the pre-routed signal is increased.

23. The machine-readable medium of claim 21, wherein the cost of a route which creates an X-overlap configuration with the pre-routed signal is increased.

24. The machine-readable medium of claim 13, wherein the cost of a route is dependent on the type of signal to be routed.

25. A system comprising:

a processor;

a memory coupled with the processor;

an input device coupled with the processor; and

wherein

the processor to define a group of contiguous areas of an integrated circuit separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of a signal to be routed on the integrated circuit and a last area including a second terminator node of the signal;

the processor further to select from a first boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary;

the processor further to select from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary;

the processor further to repeat the selection from a successive boundary for each successive boundary until a successive boundary of the last area is reached;

the processor further to, for each preceding boundary having more than one lowest-cost node, change the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and

the processor to identify a signal route through the selected lowest-cost nodes.

26. An apparatus comprising:

means for defining a group of contiguous areas being separated by successive boundaries, each boundary having one or more nodes thereon, and routes between nodes of different boundaries having costs, a first area including a first terminator node of the signal and a last area including a second terminator node of the signal;

means for selecting from a first boundary-a lowest-cost node defined by a valid crosspoint of a lowest-cost route between the first terminator and the first boundary;

for each successive boundary, means for selecting from a successive boundary a lowest-cost node defined by a valid crosspoint of a lowest-cost route between a previous lowest-cost node and the successive boundary;

means for changing, for each preceding boundary having more than one lowest-cost node, if necessary, the selected lowest-cost node to the lowest-cost node defined by a valid crosspoint of a lowest-cost route from a successive boundary to the preceding boundary; and

means for identifying a signal route through the selected lowest-cost nodes.