Congestion estimation based on routing resources of programmable logic devices

• US 8,856,718 B1
• Filed: 12/17/2008
• Issued: 10/07/2014
• Est. Priority Date: 12/17/2008
• Status: Active Grant

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Zhao, Jun
• Primary Examiner(s): Thompson, A. M.
• Application Number:
  US12/337,502
• Time in Patent Office: 2,120 Days
• 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/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: H03K 19/17736 Structural details of routing resources
• CPC Class Codes: H05K 3/0005 for designing circuits by computer

Abstract

A computer-implemented method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources include configurable interface blocks (CIBs) and wires of different types supported by the CIBs. The method includes identifying, from a representation of a PLD stored within a computer system, components of the PLD to be connected in a configuration of the PLD. A CIB associated with an identified PLD component is then selected. A wire type supported by the selected CIB is also selected. The number of wires of the selected type needed at the selected CIB to implement the PLD configuration and the number of wires of the selected type provided by the CIB are calculated. Signal congestion at the selected CIB is estimated from at least the needed number of wires and the provided number of wires.

Claims

1. A computer readable storage medium storing computer readable instructions that when executed perform a method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise common interface blocks (CIBs) and wires of different types supported by the CIBs, the method comprising:

identifying, from a representation of a PLD stored within a computer system, components of the PLD to be connected in a configuration of the PLD;

selecting, within the computer system, a CIB associated with an identified PLD component;

selecting, within the computer system, a wire type supported by the selected CIB;

determining, within the computer system, a number of wires of the selected wire type needed at the selected CIB to implement the PLD configuration, a number of wires of the selected wire type already allocated at the CIB, and a provided number of wires of the selected wire type provided by the CIB; and

determining, within the computer system, a congestion index at the selected CIB for the selected wire type from at least the needed number of wires, the number of wires already allocated, and the provided number of wires.

2. The computer readable storage medium of claim 1, wherein the PLD components are arranged in a grid, and the wires of different types includes wires having lengths of at least zero, one, and two grid positions within the PLD.

3. The computer readable storage medium of claim 1, wherein the different types of wires includes wires of different lengths internal and external to the CIB.

4. The computer readable storage medium of claim 1, wherein determining a congestion index comprises calculating a congestion index value for the selected CIB by comparing the needed number of wires to the provided number of wires.

5. The computer readable storage medium of claim 1, wherein the selected wire type is a first type.

6. The computer readable storage medium of claim 1, wherein the selected CIB is a first CIB.

7. The computer readable storage medium of claim 1, wherein the selected wire type is a first wire type, the method further comprising:

calculating, within the computer system, a number of overflow connections associated with the selected CIB for the first wire type corresponding to a difference between a number of connections of the first wire type needed at the selected CIB to implement the PLD configuration and a number of connections of the first wire type provided by the selected CIB; and

substituting, within the computer system, a second wire type for the first wire type to support the number of overflow connections.

8. The computer readable storage medium of claim 1, wherein the number of connections of the selected wire type needed at the selected CIB includes connections of the selected wire type to support:

the signal paths that connect to one of the PLD components associated with the selected CIB; and

the signal paths that pass signals through the selected CIB to other PLD components associated with other CIBs.

9. A computer-implemented method of estimating signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise common interface blocks (CIBs) and wires of different types supported by the CIBs, the method comprising:

identifying, from a representation of a PLD stored within a computer system, components of the PLD to be connected in a configuration of the PLD;

selecting, within the computer system, a CIB associated with an identified PLD component;

selecting, within the computer system, a wire type supported by the selected CIB;

determining, within the computer system, a number of wires of the selected wire type needed at the selected CIB to implement the PLD configuration, a number of wires of the selected wire type already allocated at the CIB, and a provided number of wires of the selected wire type provided by the CIB; and

determining, within the computer system, a congestion index at the selected CIB for the selected wire type from at least the needed number of wires, the already allocated number of wires, and the provided number of wires.

10. The method of claim 9, wherein the PLD components are arranged in a grid, and the wires of different types includes wires having lengths of at least zero, one, and two grid positions within the PLD.

11. The method of claim 9, wherein the different types of wires includes wires of different lengths internal and external to the CIB.

12. The method of claim 9, wherein determining a congestion index comprises calculating a congestion index value for the selected CIB by comparing the needed number of wires to the provided number of wires.

13. The method of claim 9, wherein the selected wire type is a first type.

14. The method of claim 9, wherein the selected CIB is a first CIB.

15. A system comprising:

one or more processors; and

one or more memories storing a plurality of computer readable instructions that, when executed by the one or more processors, cause the system to estimate signal congestion in routing resources of a programmable logic device (PLD), wherein the routing resources comprise common interface blocks (CIBs) and a wires of different types supported by the CIBs, the system performing the following;

identifying, from a representation of a PLD stored, components of the PLD to be connected in a configuration of the PLD;

selecting a CIB associated with an identified PLD component;

selecting a wire type supported by the selected CIB;

determining a number of wires of the selected wire type needed at the selected CIB to implement the PLD configuration, a number of wires of the selected wire type already allocated at the CIB, and a provided number of wires of the selected wire type provided by the CIB; and

determining a congestion index at the selected CIB for the selected wire type from at least the needed number of wires, the already allocated number of wires, and the provided number of wires.

16. The system of claim 15, wherein the PLD components are arranged in a grid, and the wires of different types includes wires having lengths of at least zero, one, and two grid positions within the PLD.

17. The system of claim 15, wherein the different types of wires includes wires of different lengths internal and external to the CIB.

18. The system of claim 15, wherein determining a congestion index comprises calculating a congestion index value for the selected CIB by comparing the needed number of wires to the provided number of wires.

19. The system of claim 15, wherein the selected wire type is a first type.

20. The system of claim 15, wherein the selected CIB is a first CIB.