Congestion estimation for programmable logic devices

• US 7,992,120 B1
• Filed: 11/26/2008
• Issued: 08/02/2011
• Est. Priority Date: 11/26/2008
• Status: Active Grant

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Wang, Bo, Wang, Xinyu
• Primary Examiner(s): Levin; Naum
• Application Number:
  US12/323,974
• Time in Patent Office: 979 Days
• Field of Search: 716/116, 716/128, 370/237
• US Class Current: 716/128
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/343 Logical level
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Various techniques are provided for estimating signal congestion in a programmable logic device (PLD). In one example, a computer-implemented method of estimating signal congestion in routing resources of a PLD is provided. The routing resources comprise a plurality of nodes and a plurality of wires which may be selectively interconnected to provide a plurality of signal paths through the routing resources of the PLD. The method includes determining a plurality of wire congestion values. Each of the wire congestion values identifies a relative likelihood of a corresponding one of the wires being used to provide the signal paths in comparison with the other wires. The method also includes selecting a region of the routing resources. The method further includes determining a congestion density estimate for the region using the wire congestion values associated with the wires of the region.

Claims

1. A computer-implemented method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise a plurality of nodes and a plurality of wires which may be selectively interconnected to provide a plurality of signal paths through the PLD, the method comprising:

determining in a computing device a plurality of wire congestion values, wherein each of the wire congestion values identifies a relative likelihood of a corresponding one of the wires being used to provide the signal paths in comparison with the other wires;

detecting in the computing device a selection of a first region of the routing resources;

determining in the computing device a first congestion density estimate for the first region using the wire congestion values associated with the wires of the first region;

detecting in the computing device a selection of a second region of the routing resources;

determining in the computing device a second congestion density estimate for the second region using the wire congestion values associated with the wires of the second region; and

comparing the first and second congestion density estimates to determine the relative congestion density of the first and second regions.

2. The method of claim 1, wherein the determining a congestion density estimate for a region comprises summing the wire congestion values associated with the wires of the region.

3. The method of claim 1, wherein the signal paths connect a plurality of source nodes to a plurality of destination nodes, wherein the determining wire congestion values comprises:

identifying a plurality of combinations of the source nodes and the destination nodes, wherein each combination includes at least one of the source nodes and at least one of the destination nodes;

for each combination, determining a plurality of probability values, wherein each of the probability values identifies a probability of a corresponding one of the wires being used to connect the source node to the destination node; and

for each wire, summing all of the probability values associated with the wire to determine the wire congestion value for the wire.

4. The method of claim 3, wherein the probability values are source/destination probability values, wherein the determining probability values comprises:

selecting a plurality of subsets of the routing resources, wherein each subset may be used to provide at least a portion of one of the signal paths from the source node to the destination node, wherein each subset comprises a root node, a trunk node, and a trunk wire connecting the root node to the trunk node;

determining a plurality of intermediate probability values, wherein each of the intermediate probability values identifies a probability of a corresponding one of the trunk wires being used by any of the signal paths that also include one or more other wires of the routing resources connected between the trunk wire and the source node; and

for each trunk wire, summing all intermediate probability values associated with the trunk wire to determine the source/destination probability value associated with the trunk wire.

5. The method of claim 4, wherein each of the subsets further comprises a branch wire connected to the trunk node, wherein the determining intermediate probability values further comprises:

determining a plurality of branch probability values, wherein each of the branch probability values identifies a probability of a corresponding one of the branch wires being used by any of the signal paths that also include the trunk node of the same subset; and

determining the intermediate probability values using the branch probability values.

6. The method of claim 3, wherein the source and destination nodes correspond to components of the PLD specified in a configuration of the PLD.

7. A non-transitory computer readable medium on which are stored computer readable instructions for performing the steps of claim 1.

8. A system comprising:

one or more processors, and

one or more memory devices adapted to store a plurality of computer readable instructions which when executed by the one or more processors are adapted to cause the system to perform a computer-implemented method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise a plurality of nodes and a plurality of wires which may be selectively interconnected to provide a plurality of signal paths through the routing resources of the PLD, the method comprising;

determining a plurality of wire congestion values, wherein each of the wire congestion values identifies a relative likelihood of a corresponding one of the wires being used to provide the signal paths in comparison with the other wires;

detecting a selection of a first region of the routing resources;

determining a first congestion density estimate for the first region using the wire congestion values associated with the wires of the first region;

detecting a selection of a second region of the routing resources;

determining in the computing device a second congestion density estimate for the second region using the wire congestion values associated with the wires of the second region; and

comparing the first and second congestion density estimates to determine the relative congestion density of the first and second regions.

9. The system of claim 8, wherein the determining a congestion density estimate for a region comprises summing the wire congestion values associated with the wires of the region.

10. The system of claim 8, wherein the signal paths connect a plurality of source nodes to a plurality of destination nodes, wherein the determining wire congestion values comprises:

identifying a plurality of combinations of the source nodes and the destination nodes, wherein each combination includes at least one of the source nodes and at least one of the destination nodes;

for each combination, determining a plurality of probability values, wherein each of the probability values identifies a probability of a corresponding one of the wires being used to connect the source node to the destination node; and

for each wire, summing all of the probability values associated with the wire to determine the wire congestion value for the wire.

11. The system of claim 10, wherein the probability values are source/destination probability values, wherein the determining probability values comprises:

selecting a plurality of subsets of the routing resources, wherein each subset may be used to provide at least a portion of one of the signal paths from the source node to the destination node, wherein each subset comprises a root node, a trunk node, and a trunk wire connecting the root node to the trunk node;

determining a plurality of intermediate probability values, wherein each of the intermediate probability values identifies a probability of a corresponding one of the trunk wires being used by any of the signal paths that also include one or more other wires of the routing resources connected between the trunk wire and the source node; and

for each trunk wire, summing all intermediate probability values associated with the trunk wire to determine the source/destination probability value associated with the trunk wire.

12. The system of claim 11, wherein each of the subsets further comprises a branch wire connected to the trunk node, wherein the determining intermediate probability values further comprises:

determining a plurality of branch probability values, wherein each of the branch probability values identifies a probability of a corresponding one of the branch wires being used by any of the signal paths that also include the trunk node of the same subset; and

determining the intermediate probability values using the branch probability values.

13. A non-transitory computer readable medium on which are stored computer readable instructions for performing in a computing device a method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise a plurality of nodes and a plurality of wires which may be selectively interconnected to provide a plurality of signal paths through the PLD, the method comprising

determining a plurality of wire congestion values, wherein each of the wire congestion values identifies a relative likelihood of a corresponding one of the wires being used to provide the signal paths in comparison with the other wires;

detecting a selection of a first region of the routing resources;

determining a first congestion density estimate for the first region using the wire congestion values associated with the wires of the first region;

detecting a selection of a second region of the routing resources;

determining a second congestion density estimate for the second region using the wire congestion values associated with the wires of the second region; and

comparing the first and second congestion density estimates.