Congestion-driven placement systems and methods for programmable logic devices

• US 8,112,731 B1
• Filed: 11/24/2008
• Issued: 02/07/2012
• Est. Priority Date: 11/24/2008
• Status: Active Grant

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Shen, Yinan, Wang, Bo, Chen, Chih-Chung
• Primary Examiner(s): Chiang, Jack
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US12/277,217
• Time in Patent Office: 1,170 Days
• Field of Search: 716/116
• US Class Current: 716/116
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

Techniques are provided for reducing signal congestion in programmable logic devices (PLDs). In one example, a computer-implemented method of reducing signal congestion in a configuration of a PLD includes mapping a plurality of circuit components of a circuit design to a plurality of components of the PLD, wherein each of the mapped PLD components is associated with one of a plurality of regions of the PLD and with one or more unique signal paths entering the PLD region. The method also includes determining a cost value for each PLD region based at least in part on the number of unique signal paths entering the PLD region from other PLD regions. The method also includes selecting one of the PLD components to move from a first one of the PLD regions to a second one of the PLD regions. The method also includes updating the cost values associated with the first and second PLD regions based on a change in the number of unique signal paths entering the first and second PLD regions. The method also includes selectively accepting or rejecting the move based at least in part on the updated cost values.

Claims

1. A computer-implemented method of reducing signal congestion in configuration data that implements a circuit design in a programmable logic device (PLD), the method comprising:

mapping in a computer a plurality of circuit components of the circuit design to a plurality of components of the PLD;

placing in the computer the plurality of PLD components in the PLD, wherein each of the placed PLD components is associated with one of a plurality of regions of the PLD and with one or more unique signal paths entering the PLD region;

determining in the computer a cost value for each PLD region associated with a placed PLD component based at least in part on the number of unique signal paths entering the PLD region from other PLD regions, wherein the cost value reflects the amount of signal congestion in the PLD region;

selecting in the computer one of the PLD components to move from a first one of the PLD regions to a second one of the PLD regions;

updating in the computer the cost values associated with the first and second PLD regions based on a change in the number of unique signal paths entering the first and second PLD regions; and

selectively accepting or rejecting in the computer the move based at least in part on the updated cost values.

2. The method of claim 1, wherein the determining in the computer a cost value comprises assigning a cost value to each PLD region having a number of unique signal paths that exceeds a signal path limit value associated with the PLD region.

3. The method of claim 1, further comprising determining in the computer a congestion density estimate associated with each PLD region, wherein the cost value for each PLD region is further based on the congestion density estimate associated with the PLD region.

4. The method of claim 3, wherein the determining in the computer a congestion density estimate associated with each PLD region comprises:

identifying in the computer a plurality of signal sources and a plurality of signal destinations associated with the PLD components;

for each signal source, identifying in the computer a trunk of connected wires extending from the signal source toward one or more of the signal destinations;

for each signal destination, identifying in the computer a branch of connected wires extending from the trunk to the signal destination;

identifying in the computer a plurality of bounding boxes surrounding sets of the signal sources and signal destinations;

determining in the computer a congestion density estimate associated with each bounding box; and

determining in the computer the congestion density estimate associated with each PLD region using the congestion density estimates associated with bounding boxes associated with each PLD region.

5. The method of claim 4, wherein the determining in the computer a congestion density estimate associated with each bounding box comprises:

determining in the computer a total wire length of the trunk and the one or more branches of the bounding box;

determining in the computer an area of the bounding box; and

dividing in the computer the total wire length by the area to obtain the congestion density estimate associated with the bounding box.

6. The method of claim 1, further comprising repeating the selecting, updating, and selectively accepting or rejecting for a plurality of different PLD components and a plurality of different PLD regions.

7. The method of claim 6, further comprising updating the congestion density estimates, wherein the cost values are updated more frequently than the congestion density estimates.

