A custom computing machine for genetic algorithms without pipeline stalls
Osamu KITAURA, Hideaki Asada, Masaaki MATSUZAKI, Takamitsu Kawai, Hideki Ando, T. Shimada · 2003
Genetic algorithms (GAs) are effective for large-scale optimization problems. Several GA engines that reduce computation time have been proposed. Although these engines accelerate execution of GAs over software implementations, the speedup is not enough. This problem arises from less considerations to an efficient pipeline design. The pipeline stalls over the most of the execution time. We propose a new architecture of a GA engine, which we call H/sup 3/ engine, whose pipeline never stalls. To remove all of the pipeline stalls, our H/sup 3/ engine employs steady state GA and pipelines the roulette wheel selection using a combination of binary search and linear search. We implement the H/sup 3/ engine on an FPGA and evaluate its performance. Our evaluation results show that H/sup 3/ performs GAs about 730 times faster than software. We also discuss implementation of the H/sup 3/ engine for large-scale applications.