Integrated circuit signal routing using resource cost assignment and costing data

• US 7,107,563 B1
• Filed: 06/19/2003
• Issued: 09/12/2006
• Est. Priority Date: 06/20/2002
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Kong, Raymond
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US10/600,846
• Time in Patent Office: 1,181 Days
• Field of Search: 716 11- 17
• US Class Current: 716/128
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Method, apparatus, and computer readable medium for determining signal routing cost within an integrated circuit is described. In an example, the integrated circuit is divided into topology units and includes routing resources. A respective span is determined in terms of one or more of the topology units for each of the routing resources. A cost value is assigned to each of the routing resources using the respective span associated therewith. A routing resource is selected from the routing resources. At least one distance between the routing resource and at least one other of the routing resources is calculated. A future cost value for the at least one distance is computed using the cost value assigned to the routing resource.

Claims

1. A method for determining signal routing cost for an integrated circuit, the integrated circuit having topology units and routing resources, the method comprising:

determining a respective span in terms of one or more of the topology units for each of the routing resources, wherein each of the topology units is substantially same to the other topology units;

assigning a cost value to each of the routing resources using the respective span associated therewith;

selecting a routing resource from the routing resources;

calculating at least one distance between the routing resource and at least one other of the routing resources; and

computing a future cost value for the at least one distance using the cost value assigned to the routing resource.

2. The method of claim 1, further comprising storing the future cost value for the at least one distance in a two-dimensional table indexed by a vertical distance and a horizontal distance.

3. The method of claim 1, wherein the routing resource is located at one corner of the integrated circuit.

4. The method of claim 3, wherein the integrated circuit is a programmable logic device and the topology units are associated with programmable logic blocks within the programmable logic device.

5. The method of claim 1, wherein the calculating and the computing comprises:

determining a cumulative routing cost of the at least one other of the routing resources;

obtaining a distance calculated between the first routing resource and the at least one other of the remaining routing resources; and

setting the future cost value equal to the cumulative routing cost if there is no existing future cost value corresponding to the distance or if the cumulative routing cost is less than an existing future cost value corresponding to the distance.

6. The method of claim 5, wherein the cumulative routing cost of the at least one other of the remaining routing resources includes a cumulative routing cost of the routing resource and the cost assigned to the at least one other of the remaining routing resources.

7. The method of claim 1, wherein the determining comprises identifying a number of topology units the routing resource intersects in at least one of a vertical direction and a horizontal direction.

8. A method of routing a signal within an integrated circuit, the integrated circuit having topology units and routing resources, the method comprising:

determining a respective span in terms of one or more of the topology units for each of the routing resources, wherein each of the topology units is substantially same to the other topology units;

assigning a cost value to each of the routing resources using the respective span associated therewith;

selecting a routing resource from the routing resources;

calculating at least one distance between the routing resource and at least one other of the routing resources;

computing a future cost value for the at least one distance using the cost value assigned to the routing resource; and

determining a signal path from a source routing resource to a destination routing resource using the future cost value computed for the distance between the source routing resource and the destination routing resource.

9. The method of claim 8, further comprising repeating the determining a signal path for additional pairs of source and destination routing resources.

10. The method of claim 8, further comprising storing the future cost value for the at least one distance in a two-dimensional table indexed by a vertical distance and a horizontal distance.

11. The method of claim 8, wherein the determining a span comprises, for each routing resource, identifying a number of topology units the routing resource intersects in at least one of a vertical direction and a horizontal direction.

12. A computer readable medium having stored thereon instructions that, when executed by a processor, cause the processor to perform a method of determining signal routing cost within an integrated circuit, the integrated circuit having topology units and routing resources, the method comprising:

determining a respective span in terms of one or more of the topology units for each of the routing resources, wherein each of the topology units is substantially same to the other topology units;

assigning a cost value to each of the routing resources using the respective span associated therewith;

selecting a routing resource from the routing resources;

calculating at least one distance between the routing resource and at least one other of the routing resources; and

computing a future cost value for the at least one distance using the cost value assigned to the routing resource.

13. An apparatus for determining signal routing cost within an integrated circuit, the integrated circuit being divided into topology units and having routing resources, the apparatus comprising:

means for assigning a cost value to each of the routing resources using a respective span associated therewith, the span being measured in terms of one or more of the topology units, wherein each of the topology units is substantially same to the other topology units;

means for calculating at least one distance between a first routing resource and at least one other of the routing resources; and

means for computing a future cost value for the at least one distance using the cost value assigned to the first routing resource.

14. A system for determining signal routing cost within an integrated circuit, the system comprising:

a processing unit having access to one or more storage devices;

at least a portion of the one or more storage devices having topology data and routing resource data associated with the integrated circuit; and

at least another portion of the one or more storage devices having a program product configured to;

select routing resources from the routing resource data;

determine a respective span in terms of one or more topology units of the topology data for each of the routing resources, wherein each of the topology units is substantially same to the other topology units;

assign a cost value to each of the routing resources using the respective span associated therewith;

select a routing resource from the routing resources;

calculate at least one distance between the routing resource and at least one other of the routing resources; and

compute a future cost value for the at least one distance using the cost value assigned to the routing resource.

15. A system for routing a signal within an integrated circuit, the integrated circuit having topology units and routing resources, the system comprising:

a router initialization section for assigning a cost value to each of the routing resources using a respective span associated therewith, the span being measured in terms of one or more of the topology units, for calculating at least one distance between a first routing resource and at least one other of the routing resources, and for computing a future cost value for the at least one distance using the cost value assigned to the first routing resource, wherein each of the topology units is substantially same to the other topology units; and

a router section for determining a signal path from a source routing resource to a destination routing resource using the future cost computed for the distance between the source routing resource and the destination routing resource.

16. A method of determining signal routing cost for an integrated circuit having blocks of circuitry and having routing resources for interconnecting at least a portion of the blocks of circuitry, the method comprising:

identifying interconnects for the routing resources;

describing each span of the interconnects in terms of circuitry blocks in association with the blocks of circuitry, wherein the circuitry blocks is substantially same topology;

assigning a routing cost to a respective one of the interconnects until each of the interconnects has been assigned a respective cost of routing, wherein the routing cost is for each of the interconnects is responsive to the circuitry blocks respectively used to describe the interconnects;

selecting each of the routing resources;

determining each distance between a routing resource selected and the routing resources remaining to provide distances; and

calculating a future cost for each of the distances responsive to the routing cost associated therewith.

17. The method of claim 16, further comprising storing the future cost for each of the distances in a two-dimensional table indexed by vertical and horizontal distances.

18. The method of claim 16, wherein the routing resource is located at one corner of the integrated circuit.

19. The method of claim 16, wherein the integrated circuit is a programmable logic device.

20. The method of claim 19, wherein the routing resources are associated with programmable logic blocks within the programmable logic device.