View Full Document

Evolving Computer Programs using Rapidly Reconfigurable Field-Programmable Gate Arrays



View the full content.
View Full Document
View Full Document

12 views

Unformatted text preview:

Evolving Computer Programs using Rapidly Reconfigurable Field Programmable Gate Arrays and Genetic Programming John R Koza Forrest H Bennett III Jeffrey L Hutchings Computer Science Dept Stanford University Stanford California 94305 9020 Visiting Scholar Computer Science Dept Stanford University Stanford California 94305 Convergent Design L L C 3221 E Hollyhock Hill Salt Lake City UT 84121 koza cs stanford edu http www csfaculty stanford edu koza forrest evolute com hutch ConvergentDesign com Stephen L Bade Martin A Keane David Andre Convergent Design L L C 379 North 900 East Orem UT 84097 Martin Keane Inc 5733 West Grover Chicago Illinois 60630 Computer Science Division University of California Berkeley California bade ConvergentDesign com makeane ix netcom com dandre cs berkeley edu ABSTRACT This paper describes how the massive parallelism of the rapidly reconfigurable Xilinx XC6216 FPGA in conjunction with Virtual Computing s H O T Works board can be exploited to accelerate the time consuming fitness measurement task of genetic algorithms and genetic programming This acceleration is accomplished by embodying each individual of the evolving population into hardware in order to perform the fitness measurement task A 16 step sorting network for seven items was evolved that has two fewer steps than the sorting network described in the 1962 O Connor and Nelson patent on sorting networks and the same number of steps as a 7sorter that was devised by Floyd and Knuth subsequent to the patent and that is now known to be minimal Other minimal sorters have been evolved 1 Introduction Field programmable gate arrays FPGAs are often used to facilitate rapid prototyping of new electronic products particularly those for which time to market and other economic considerations preclude the design and fabrication of a custom application specific integrated circuit Genetic programming GP is an extension to the genetic algorithm Holland 1975 Goldberg 1989 Michalewicz 1992 Mitchell 1996 and Gen and Cheng 1997 that automatically creates a computer program to solve a problem using a simulated evolutionary process Koza 1992 1994a 1994b Koza and Rice 1992 Genetic programming successively transforms a population of individual computer programs each with an associated value of fitness into a new population of individuals i e a new generation using the Darwinian principle of survival and reproduction of the fittest and analogs of naturally occurring genetic operations such as crossover sexual recombination and mutation The dominant component of the computational burden of solving non trivial problems with the genetic algorithm or genetic programming is the task of measuring the fitness of each individual in each generation of the evolving population Relatively little computer time is expended on other tasks of the algorithm such as the creation of the initial random population at the beginning of the run and the execution of the genetic operations during the run In a run of the genetic algorithm or genetic programming the population may contain thousands or even millions of individuals and the algorithm may be run for dozens hundreds or thousands of generations Moreover the measurement of fitness for just one individual in just one generation typically involves exposing the individual program to hundreds or thousands of different combinations of inputs called fitness cases Executing one individual program for just one fitness case may in turn entail hundreds or thousands of steps Reconfigurability is not enough for practical work with genetic algorithms and genetic programming Rapid reconfigurability is what is needed where rapid means times ranging between microseconds to milliseconds for all five preliminary tasks technology mapping placement routing bit creation and downloading Field programmable gate arrays are massively parallel computational devices Once an FPGA is configured its thousands of logical function units operate in parallel at the chip s clock rate The advent of rapidly reconfigurable fieldprogrammable gate arrays FPGAs and the idea of evolvable hardware Higuchi et al 1993 Sanchez and Tomassini 1996 Higuchi 1997 Thompson 1996 opens the possiblity of embodying each individual of the evolving population into hardware Since the fitness measurement task residing in the inner loop of genetic algorithm or genetic programming constitutes the main component of the computational burden of a run the question arises as to whether the massive parallellism of FPGAs can be used to accelerate this time consuming task Fourth the genetic algorithm starts with an initial population of randomly created individuals and uses probabilistic operations to breed new candidate individuals These randomly created individuals typically do not conform to the design principles unconsciously employed by humans and are often quite bizarre Most commercially available FPGAs are vulnerable to damage caused by combinations of configuration bits that connect contending digital signals to the same line The process of verifying the acceptability of genetically created combinations of configuration bits is complex and would be prohibitively slow in the inner loop of the genetic algorithm or genetic programming Invulnerability or near invulnerability to damage is needed in order to make FPGAs practical for the inner loop of the genetic algorithm or genetic programming This alluring possiblity cannot in practice be realized with previously available FPGAs for four reasons First the encoding schemes for the configuration bits of almost all commercially available FPGAs are complex and kept confidential by the FPGA manufacturers Second the tasks of technology mapping placement routing and creation of the configuration bits consume so much time as to preclude practical use of an FPGA in the inner loop of the genetic algorithm or genetic programming Even if these four tasks could be reduced from the usual hours or minutes to as little as 10 seconds for each individual in the population these four tasks would consume 106 seconds 278 hours in a run of the genetic algorithm or genetic programming involving a population as minuscule as 1 000 for as short as 100 generations A run involving a population of 1 000 000 individuals would multiply the above unacceptably long time 278 hours by 1 000 Third the 500 milliseconds typically required for the task of downloading the configuration bits to an FPGA brief and insignificant for an engineer


Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Evolving Computer Programs using Rapidly Reconfigurable Field-Programmable Gate Arrays and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Evolving Computer Programs using Rapidly Reconfigurable Field-Programmable Gate Arrays and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?