Skew-driven routing for networks

• US 7,516,437 B1
• Filed: 07/20/2006
• Issued: 04/07/2009
• Est. Priority Date: 07/20/2006
• Status: Active Grant

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Stern, Carl M., Kannan, Parivallal
• Primary Examiner(s): Dinh; Paul
• Assistant Examiner(s): Parihar; Suchin
• Application Number:
  US11/490,670
• Time in Patent Office: 992 Days
• Field of Search: 716/13, 716/6, 716/12
• US Class Current: 716/126
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A method of generating a low-skew network for a circuit design can include routing connections between a source and a plurality of loads of the network, determining a delay for at least one routed connection, and accepting the routed connections if the delay of each routed connection is within a skew tolerance range.

Claims

1. A method of generating a low-skew routing for a network of a circuit design comprising:

routing connections between a source and a plurality of loads of the network;

determining a delay for at least one routed connection; and

accepting the routed connections if the delay of each routed connection is within a skew tolerance range;

wherein routing connections further comprises selecting routing resources according to a base cost calculated for each routing resource selected for routing the connections between the source and the plurality of loads of the network, wherein the base cost for each routing resource comprises a delay from the source to the routing resource multiplied by a first tuning factor and an estimated delay from the routing resource to one of the plurality of loads multiplied by a second tuning factor, and a target delay specified as a maximum of lowest delay paths between the source and each of the plurality of loads of the network.

2. The method of claim 1, further comprising defining the skew tolerance range according to an amount by which propagation delays from the source to each of the plurality of loads of the network are permitted to vary and a target delay for the network.

3. The method of claim 2, further comprising if the delay for a routed connection of the network exceeds an upper bound of the skew tolerance range, increasing the target delay to be equal to the delay for that routed connection.

4. The method of claim 3, further comprising:

deleting all routed connections for the network; and

routing connections between the source and the plurality of loads of the network using the increased target delay to specify the skew tolerance range.

5. The method of claim 1, further comprising marking the routed network as non-skew optimized if the delay of at least one routed connection is less than a lower bound of the skew tolerance range and indicating that each routing path that exists for the at least one routed connection has a delay that is too small for the at least one routed connection to have a skew within the skew tolerance range.

6. The method of claim 1, further comprising indicating that the circuit design is not feasible if the delay of at least one routed connection is less than a lower bound of the skew tolerance range.

7. A machine readable storage, having stored thereon a computer program having a plurality of code sections, which when executed by a computer perform the following steps, the code comprising:

code for routing connections between a source and a plurality of loads of a network of a circuit design;

code for determining a delay for at least one routed connection; and

code for accepting the routed connections if the delay of each routed connection is within a skew tolerance range;

wherein the code for routing connections further comprises code for selecting routing resources according to a base cost calculated for each routing resource selected for routing the connections between the source and the plurality of loads of the network, wherein the base cost for each routing resource comprises a delay from the source to the routing resource multiplied by a first tuning factor and an estimated delay from the routing resource to one of the plurality of loads multiplied by a second tuning factor, and a target delay specified as a maximum of lowest delay paths between the source and each of the plurality of loads of the network.

8. The machine readable storage of claim 7, further comprising code for defining the skew tolerance range according to an amount by which propagation delays from the source to each of the plurality of loads of the network are permitted to vary and a target delay for the network.

9. The machine readable storage of claim 8, wherein the delay for at least one routed connection exceeds an upper bound of the skew tolerance range, the machine readable storage further comprising:

code for increasing the target delay to be equal to the delay;

code for deleting all routed connections for the network; and

code for routing connections of the network using the increased target delay to specify the skew tolerance range.

10. The machine readable storage of claim 7, wherein the delay of at least one routed connection is less than a lower bound of the skew tolerance range, the machine readable storage further comprising code for marking the routed network as non-skew optimized and for indicating that each routing path that exists for the at least one routed connection has a delay that is too small for the at least one routed connection to have a skew within the skew tolerance range.