Method and apparatus for evolving configuration bitstreams

• US 6,430,736 B1
• Filed: 06/17/1999
• Issued: 08/06/2002
• Est. Priority Date: 02/26/1999
• Status: Expired due to Fees

• Current Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Original Assignee: Xilinx, Inc. (Advanced Micro Devices, Inc.)
• Inventors: Levi, Delon, Guccione, Steven A.
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US09/335,862
• Time in Patent Office: 1,146 Days
• Field of Search: 709/217, 703/27, 716/17, 716/6, 716/2, 716/5
• US Class Current: 716/117
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A system and method for evolving configuration bitstreams for a programmable logic device are disclosed. A plurality of data structures having respective sets of data are established. From the sets of data, respective configuration bitstreams are generated, wherein the sets of data are mapped to positions in the bitstreams. The configuration bitstreams are then evaluated for relative suitability to meet predetermined criteria when deployed on a progammable logic device. From the relative suitability of the configuration bitstreams, next-generation data for the data structures are generated using a genetic algorithm applied to sets of data. In the various embodiments, the configuration bitstreams eliminate resource contentions, selectively eliminate asynchronous behavior, include built-in test circuits, and are relocatable. Multiple populations of configuration bitstreams can evolve in parallel over a network.

Claims

1. A method for evolving configuration bitstreams for a programmable logic device, comprising:

evolving configuration bits for a first set of programmable resources of the device;

restraining evolution of configuration bits for a second set of programmable resources of the device; and

evaluating relative suitability of the configuration bits of the first set of programmable resources to meet predetermined criteria.

2. The method of claim 1, wherein the configuration bits for the second set of programmable resources are set to predetermined logic levels while evolving the bitstreams.

3. The method of claim 2, wherein the second set of programmable resources programmably supports asynchronous behavior.

4. The method of claim 2, wherein the second set of resources include connections to signal lines for which output contention is possible.

5. A method for evolving configuration bitstreams for a programmable logic device, comprising:

establishing a plurality of data structures, each data structure having a respective set of data;

generating respective configuration bitstreams from the data in the data structures mapped to positions in the respective configuration bitstreams;

evaluating relative suitability of the configuration bitstreams to meet predetermined criteria when deployed on a programmable logic device; and

generating, as a function of the relative suitability of the configuration bitstreams, next-generation data for the data structures, using a genetic algorithm applied to sets of data from the data structures.

6. The method of claim 5, wherein selected bits in the configuration bitstream are set to predetermined logic levels while evolving the bitstreams, and the selected bits in the configuration bitstream are not associated with the sets of data in the data structures.

7. The method of claim 6, wherein the selected bits include bits for programming connections for signal lines for which output contention is possible.

8. The method of claim 5, further comprising:

operating the programmable logic device with the configuration bitstreams;

reading state data generated by operating programmable logic device with the configuration bitstreams; and

evaluating the state data.

9. The method of claim 8, wherein the state data is read from a device external to the programmable logic device.

10. The method of claim 9, wherein the device external to the programmable logic device is a RAM.

11. The method of claim 5, further comprising using the next-generation data in repeating the steps of generating configuration bitstreams, evaluating relative suitability, and generating subsequent generations of data for the data structures until one or more of the configuration bitstreams evaluates to a desired suitability level.

12. The method of claim 11, wherein the data structures initially have pseudo-random data.

13. The method of claim 5, further comprising generating the next-generation data using a plurality of reproductive methods.

14. The method of claim 13, further comprising:

assigning respective weight values to the reproductive methods; and

probabilistically selecting the reproductive methods in accordance with the respective weight values.

15. The method of claim 5, further comprising:

associating respective scores with the sets of data in accordance with the relative suitability of the configuration bitstreams to meet predetermined criteria when deployed on a programmable logic device; and

probabilistically selecting sets of data for generating the next-generation data in accordance with the respective scores.

16. A method for evolving configuration bitstreams for a programmable logic device comprising:

evolving configuration bits for a first set of programmable resources of the device;

restraining evolution of configuration bits for a second set of programmable resources of the device, wherein the configuration bits for the second set of programmable resources of the device include bits that programmably enable and disable asynchronous behavior; and

