Method and apparatus for testing evolvable configuration bitstreams

• US 6,363,519 B1
• Filed: 06/17/1999
• Issued: 03/26/2002
• Est. Priority Date: 02/26/1999
• Status: Expired due to Term

• 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): Kik, Phallaka
• Application Number:
  US09/335,422
• Time in Patent Office: 1,013 Days
• Field of Search: 716/1-21, 709/201-203, 709/217-222, 713/1-2, 713/180
• 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 programmable 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:

providing a test circuit to be implemented on the programmable logic device;

creating a population of configuration bitstreams, each bitstream implementing the test circuit and having a selected portion that is evolvable; and

evolving respective selected portions of the configuration bitstreams until at least one predetermined criterion is met.

2. The method of claim 1, wherein the test circuit implements a memory.

3. The method of claim 1, wherein the test circuit implements a memory and a circuit for providing test vectors to the evolved portions of the bitstreams.

4. The method of claim 3, wherein data used by the test vectors are stored in the test circuit.

5. The method of claim 3, wherein data used by the test vectors are stored in another device.

6. The method of claim 3, wherein data and instructions used by the test circuit are stored in another device.

7. The method of claim 3, wherein instructions used by the test circuit are generated by another evolved bitstream.

8. The method of claim 1, further comprising selectively changing the test circuit with each new generation of configuration bitstreams.

9. The method of claim 1, further comprising selectively changing the test circuit with each new configuration bitstream.

10. The method of claim 1, further comprising evolving the selected portions of the configuration bitstreams using a plurality of reproductive methods.

11. The method of claim 10, further comprising:

assigning respective weight values to the reproductive methods; and

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

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

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

providing a test circuit to be implemented on the programmable logic device;

establishing chromosome data structures having data associated with programming resources of the programmable logic device;

creating respective configuration bitstreams from data of the chromosome data structures and the test circuit;

evaluating the respective configuration bitstreams that include the test circuit 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; and

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

14. The method of claim 13, further comprising selectively changing the test circuit with each new generation of chromosome data structures.

15. The method of claim 13, further comprising selectively changing the test circuit with each new chromosome data structure.

16. The method of claim 13, further comprising:

programming a first set of resources of the device;

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.

17. The method of claim 13, wherein the test circuit implements a memory and a circuit for providing test vectors.

18. The method of claim 13, further comprising evolving data in the chromosome data structures using a plurality of reproductive methods.

19. The method of claim 18, further comprising:

assigning respective weight values to the reproductive methods; and

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

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

21. An apparatus for evolving configuration bitstreams for a programmable logic device, comprising:

means for providing a test circuit to be implemented on the programmable logic device;

means for establishing chromosome data structures having data associated with programming resources of the programmable logic device;

means for creating respective configuration bitstreams from data of the chromosome data structures and the test circuit;

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

means for evolving data in the chromosome data structures based on the relative suitability until at least one predetermined criterion is met.

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

creating respective configuration bitstreams on a data processing system;

downloading the configuration bitstreams from the data processing system to the device, where the device is at a location remote from the data processing system;

operating the device using the bitstream downloaded to the device;

reading back data from the device to the data processing system; and

evolving the configuration bitstreams until at least one predetermined criterion is met.

23. An apparatus for evolving configuration bitstreams for a programmable logic device, comprising:

means for establishing chromosome data structures having data associated with programming resources of an area of the programmable logic device;

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

means for evolving data in the chromosome data structures based on relative suitability until at least one predetermined criterion is met;

means for downloading the configuration bitstreams to the device via a network; and

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