Synthesis of a systolic array genetic algorithm

Megson, G. M. and Bland, I. M. (1998) Synthesis of a systolic array genetic algorithm. In: Proceedings of the first merged International Parallel Processing Symposium & Symposium on Parallel and Distributed Processing. IEEE, pp. 316-320. ISBN 0818684038 doi: 10.1109/IPPS.1998.669933

Abstract/Summary

The paper presents a design for a hardware genetic algorithm which uses a pipeline of systolic arrays. These arrays have been designed using systolic synthesis techniques which involve expressing the algorithm as a set of uniform recurrence relations. The final design divorces the fitness function evaluation from the hardware and can process chromosomes of different lengths, giving the design a generic quality. The paper demonstrates the design methodology by progressively re-writing a simple genetic algorithm, expressed in C code, into a form from which systolic structures can be deduced. This paper extends previous work by introducing a simplification to a previous systolic design for the genetic algorithm. The simplification results in the removal of 2N 2 + 4N cells and reduces the time complexity by 3N + 1 cycles.