The Systolic Array Genetic Algorithm, An Example of Systolic Arrays as a Reconfigurable Design Methodology

this paper. Details can be found in [4]. Of interest here is our decision on which domains are expressed as spatial dimensions (actually representing a physical location on the device) and which represent time. We have chosen to express the size of the population as spatial dimensions and the length of the chromosome as time. The result is an architecture which is only dependent on the size of the population being used (and not the lengths of the chromosomes). As this is changed, we simply adjust the arrays to accommodate. We can interconnect a number of RPEs to implement a Island model parallel GA, where larger populations can be processed than can be accommodated on a single device. Different lengths of chromosomes require no hardware modifications with longer chromosomes simply requiring more time to fully pass through the arrays. We have targeted this design to a XC4036XL FPGA and implemented a four-chromosome GA. The design occupies 690 Control Logic Blocks (CLBs) and an exploratory timing analysis identified a critical path of 34.3ns allowing the device to be clocked at 28.3MHz (speed rating-0.9). The maximum number of cycles per cell is seven, dictated by the need to generate random numbers. This limits the synchronising clock to 4MHz. The macro-pipeline has a latency, for four chromosomes, of 35 cycles of the synchronising clock (8.75 ¯s). Once this has been overcome, genes emerge from the device at the rate of 16 million per second. Expressed practically, a population of four chromosomes, with 100 genes per chromosomes can be processed in 8.75 ¯s (latency) + 25 ¯s (processing) + 1 ¯s (unloading the stagger) = 34.75 ¯s or 28777 generations per second. This figure of course excludes the fitness function evaluation and the loading and unloading of the device