An FPGA array for cellular genetic algorithms: Application to the minimum energy broadcast problem

作者：dos Santos Pedro Vieira^*; Alves Jose Carlos; Ferreira Joao Canas

来源：Microprocessors and Microsystems, 2018, 58: 1-12.

DOI：10.1016/j.micpro.2018.01.006

• Genetic algorithms
• FPGA
• Array processor
• High-level synthesis

The genetic algorithm is a general purpose optimization metaheuristic for solving complex optimization problems. Because the algorithm usually requires a large number of iterations to evolve a population of solutions to good final solutions, it normally exhibits long execution times, especially if running on low-performance conventional processors. In this work, we present a scalable computing array to parallelize and accelerate the execution of cellular GAs (cGAs). This is a variant of genetic algorithms which can conveniently exploit the coarse-grain parallelism afforded by custom parallel processing. The proposed architecture targets Xilinx FPGAs and was implemented as an auxiliary processor of an embedded soft-core CPU (MicroBlaze). To facilitate the customization for different optimization problems, a high-level synthesis design flow is proposed where the problem-dependent operations are specified in C++ and synthesised to custom hardware, thus demanding of the programmer only minimal knowledge of low-level digital design for FPGAs. To demonstrate the efficiency of the array processor architecture and the effectiveness of the design methodology, the development of a hardware solver for the minimum energy broadcast problem in wireless ad hoc networks is employed as a use case. Implementation results for a Virtex-6 FPGA show significant speedups, especially when comparing to embedded processors used in current FPGA devices.

• 出版日期2018-4