Article,
A High-Performance, Pipelined, FPGA-Based Genetic Algorithm Machine
Genetic Programming and Evolvable Machines, 2 (1): 33--60 (March 2001)
DOI: doi:10.1023/A:1010018632078
Abstract
Accelerating a genetic algorithm (GA) by implementing
it in a reconfigurable field programmable gate array
(FPGA) is described. The implemented GA features:
random parent selection, which conserves selection
circuitry; a steady-state memory model, which conserves
chip area; survival of fitter child chromosomes over
their less-fit parent chromosomes, which promotes
evolution. A net child chromosome generation rate of
one per clock cycle is obtained by pipelining the
parent selection, crossover, mutation, and fitness
evaluation functions. Complex fitness functions can be
further pipelined to maintain a high-speed clock cycle.
Fitness functions with a pipeline initiation interval
of greater than one can be plurally implemented to
maintain a net evaluated-chromosome throughput of one
per clock cycle. Two prototypes are described: The
first prototype (c. 1996 technology) is a multiple-FPGA
chip implementation, running at a 1 MHz clock rate,
that solves a 94-row times 520-column set covering
problem 2,200 times faster than a 100 MHz workstation
running the same algorithm in C. The second prototype
(Xilinx XVC300) is a single-FPGA chip implementation,
running at a 66 MHZ clock rate, that solves a
36-residue protein folding problem in a 2-d lattice 320
times faster than a 366 MHz Pentium II. The current
largest FPGA (Xilinx XCV3200E) has circuitry available
for the implementation of 30 fitness function units
which would yield an acceleration of 9,600 times for
the 36-residue protein folding problem.
