Main PageFPGA98Front MatterTable of ContentsSession IndexEvolving Computer Programs using RapidlyReconfigurable Field-Programmable Gate Arrays andGenetic ProgrammingJohn R. KozaComputer Science Dept.Stanford UniversityStanford, California [email protected]://www-cs-faculty.stanford.edu/~koza/Forrest H Bennett IIIVisiting ScholarComputer Science Dept.Stanford UniversityStanford, California [email protected] L. HutchingsConvergent Design, L.L.C.3221 E. Hollyhock HillSalt Lake City, UT [email protected] L. BadeConvergent Design, L.L.C.379 North, 900 EastOrem, UT, [email protected] A. KeaneMartin Keane Inc.5733 West GroverChicago, Illinois [email protected] AndreComputer Science DivisionUniversity of CaliforniaBerkeley, [email protected] paper describes how the massiveparallelism of the rapidly reconfigurableXilinx XC6216 FPGA (in conjunctionwith Virtual Computing's H.O.T. Worksboard) can be exploited to accelerate thetime-consuming fitness measurement taskof genetic algorithms and geneticprogramming. This acceleration isaccomplished by embodying eachindividual of the evolving population intohardware in order to perform the fitnessmeasurement task. A 16-step sortingnetwork for seven items was evolved thathas two fewer steps than the sortingnetwork described in the 1962 O'Connorand Nelson patent on sorting networks(and the same number of steps as a 7-sorter that was devised by Floyd andKnuth subsequent to the patent and that isnow known to be minimal). Otherminimal sorters have been evolved.1. IntroductionField-programmable gate arrays (FPGAs) are often used tofacilitate rapid prototyping of new electronic products –particularly those for which time-to-market and othereconomic considerations preclude the design and fabricationof a custom application-specific integrated circuit.Genetic programming (GP) is an extension to the geneticalgorithm (Holland 1975, Goldberg 1989, Michalewicz1992, Mitchell 1996, and Gen and Cheng 1997) thatautomatically creates a computer program to solve aproblem using a simulated evolutionary process (Koza1992, 1994a, 1994b; Koza and Rice 1992). Geneticprogramming successively transforms a population ofindividual computer programs, each with an associatedvalue of fitness, into a new population of individuals (i.e.,a new generation), using the Darwinian principle ofsurvival and reproduction of the fittest and analogs ofnaturally occurring genetic operations such as crossover(sexual recombination) and mutation.The dominant component of the computational burden ofsolving non-trivial problems with the genetic algorithm orgenetic programming is the task of measuring the fitness ofeach individual in each generation of the evolvingpopulation. (Relatively little computer time is expendedon other tasks of the algorithm, such as the creation of theinitial random population at the beginning of the run andthe execution of the genetic operations during the run). In arun of the genetic algorithm or genetic programming, thepopulation may contain thousands or even millions ofindividuals and the algorithm may be run for dozens,hundreds, or thousands of generations. Moreover, themeasurement of fitness for just one individual in just onegeneration typically involves exposing the individualprogram to hundreds or thousands of different combinationsof inputs (called fitness cases). Executing one individualprogram for just one fitness case may, in turn, entailhundreds or thousands of steps.Field-programmable gate arrays are massively parallelcomputational devices. Once an FPGA is configured, itsthousands of logical function units operate in parallel at thechip's clock rate. The advent of rapidly reconfigurable field-programmable gate arrays (FPGAs) and the idea ofevolvable hardware (Higuchi et al. 1993; Sanchez andTomassini 1996; Higuchi 1997; Thompson 1996) opensthe possiblity of embodying each individual of the evolvingpopulation into hardware. Since the fitness measurementtask residing in the inner loop of genetic algorithm orgenetic programming constitutes the main component ofthe computational burden of a run, the question arises as towhether the massive parallellism of FPGAs can be used toaccelerate this time-consuming task.This alluring possiblity cannot, in practice, be realized withpreviously available FPGAs for four reasons.First, the encoding schemes for the configuration bits ofalmost all commercially available FPGAs are complex andkept confidential by the FPGA manufacturers.Second, the tasks of technology mapping, placement,routing, and creation of the configuration bits, consume somuch time as to preclude practical use of an FPGA in theinner loop of the genetic algorithm or geneticprogramming. Even if these four tasks could be reducedfrom the usual hours or minutes to as little as 10 secondsfor each individual in the population, these four tasks wouldconsume 106 seconds (278 hours) in a run of the geneticalgorithm or genetic programming involving a populationas minuscule as 1,000 for as short as 100 generations. Arun involving a population of 1,000,000 individuals wouldmultiply the above unacceptably long time (278 hours) by1,000.Third, the 500 milliseconds typically required for the task ofdownloading the configuration bits to an FPGA (brief andinsignificant for an engineer who has spent hours, days, ormonths on a single prototype design) would consume 14hours for even a minuscule population of 1,000 that wasrun for as few as 100 generations. Again, a run involving apopulation of 1,000,000 individuals would multiply thisalready unacceptably long time (14 hours) by 1,000.What's worse – both of these unacceptably long times (278hours and 14 hours) are merely preliminary to the timerequired by the FPGA for the actual problem-specific fitnessmeasurement. Thus, there is a discrepancy of numerousorders of magnitude between the time required for thetechnology mapping, placement, routing, bit creation, anddownloading tasks and the time available for thesepreliminaries in the inner loop of a practical run of thegenetic algorithm or genetic programming.Reconfigurability is not enough for practical work withgenetic algorithms and genetic programming. Rapidreconfigurability is what is needed – where "rapid" meanstimes ranging between microseconds to milliseconds for allfive preliminary tasks (technology mapping, placement,routing, bit