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

• Type: Article in International Scientific Journal
• Date: 2018

Authors

Pedro Vieira dos Santos (Author) Other; José Carlos Alves (Author) FEUP; João Canas Ferreira (Author) FEUP

Journal

Title: Microprocessors and Microsystems

Vol. 58

Pages: 1-12

ISSN: 0141-9331

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 4 Citations

Scopus - 5 Citations

INSPEC

Other information

Authenticus ID: P-00N-K6F

DOI: 10.1016/j.micpro.2018.01.006

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12