2D and 3D On-Chip Development of Cellular Automata Machines

Cellular automata (CAs) are massively parallel machines where many simple cells work together to solve a larger problem. Each cell is very simple and only interacts with its neighbouring cells. Evolutionary algorithms (EAs) are often used to evolve them because they are very difficult to program by conventional methods. In evolvable hardware (EHW), EAs are used to evolve computer hardware designs. Field programmable gate arrays (FPGAs) are often used as a platform for implementing EHW because of their massive reconfigurability. Previous research at IDI NTNU have resulted in the construction of a virtual FPGA, better suited for EHW, implemented on an actual FPGA. The virtual FPGA is called an sblock matrix and is designed as a reconfigurable non-uniform two dimensional (2D) CA. Each cell in the CA is called an sblock. Also implemented on the physical FPGA is a developmental system based on cellular development. This system is used to develop the sblock matrix based on a set of development rules that activate new sblocks or changes the sblocks' behaviour based on neighbouring sblocks' attributes. The implementation also supports on chip fitness evaluation, which evaluates how well the current CA is performing its intended task. The fitness evaluation is based on some transform of the CA's output data. EAs need such a fitness value for their operations, so this is useful when evolving the CA. This thesis' focus is on improving and extending the system for implementation on a newer and bigger FPGA chip with more features. There are three focus areas explored in the thesis, improving the performance of the system, extending the sblock matrix to be three dimensional (3D), and implementing a new transform for interpreting output data from the sblock matrix as part of the fitness evaluation. The results show that the new FPGA allows for making many parts of the system at least 4 times faster, depending on the size of the sblock matrix. In the case of running the sblock matrix with fitness evaluation, the performance has been increased by at least an order of magnitude. The 3D sblock matrix is much more expensive to implement than the 2D one, so for implementing larger ones, the performance is scaled back down to that of the original design. The new transform of the CA's output implemented is the discrete Fourier transform (DFT), which require a lot of multiplication to be done. Implementing multiplicators on an FPGA is traditionally very expensive, however some newer FPGAs have dedicated multiplicators that can be taken advantage of. Implementing a highly parallel DFT using many such multiplicators lets the DFT be as fast as most other parts of the design without using too many additional resources