Method and apparatus for evolving a plurality of versions of a configuration bitstream in parallel

• US 6,378,122 B1
• Filed: 06/17/1999
• Issued: 04/23/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): DO, THUAN V
• Application Number:
  US09/336,423
• Time in Patent Office: 1,041 Days
• Field of Search: 709/217, 716/17, 716/3, 716/4, 716/5, 716/16
• 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:

creating a plurality of populations of configuration bitstreams on a data processing system;

evolving the plurality of populations of configuration bitstreams concurrently until at least one predetermined criterion is met; and

downloading at least one of the plurality of populations of configuration bitstreams from the data processing system to the programmable logic device.

2. The method of claim 1, wherein classes from which each of the populations is derived are threaded.

3. The method of claim 1, further comprising:

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

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

4. The method of claim 3, wherein the first set of resources includes one or more lookup tables and one or more flip-flops.

5. The method of claim 4, wherein the first set of resources includes lookup table inputs and one or more multiplexers.

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

7. The method of claim 6, further comprising:

assigning respective weight values to the reproductive methods; and

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

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

9. The method of claim 1, wherein the plurality of populations evolves on a plurality of devices.

10. The method of claim 1, wherein the plurality of populations evolves on a single device.

11. The method of claim 1, wherein each of the populations uses a different area of the device.