Method and apparatus for relocating elements in an evolvable configuration bitstream

• US 6,539,532 B1
• Filed: 06/17/1999
• Issued: 03/25/2003
• 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): Siek, Vuthe
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US09/335,437
• Time in Patent Office: 1,377 Days
• Field of Search: 716/16, 716/18, 716/4
• 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:

selecting an area of the programmable device in which programmable logic is to evolve;

evolving a population of configuration bitstreams, each bitstream having a selected portion that is evolvable and associated with the area in which programmable logic is to evolve;

moving at least one of the configuration bitstreams to another area; and

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

2. The method of claim 1 wherein the area is moved to a second area located on the programmable device.

3. The method of claim 1 wherein the area is moved to a second area located on a different programmable device.

4. The method of claim 3 wherein the different programmable device is located on a different board from the programmable logic device.

5. The method of claim 1, wherein the area includes a group of configurable logic blocks.

6. The method of claim 5, wherein the area is rectangle of configurable logic blocks.

7. The method of claim 1, further comprising selectively changing boundaries of the area with each new generation of configuration bitstreams.

8. The method of claim 7, further comprising selecting a device on which the programmable logic is to evolve.

9. The method of claim 7, further comprising selectively changing devices with each new generation of configuration bitstreams.

10. The method of claim 1, further comprising selecting a device on which the programmable logic is to evolve.

11. The method of claim 10, further comprising selectively changing devices with each new generation of configuration bitstreams.

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

selecting an area of the programmable device in which programmable logic is to evolve;

establishing 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; and

repeating the steps of creating, evaluating, and evolving until at least one predetermined criterion is met, further comprising selecting a device on which the programmable logic is to evolve, and selectively changing devices with each new generation of chromosome data structures.