Pipelined Genetic Propagation
File(s)
Accepted version
Author(s)
Thomas, DB
Guo, L
Guo, C
Luk, W
Type
Conference Paper
Abstract
Genetic Algorithms (GAs) are a class of numerical
and combinatorial optimisers which are especially useful for
solving complex non-linear and non-convex problems. However,
the required execution time often limits their application to smallscale
or latency-insensitive problems, so techniques to increase
the computational efficiency of GAs are needed. FPGA-based
acceleration has significant potential for speeding up genetic
algorithms, but existing FPGA GAs are limited by the generational
approaches inherited from software GAs. Many parts
of the generational approach do not map well to hardware,
such as the large shared population memory and intrinsic loopcarried
dependency. To address this problem, this paper proposes
a new hardware-oriented approach to GAs, called Pipelined
Genetic Propagation (PGP), which is intrinsically distributed
and pipelined. PGP represents a GA solver as a graph of
loosely coupled genetic operators, which allows the solution to be
scaled to the available resources, and also to dynamically change
topology at run-time to explore different solution strategies.
Experiments show that pipelined genetic propagation is effective
in solving seven different applications. Our PGP design is 5 times
faster than a recent FPGA-based GA system, and 90 times faster
than a CPU-based GA system.
and combinatorial optimisers which are especially useful for
solving complex non-linear and non-convex problems. However,
the required execution time often limits their application to smallscale
or latency-insensitive problems, so techniques to increase
the computational efficiency of GAs are needed. FPGA-based
acceleration has significant potential for speeding up genetic
algorithms, but existing FPGA GAs are limited by the generational
approaches inherited from software GAs. Many parts
of the generational approach do not map well to hardware,
such as the large shared population memory and intrinsic loopcarried
dependency. To address this problem, this paper proposes
a new hardware-oriented approach to GAs, called Pipelined
Genetic Propagation (PGP), which is intrinsically distributed
and pipelined. PGP represents a GA solver as a graph of
loosely coupled genetic operators, which allows the solution to be
scaled to the available resources, and also to dynamically change
topology at run-time to explore different solution strategies.
Experiments show that pipelined genetic propagation is effective
in solving seven different applications. Our PGP design is 5 times
faster than a recent FPGA-based GA system, and 90 times faster
than a CPU-based GA system.
Date Issued
2015-05-06
Citation
2015
Source
IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM)
Start Date
2015-05-03
Finish Date
2015-05-05
Coverage Spatial
Vancouver, BC, Canada