A Reconfigurable Hardware Implementation of Genetic Algorithms for
VLSI CAD Design
By Gurwant Koonar, August 2003
Abstract:
In recent years there has been a great interest in accelerating time consuming
algorithms that solve large combinatorial optimization problems.
The advent of high density field programmable gate arrays in combination with
efficient synthesis tools have enabled the production of custom machines for
such difficult problems. Genetic Algorithms (GAs) are robust techniques based
on natural selection that can be used to solve a wide range of problems, including
circuit partitioning. Although, a GA can provide very good solutions for such problems
the amount of computations and iterations required
for this method is enormous. As a result, software implementations
of GA can become extremely slow for large circuit partitioning problems.
In this research project, an architecture for implementing GAs on a Field Programmable
Gate Array (FPGA) is presented. The architecture employs a combination of
pipelining and parallelization to achieve substantial speedups.
The GA accelerator proposed in this paper achieves more than 100x
improvement in processing speed over its counterpart software implementation.
