Using parallelization and hardware concurrency to improve the performance of a genetic algorithm
Genetic algorithms (GAs) are powerful tools for solving many problems requiring the search of a solution space having both local and global optima. The main drawback for GAs is the long execution time normally required for convergence to a solution. This paper discusses three different techniques that can be applied to GAs to improve overall execution time. A serial software implementation of a GA designed to solve a task scheduling problem is used as the basis for this research. The execution time of this implementation is then improved by exploiting the natural parallelism present in the algorithm using a multiprocessor. Additional performance improvements are provided by implementing the original serial software GA in dedicated reconfigurable hardware using a pipelined architecture. Finally, an advanced hardware implementation is presented in which both pipelining and duplicated hardware modules are used to provide additional concurrency leading to further performance improvements. Copyright (c) 2006 John Wiley & Sons, Ltd.
parallelism concurrency genetic algorithm task scheduling multiprocessor pipelining