Multi-priority placement for configuring programmable logic devices

• US 8,181,139 B1
• Filed: 12/22/2008
• Issued: 05/15/2012
• Est. Priority Date: 12/22/2008
• Status: Active Grant

• Current Assignee: Lattice Semiconductor Corporation
• Original Assignee: Lattice Semiconductor Corporation
• Inventors: Chen, Xiaotao, Yi, Yanhua, Zhao, Jun, Ting, Eric, Xu, Ruofan
• Primary Examiner(s): Doan, Nghia
• Assistant Examiner(s): Lee, Eric
• Application Number:
  US12/341,929
• Time in Patent Office: 1,240 Days
• Field of Search: 716/116, 716/121, 716/128
• US Class Current: 716/121
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In one embodiment of the invention, a computer-implemented method of configuring a programmable logic device (PLD) includes placing logical functions within logical resources of the PLD to implement a desired netlist; swapping the logical function of at least one logical resource with the logical function of at least one other logical resource within the PLD; and evaluating whether to accept or reject the swap using a simulated annealing process that calculates at least three cost function values based upon routing priority groups, timing priority groups, and a timing critical group.

Claims

1. A computer-implemented method of configuring a programmable logic device (PLD), the method comprising:

based on an initial mapping into the PLD of a netlist, performing a global routing analysis of all netlist connections;

based on the analysis, assigning to each netlist connection a routing score determined by the connection'"'"'s routing resource usage;

categorizing the netlist connections into at least two routing priority groups based on each connection'"'"'s routing score;

calculating a slack-to-target ratio for each netlist connection, wherein the ratio=(estimated delay−

target delay)/target delay;

categorizing the netlist connections into at least two timing priority groups based on each connection'"'"'s slack-to-target ratio;

categorizing a certain percentage of the highest slack-to-target ratios into a timing critical group;

swapping the logical function of at least one logical resource with the logical function of at least one other logical resource within the PLD; and

calculating, by a computer, three cost function values in parallel based on the routing priority groups, the timing priority groups, and the timing critical group, respectively; and

evaluating whether to accept or reject the swap using a simulated annealing process and at least the three cost function values.

2. The method of claim 1, wherein the cost function value based on the timing critical group has a higher priority than the first cost function value based on the timing priority groups, and the cost function value based on the timing priority groups has a higher priority than the cost function value based on the routing priority groups.

3. The method of claim 1 including, after evaluating the at least three cost function values, performing another swapping of at least one logical resource and evaluating whether to accept or reject the other swap before again performing the categorizing steps of the method.

4. The method of claim 3 including, after a pre-determined number of swaps, again performing the categorizing steps of the method.

5. The method of claim 1, wherein the PLD is a field programmable logic array (FPGA) and the logical resources include a plurality of logic blocks.

6. The method of claim 1, wherein the routing resources comprise row routing resources and column routing resources.

7. A non-transitory computer readable medium on which are stored computer readable instructions for performing the following:

based on an initial mapping into a programmable logic device (PLD) of a netlist, performing a global routing analysis of all netlist connections;

based on the analysis, assigning to each netlist connection a routing score determined by the connection'"'"'s routing resource usage;

categorizing the netlist connections into at least two routing priority groups based on each connection'"'"'s routing score;

calculating a slack-to-target ratio for each netlist connection, wherein the ratio=(estimated delay−

target delay)/target delay;

categorizing the netlist connections into at least two timing priority groups based on each connection'"'"'s slack-to-target ratio;

categorizing a certain percentage of the highest slack-to-target ratios into a timing critical group;

swapping the logical function of at least one logical resource with the logical function of at least one other logical resource within the PLD; and

calculating three cost function values in parallel based on the routing priority groups, the timing priority groups, and the timing critical group, respectively; and

evaluating whether to accept or reject the swap using a simulated annealing process and at least the three cost function values.

8. The computer readable medium of claim 7, wherein the cost function value based on the timing critical group has a higher priority than the first cost function value based on the timing priority groups, and the cost function value based on the timing priority groups has a higher priority than the cost function value based on the routing priority groups.

9. The computer readable medium of claim 7 including, after evaluating the at least three cost function values, performing another swapping of at least one logical resource and evaluating whether to accept or reject the other swap before again performing the categorizing steps of the method.

10. The computer readable medium of claim 9 including, after a pre-determined number of swaps, again performing the categorizing steps of the method.