evaluating relative suitability of the configuration bits of the first set of programmable resources to meet predetermined criteria.

17. The method of claim 16, further comprising restraining in the bitstream each signal line to be driven by at most one output driver.

18. The method of claim 17, further comprising:

tracking which signal lines have been connected to output drivers of the device; and

if the configuration bitstream specifies connecting to a second output driver a signal line that is presently connected to a first output driver, connecting the second output driver to another available signal line.

19. The method of claim 18, wherein selected bits in the configuration bitstream are set to predetermined logic levels while evolving the bitstreams, and the selected bits in the configuration bitstream are not associated with the sets of data in the data structures.

20. The method of claim 19, wherein the selected bits include bits for programming connections for signal lines for which output contention is possible.

21. The method of claim 19, wherein the selected bits include bits for programming at least one of the group of long lines, quad-length lines, double length lines, and single length lines.

22. The method of claim 19, wherein the selected bits include bits for causing flip-flops to behave synchronously.

23. The method of claim 19, wherein the selected bits include bits that programmably enable and disable asynchronous behavior.

24. The method of claim 23, wherein the selected bits include bits for programming at least one of the group of:

asynchronous set/reset ports of flip-flops, clock inputs to flip-flops, clock enables to flip-flops, latch modes of flip-flops, CLB outputs to be driven by other than flip-flop outputs, and CLB inputs to be driven by signals other than synchronous outputs.

25. A method for evolving configuration bitstreams for a programmable logic device, comprising:

programming a first set of resources of the device;

establishing chromosome data structures having gene codes associated with a second set of programmable resources of the device, wherein the first set is different from the second set;

creating respective configuration bitstreams from the chromosome data structures;

evaluating the respective configuration bitstreams for relative suitability to meet predetermined criteria when deployed on a programmable logic device;

evolving the gene codes of chromosome data structures based on relative suitability; and

repeating the steps of creating, evaluating, and evolving until at least one predetermined criterion is met.

26. The method of claim 25, wherein the first set of resources includes bits that programmably enable and disable asynchronous behavior.

27. The method of claim 25, wherein the first set of resource s includes bits for programming connections for signal lines for which output contention is possible.

28. A system for evolving configuration bitstreams for a programmable logic device, comprising:

means for programming a first set of resources of the device;

means for establishing chromosome data structures having gene codes associated with a second set of programmable resources of the device, wherein the first set is different from the second set;

means for creating respective configuration bitstreams from the chromosome data structures;

means for evaluating the respective configuration bitstreams for relative suitability to meet predetermined criteria when deployed on a programmable logic device;

means for evolving the gene codes of chromosome data structures based on relative suitability; and

means for continuing to create, evaluate, and evolve until at leas t one predetermined criterion is met.

29. A method for evolving configuration bitstreams for a programmable logic device, comprising:

establishing a plurality of populations of chromosome data structures having data associated with programming resources of the area of the programmable logic device;

creating respective configuration bitstreams from data of the chromosome data structures;

evaluating the respective configuration bitstreams for relative suitability to meet predetermined criteria when deployed on a programmable logic device;

evolving data in the chromosome data structures based on the relative suitability;

repeating the steps of creating, evaluating, and evolving until at least one predetermined criterion is met; and

downloading the configuration bitstreams to at least one of the devices.

30. The method of claim 29, further comprising:

programming a first set of resources of the device; and

wherein the data of the chromosome data structures are comprised of gene codes associated with a second set of programmable resources of the device, wherein the first set of resources is different from the second set of resources.

31. The method of claim 30, wherein the second set of resources includes one or more lookup tables and one or more flip-flops.

32. The method of claim 30, wherein the second set of resources includes lookup table inputs and one or more multiplexers.

33. The method of claim 29, wherein the step of evolving data in the chromosome data structures uses a plurality of reproductive methods.

34. The method of claim 33, further comprising:

assigning respective weight values to the reproductive methods; and

probabilistically selecting the reproductive methods in accordance with the respective weight values.

35. The method of claim 33, wherein the reproductive methods include elitism, mutation, cross-over, and copy.