Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-06-17
2002-08-06
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06430736
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to genetic algorithms and evolvable hardware, and more particularly to a method for evolving configuration bitstreams for programmable logic devices.
BACKGROUND
Many conventional design methodologies are based on a structured design approach. That is, high-level requirements are partitioned, perhaps hierarchically, into lower-level requirements. Teams of engineers are assigned to create designs and sub-designs that meet the requirements at the different levels. The structured design methodology is advantageous because it supports building on past experiences in addressing similar types of requirements, thereby promoting development of an effective design in an efficient manner. However, a drawback to traditional design methods is that the same experiences that promote quickly satisfying a requirement may blind engineers to alternative, and perhaps better, solutions.
Work is presently underway to fundamentally change the way in which designs are created. The new methodology uses principles of natural selection from the biological world to create electronic hardware designs. The process is often characterised as “evolvable hardware” or using genetic algorithms to create hardware designs. In an example process of evolving a design, a population of designs is first randomly created, tested, and scored based on the suitability to meet the design requirements. Then based on natural selection principles, certain ones of the designs in the population are selected to “reproduce,” that is, used to create new designs for the population. The process of testing, scoring, and reproducing is then repeated until a suitable design has evolved.
The hardware used in evolving designs is typically some type of programmable logic device. SRAM FPGAs are suitable because they can be programmed, tested, and reprogrammed many times in evolving a design. The XC6200 FPGA from XILINX has been often used for the additional reason that the architecture does not allow contention in the device, no matter what the bitstream is.
A problem often encountered with evolving designs for other SRAM FPGA architectures is that the objective designs are usually intended to be digital solutions for digital devices (e.g., a bitstream for an FPGA), but an evolved design can cause a digital device to exhibit unintended asynchronous behavior and even contain contentions for resources capable of destroying the device. For example, widely used-commercial parts, such as the XC4000EX/XL and Virtex FPGAs from XILNX, can be damaged if multiple signals are allowed to drive the same wire. Thus, such parts have been avoided for evolving hardware.
At present, testing the evolving circuits is very time consuming. Many hours are spent reading and writing configuration bitstreams and testing the fitness of the bitstreams. Some implementations use dedicated input/output ports for probing the evolving designs. However, dedicating input/output ports to testing limits the portability of the design. Further, setting up the hardware for a test procedure is expensive. A test system board must include several IC devices for performing the tests, and these IC devices may not be configurable. If these non-configurable IC devices do not perform properly with an evolved design, the tests may not be valid or useful, and the hardware may have to be changed.
Today's evolved circuits tend to be suitable for implementation on specific devices. Irregularities in device fabrication, operating temperature, operating voltage, and other environmental factors can affect a circuit's performance, and thus, its fitness. Therefore, an evolved circuit is rarely suitable for implementation on a variety of devices.
A method that address the aforementioned problems, as well as other related problems, is therefore desirable.
SUMMARY OF THE INVENTION
The invention provides a method and apparatus for evolving configuration bitstreams. In particular, the embodiments permit elimination of contentions for certain hardware resources and unintended asynchronous behavior.
In one embodiment a method for evolving configuration bitstreams for a programmable logic device is provided. The method comprises 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.
In another embodiment, the method comprises establishing a plurality of data structures, each data structure having a respective set of data. Respective configuration bitstreams are generated from the data in the data structures, which are mapped to positions in the bitstreams. The relative suitability of the configuration bitstreams to meet predetermined criteria when deployed on a programmable logic device is evaluated, and next-generation data for the data structures is generated using a genetic algorithm applied to sets of data from the data structures as a function of the relative suitability of the configuration bitstreams.
In another method, a first set of resources of the device is programmed, and chromosome data structures having gene codes associated with a second set of programmable resources of the device are established. The first set of resources is different from the second set of resources. Respective configuration bitstreams are created from the chromosome data structures, and the respective configuration bitstreams are evaluated for relative suitability to meet predetermined criteria when deployed on the programmable logic device. The gene codes of chromosome data structures are evolved based on the evaluation, and the steps of creating, evaluating, and evolving are repeated until at least one predetermined criterion is met.
In another embodiment a system is provided. The system comprises: 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; means for evolving the gene codes of chromosome data structures; and means for continuing to create, evaluate, and evolve until at least one predetermined criterion is met.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.
REFERENCES:
patent: 5784577 (1998-07-01), Jacobson et al.
patent: 5794033 (1998-08-01), Aldebert et al.
patent: 5864486 (1999-01-01), Deming et al.
patent: 5995744 (1999-11-01), Guccione
patent: 6023565 (2000-02-01), Lawman et al.
patent: 6035106 (2000-03-01), Carruthers et al.
patent: 6052720 (2000-04-01), Traversat et al.
patent: 6078735 (2000-06-01), Baxter
patent: 6078736 (2000-06-01), Guccione
patent: 6099583 (2000-08-01), Nag
patent: 6102963 (2000-08-01), Agrawal
patent: 6134516 (2000-10-01), Wang
patent: 6167364 (2000-12-01), Stellenberg et al.
patent: 6216258 (2001-04-01), Mohan et al.
patent: 6226776 (2001-05-01), Panchul et al.
patent: 6237029 (2001-05-01), Master
patent: 6243851 (2001-06-01), Hwang et al.
patent: 6272669 (2001-08-01), Anderson et al.
patent: 6279146 (2001-08-01), Evans et al.
patent: 6301695 (2001-10-01), Burnham et al.
patent: 0 657 832 (1995-06-01), None
patent: WO 98 19256 (1998-05-01), None
patent: WO 00 38087 (2000-06-01), None
Adrian Thompson, “Silicon Evolution,” Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al. (Eds), pp. 444-452, MIT Press 1996.
Levi D and Guccione S. A.: “GeneticFPGA: A Java-Based Tool for Evolving Stable Circuits”, Part of the SPIE Conference on Reconfigurable Technology: FPGAs for Computing Applications, vol. 3844, Sep. 1999 pp. 114-121, Boston USA.
Kitano H. et al.: “Evolvable Hardware with Development”, IEEE International Sympos
Guccione Steven A.
Levi Delon
Brown, Esq. Scott R.
Do Thuan
Maunu LeRoy D.
Smith Matthew
Xilinx , Inc.
LandOfFree
Method and apparatus for evolving configuration bitstreams does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for evolving configuration bitstreams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for evolving configuration bitstreams will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876244