Template-based simulated annealing move-set that improves FPGA architectural feature utilization

• US 6,185,724 B1
• Filed: 12/02/1997
• Issued: 02/06/2001
• Est. Priority Date: 12/02/1997
• Status: Expired due to Term

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Ochotta, Emil S.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US08/982,847
• Time in Patent Office: 1,162 Days
• Field of Search: 395/500.02-500.19, 716/1-21
• US Class Current: 716/123
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A modification to the available simulated annealing algorithm is provided to better utilize direct connects and other architecture-specific features of a Field Programmable Gate Array. A preferred embodiment comprises adding a template-based move to the SA move-set that recognizes a specific pattern or template in the user'"'"'s design after mapping, and arranges the components into the optimal configuration for the specific template discovered. The present invention increases the intelligence of the SA move-set by selectively supplementing the random moves in the move-set with moves that produce locally good solutions.

Claims

1. A method of allocating a plurality of integrated circuit device elements to implement a circuit design in a programmable device having a localized routing structure, each such element having a position on the device, the method comprising the steps of:

a) mapping the design into a plurality of blocks, each of the blocks corresponding to a single element on the device;

b) placing the blocks according to an iterative algorithm; and

c) during said placing step, scanning the design for a plurality of design elements that can be advantageously interconnected using the localized routing structure, and upon locating such a plurality of design elements, altering the placement of the blocks in a non-random fashion to accommodate the localized routing structure.

2. The method of claim 1 further comprising the steps of:

d) comparing the altered placement of the blocks to a pre-altered placement of the blocks; and

e) based on the results of comparing the altered placement of the blocks to the pre-altered placement of the blocks, canceling the altered placement.

3. A method of allocating a plurality of integrated circuit device elements to implement a circuit design in a programmable device, each such element having a position on the device, the method comprising the steps of:

a) mapping the design into a plurality of blocks, each of the blocks corresponding to a single element on the device;

b) placing the blocks according to an iterative algorithm; and

c) during said placing step, scanning the design for a plurality of design elements having a predetermined correlation with one another, and upon locating such a plurality of design elements, altering the placement of the blocks in a non-random fashion to accommodate the predetermined correlation in the implemented circuit,

wherein in step b) the iterative algorithm is simulated annealing.

4. The method of claim 3 wherein the design is scanned for a plurality of design elements having a predetermined correlation with one another at the beginning of the simulated annealing process.

5. A method of allocating a plurality of integrated circuit device elements to implement a circuit design in a programmable device having a localized routing structure, each such element having a position on the device, the method comprising the steps of:

a) segmenting the design into a plurality of blocks, each of said blocks corresponding to a single element on the device;

b) placing said blocks among said elements on the device;

c) randomly swapping said blocks to improve an estimated efficiency of an implementation resulting from said placement; and

d) scanning the design for a plurality of design elements that can be advantageously interconnected using the localized routing structure, and upon locating said plurality of design elements, non-randomly altering the placement of said blocks to accommodate said localized routing structure.

6. A method of re-allocating a plurality of components previously allocated to logic blocks in an FPGA design, the FPGA having a localized routing structure, the method comprising the steps of:

a) studying the design to determine where a template can be applied in order to take advantage of the localized routing structure;

b) selecting one such template;

c) randomly selecting a logic block having a component assigned to it to participate in the selected template;

d) identifying other components that participate in the selected template;

e) determining the current location of the other components participating in the selected template; and

f) moving the components participating in the selected template in a non-random fashion, the moving resulting in a configuration matching the configuration of the template.

7. The method of claim 6, wherein step f) further comprises exchanging at least one component participating in the selected template with another component not participating in the template, thereby making room for the participating component.

8. A method of iteratively placing a plurality of components from a logic circuit into a programmable device, the programmable device comprising an array of logic blocks, each component including logic that can be implemented in one logic block, each component being assigned to one logic block in the array, thereby creating an initial placement, the method comprising;

performing a random iteration, the random iteration comprising;

randomly swapping the assignments of at least two logic blocks, whereby creating a first resulting placement; and

evaluating the first resulting placement; and

performing a non-random iteration, the non-random iteration comprising;

scanning the logic circuit and locating a plurality of components having a predetermined correlation according to a predetermined template;

non-randomly swapping the assignments of at least two logic blocks such that the predetermined correlation is preserved, thereby creating a second resulting placement; and

evaluating the second resulting placement.

9. The method of claim 8, wherein the step of performing a random iteration precedes the step of performing a non-random iteration.

10. The method of claim 9, further comprising:

after performing the non-random iteration, comparing the second resulting placement to the first resulting placement;

calculating an accept function value for the second resulting placement; and

based on the results of comparing the second resulting placement to the first resulting placement, and further based on the accept function value, returning to the first resulting placement.

11. The method of claim 8, wherein the step of performing a random iteration follows the step of performing a non-random iteration.

12. The method of claim 11, further comprising:

after performing the random iteration, comparing the first resulting placement to the second resulting placement;

calculating an accept function value for the first resulting placement; and

based on the results of comparing the first resulting placement to the second resulting placement, and further based on the accept function value, returning to the second resulting placement.

13. The method of claim 8, further comprising:

creating a library of predetermined templates; and

prior to the step of scanning the logic circuit, selecting the predetermined template from the library of predetermined templates.

14. A method of iteratively placing a plurality of components from a logic circuit into a programmable device comprising an array of logic blocks, each component including logic that can be implemented in one logic block, the method comprising:

assigning each component to one logic block in the array; and

changing the assignments of at least two logic blocks using a modified simulated annealing algorithm, the modified simulated annealing algorithm including a series of swapping steps,

a first group of the swapping steps randomly swapping the assignments of at least two logic blocks, and

a second group of the swapping steps non-randomly swapping the assignments of at least two logic blocks by scanning the logic circuit, locating a plurality of components having a predetermined correlation according to a predetermined template, and swapping the assignments of the at least two logic blocks to correlate the logic blocks according to the template.

15. The method of claim 14, wherein each of the first group of swapping steps results in a random placement, and each of the second group of swapping steps results in a non-random placement, the step of changing the assignments of at least two logic blocks using a modified simulated annealing algorithm further comprising:

comparing a first non-random placement to a first random placement;

calculating an accept function value for the first non-random placement; and

based on the results of comparing the first non-random placement to the first random placement, and further based on the accept function value, returning to the first random placement.

16. The method of claim 14, further comprising:

creating a library of predetermined templates; and

prior to the step of changing the assignments of at least two logic blocks using a modified simulated annealing algorithm, selecting the predetermined template from the library of predetermined templates.