Evolutionary algorithms: a FPGA-CPU-GPU performance comparison
Many large combinatorial optimization problems tackled with evolutionary algorithms often require very high computational times, usually due to the fitness evaluation. This fact forces programmers to use clusters of computers, a computational solution very useful for running applications of intensive calculus but having a high acquisition price and operation cost, mainly due to the Central Processing Unit (CPU) power consumption and refrigeration devices. A low-cost and high-performance alternative comes from reconfigurable computing, a hardware technology based on Field Programmable Gate Array devices (FPGAs).
The main objective of the work presented in this paper is to compare implementations on FPGAs and CPUs of different fitness functions in evolutionary algorithms in order to study the performance of the floating-point arithmetic in FPGAs and CPUs that is often present in the optimization problems tackled by these algorithms. We have taken advantage of the parallelism at chip-level of FPGAs pursuing the acceleration of the fitness functions (and consequently, of the evolutionary algorithms) and showing the parallel scalability to reach low cost, low power and high performance computational solutions based on FPGA. Finally, the recent popularity of GPUs as computational units has moved us to introduce these devices in our performance comparisons. We analyze performance in terms of computation times and economic cost.
Conclusions
The interest of a hardware solution based on FPGAs to solve combinatorial optimization problems lies in the possibility of accelerating the calculations by means of the parallel processors. The results obtained show that FPGAs offer better performance than CPUs for the problems considered when more than one parallel processor is used. In addition, we can say in the light of the achieved results that the FPGA performance is highly dependent on the nature of the fitness function (mainly, its ability to be parallelized in a high degree). For these reasons, the possibility of doing fitness processing by means of specifically designed reconfigurable processors in an evolutionary algorithm environment is sufficiently interesting to merit in-depth exploration of this computational alternative, which can offer better performance results, clearly surpassing those of CPUs.
Taking into account the very low power consumption of FPGA devices (less than 1 watt) in comparison to general-purpose processors (around 100 watts) and GPUs, a FPGA-based parallel computing environment emerges as a low-cost computing platform in intensive computing scenarios.
Some of the FPGAs (Virtex2Pro and Spartan3) used in this work have a lack of novelty, even though an acceptable speedup has been demonstrated. Nevertheless, modern Virtex5 device achieves the best performance rates. The results could be extrapolated to current and future technologies because the ones used in this paper are shown in a chronological manner: 2002–2003–2006/130–90–65 nm/P4.2–P4.3–Core2/Virtex2–Spartan3–Virtex5, and in this evolution the speedup stays, even improves. Also, these results show that it is possible to obtain good performances for some applications using FPGAs mounted on economical custom-designed boards.
Juan A. Gomez-Pulido, Miguel A. Vega-Rodriguez, Juan M. Sanchez-Perez, Silvio Priem-Mendes, Vitor Carreira. Accelerating floating-point fitness functions in evolutionary algorithms: a FPGA-CPU-GPU performance comparison. Genetic Programming and Evolvable Machines. Volume 12 Issue 4, December 2011. [doi: 0.1007/s10710-011-9137-2]
Category: Articles, Computer Science
Subscribe
If you enjoyed this article, subscribe to receive more just like it.
