Parallel Evolutionary Optimization.- A Model for Parallel Operators in Genetic Algorithms.- Parallel Evolutionary Multiobjective Optimization.- Parallel Hardware for Genetic Algorithms.- A Reconfigurable Parallel Hardware for Genetic Algorithms.- Reconfigurable Computing and Parallelism for Implementing and Accelerating Evolutionary Algorithms.- Distributed Evolutionary Computation.- Performance of Distributed GAs on DNA Fragment Assembly.- On Parallel Evolutionary Algorithms on the Computational Grid.- Parallel Evolutionary Algorithms on Consumer-Level Graphics Processing Unit.- Parallel Particle Swarm Optimization.- Intelligent Parallel Particle Swarm Optimization Algorithms.- Parallel Ant Colony Optimization for 3D Protein Structure Prediction using the HP Lattice Model.
4 Reconfigurable Computing and Parallelism for Implementing and Accelerating Evolutionary Algorithms (p. 71-72)
Miguel A. Vega Rodr´ýguez1, Juan A. G´omez Pulido1, Juan M. S´anchez
P´erez1, Jos´e M. Granado Criado1, and Manuel Rubio del Solar2
1 Departamento de Inform´atica,
Escuela Polit´ecnica, Universidad de Extremadura,
Campus Universitario s/n, 10071 C´aceres, Spain
(mavega,jangomez,sanperez,granado)@unex.es, http://arco.unex.es
2 Servicio de Inform´atica, Universidad de Extremadura,
Avda. de Elvas s/n, Badajoz, Spain
mrubio@unex.es
Reconfigurable Computing is a technique for executing algorithms directly on the hardware in order to accelerate and increase their performance. Recon- figurable hardware consists of programmed FPGA chips for working as specific purpose coprocessors. The algorithms to be executed are programmed by means of description hardware languages and implemented in hardware using synthesis tools. Recon.gurable Computing is very useful for processing high computational cost algorithms because the algorithms implemented in a speci .c hardware get greater performance than if they are processed by a general purpose conventional processor. So Recon.gurable Computing and parallel techniques have been applied on a genetic algorithm for solving the salesman problem and on a parallel evolutionary algorithm for time series predictions. The hardware implementation of these two problems allows a wide set of tools and techniques to be shown. In both cases satisfactory experimental performances have been obtained.
4.1 Introduction
The reader will .nd two instances of hardware implementation of evolutionary algorithms in this chapter. Both instances provide distinct points of view on how to apply recon.gurable computing technology to increase algorithm e.ciency. Two cases are considered: a genetic algorithm and a parallel evolutionary algorithm. As a result, many .elds of recon.gurable hardware techniques are covered, such as modeling by means of high-level hardware description languages, implementation on di.erent recon.gurable chips, hierarchical design, etc.
In Section 4.2 a general introductory view about Recon.gurable Computing and Field Programmable Gate Arrays (FPGAs) circuits, programming languages for algorithm modelling and implementing and the recon.gurable prototyped platforms used is o.ered. This will give us an idea about why this technology for the synthesis of the evolutionary algorithms is useful. In Section 4.3 we perform a detailed study on the use of parallelism and FPGAs for implementing Genetic Algorithms (GAs). In particular, we do an experimental study using the Traveling Salesman Problem (TSP). After an overview on the TSP, we explain the GA used for solving it. Then, we study the hardware implementation of this algorithm, detailing 13 di.erent hardware versions. Each new version improves the previous one, and many of these improvements are based on the use of parallelism techniques. In this section we also show and analyse the results found: Parallelism techniques that obtain better results, hardware/software comparisons, resource use, operation frequency, etc. We conclude stating FPGA implementation is better when the problem size increases or when better solutions (nearer to the optimum) must be found.
Finally, in Section 4.4 we show an application of Recon.gurable Computing for accelerating the execution of one of the steps of a parallel evolutionary algorithm. In the proposed algorithm the intermediate results evolve to find the local optimum. The algorithm has been created to increase the precision in the time series behaviour prediction. To do this, a set of processing units works in parallel mode to send its results to an evolutionary unit. This unit must determine an optimum value and generate a new input parameter sequence for the parallel units. The evolutionary unit has been implemented in the hardware in order to study its performance. We have found the algorithm execution is accelerated. This result encourages us to design, in the near future, a specific purpose processor for time series identification.