8. The method of claim 1, wherein the determining, selecting, updating, and selectively accepting or rejecting are part of a simulated annealing process.

9. The method of claim 8, further comprising repeating the selecting, updating, and selectively accepting or rejecting for a plurality of different PLD components and a plurality of different PLD regions until a temperature of the simulated annealing process reaches a minimum value.

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

11. A system comprising:

one or more processors; and

one or more memories 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 method of reducing signal congestion in a configuration of a programmable logic device (PLD), the method comprising;

mapping a plurality of circuit components of a circuit design to a plurality of components of the PLD,

placing the plurality of PLD components in the PLD, wherein each of the placed PLD components is associated with one of a plurality of regions of the PLD and with one or more unique signal paths entering the PLD region,

determining a cost value for each PLD region associated with a placed PLD component based at least in part on the number of unique signal paths entering the PLD region from other PLD regions, wherein the cost value reflects the amount of signal congestion in the PLD region,

selecting one of the PLD components to move from a first one of the PLD regions to a second one of the PLD regions,

updating the cost values associated with the first and second PLD regions based on a change in the number of unique signal paths entering the first and second PLD regions, and

selectively accepting or rejecting the move based at least in part on the updated cost values.

12. The system of claim 11, wherein the determining a cost value comprises assigning a cost value to each PLD region having a number of signal paths that exceeds a signal path limit value associated with the PLD region.

13. The system of claim 11, further comprising determining a congestion density estimate associated with each PLD region, wherein the cost value for each PLD region is further based on the congestion density estimate associated with the PLD region.

14. The system of claim 13, wherein the determining a congestion density estimate associated with each PLD region comprises:

identifying a plurality of signal sources and a plurality of signal destinations associated with the PLD components;

for each signal source, identifying a trunk of connected wires extending from the signal source toward one or more of the signal destinations;

for each signal destination, identifying a branch of connected wires extending from the trunk to the signal destination;

identifying a plurality of bounding boxes surrounding sets of the signal sources and signal destinations;

determining a congestion density estimate associated with each bounding box; and

determining the congestion density estimate associated with each PLD region using the congestion density estimates associated with bounding boxes associated with each PLD region.

15. The system of claim 14, wherein the determining a congestion density estimate associated with each bounding box comprises:

determining a total wire length of the trunk and the one or more branches of the bounding box;

determining an area of the bounding box; and

dividing the total wire length by the area to obtain the congestion density estimate associated with the bounding box.

16. The system of claim 11, further comprising repeating the selecting, updating, and selectively accepting or rejecting for a plurality of different PLD components and a plurality of different PLD regions.

17. The system of claim 16, further comprising updating the congestion density estimates, wherein the cost values are updated more frequently than the congestion density estimates.

18. The system of claim 11, wherein the determining, selecting, updating, and selectively accepting or rejecting are part of a simulated annealing process.

19. The system of claim 18, further comprising repeating the selecting, updating, and selectively accepting or rejecting for a plurality of different PLD components and a plurality of different PLD regions until a temperature of the simulated annealing process reaches a minimum value.

20. A system for reducing signal congestion in a configuration of a programmable logic device (PLD), the system comprising:

means for mapping a plurality of circuit components of a circuit design to a plurality of components of the PLD;

means for placing the plurality of PLD components in the PLD, wherein each of the placed PLD components is associated with one of a plurality of regions of the PLD and with one or more unique signal paths entering the PLD region;

means for determining a cost value for each PLD region associated with a placed PLD component based at least in part on the number of unique signal paths entering the PLD region from other PLD regions, wherein the cost value reflects the amount of signal congestion in the PLD region;

means for selecting one of the PLD components to move from a first one of the PLD regions to a second one of the PLO regions;

means for updating the cost values associated with the first and second PLD regions based on a change in the number of unique signal paths entering the first and second PLD regions; and

means for selectively accepting or rejecting the move based at least in part on the updated cost values.