Automatic random tree generator on FPGA

11:10 am - 11:35 am 24 Thursday


Genetic Programming

 This work deals with the implementation of the automatic generation of random syntax trees on FPGAs, these trees are used as the initial population in genetic programming (GP) algorithms and serve as the mean of how genetic material is inherited through the generations. GP is an evolutionary computation technique that allows to find the solution of a search problem without requiring the user to provide prior information about the structure or form of the solution. Trees are the most used data structure in GP applications found in literature for the representation of programs, these programs are normally mathematical functions although they may be computer code or movement instruction in the case of robotic applications.

Initially, GP was run using software on a desktop computer or workstation, however as the paradigm matured, GP was used on the resolution of more complex problems leading to longer times and larger memory consumption. One method to reduce time consumption is to use multicore microprocessor, this technique allows the whole program to run in concurrent threads that accelerate the calculation process, however the number of cores found in commercial microprocessor are limited to four or so. On the other hand, one can take advantage of the massive parallel processing power that a Graphics Processor Unit (GPU) exhibits. GPU may seem the natural choice when high parallel processing power is needed, however the strength ofGPUs is also its own weakness because high parallelization works well when the very same operation needs to be performed on a vast amount of data, but it is not efficient when different operations on differentdata is required, the latter is a normal case when GP is used in real world applications. Here is when another well-known device comes to the rescue: the Field Programmable Gate Array (FPGA). FPGA is a very flexible device that allows the implementation of complex digital systems in a small silicon chip or Integrated Circuit. FPGA is less expensive compared to the GPU or a CPU not to mention compared to other high performance computing technologies. Another good characteristic of FPGAs is that it is possible to perform parallel computing because it is able to handle multiple parallel processes.

Finally, one should point to the fact that FPGA is reconfigurable so it provides additional flexibility. Some works have addressed the issue of GP hardware implementation on GPU like in [3] and [5], some others have done implementations on FPGAs like in [1], [2] and [4], nevertheless, none of the previous works implemented true tree data structure as means of evolving programs. 

In this work the implementation of the automatic generation of random trees is totally embedded on a FPGA and allows flexibility in the tree instantiation in contrast to previous works, this means that besides the tree-like structure implementation on the FPGA, a Pseudo-Random Number Generator is used, so random function or variable/constant selection is enabled. As several processes may be parallelized on the FPGA, each tree is generated in parallel, so it means that a signicant reduction in the amount of time consumed is expected when compared to traditional runs on CPUs, more signicant is the fact that true embedded tree-like data structures are embedded on the FPGA.


[1]Radek Hrbacek and Michaela Sikulova Co evolutionary Cartesian Genetic Programming in FPGA.12th European Conference on Articial Life Proceedings, pp. 431-438, 2013.

[2]Sidhu, R. P. S.; Mei, A. and Prasanna, V. K. Genetic Programming using Self-Recongurable.FPGAs, in '9th International Workshop on Field Programmable Logic and Applications' , Springer-Verlag,Glasgow, UK , pp. 301-312, 1998.

[3]Douglas A. Augusto, Helio J.C. Barbosa. Accelerated parallel genetic programming tree evaluation with OpenCL.Journal of Parallel and Distributed Computing, Volume 73, Issue 1, pp. 86-100, January 2013.

[4]M. I. Heywo o d and A. N. Zincir-Heywood Register Based Genetic Programming on FPGA Computing Platforms Genetic Programming, Proceedings of EuroGP'2000, pp. 44-59, 2000.

[5]Harding, S. Evolution of image filters on graphics processor units using Cartesian Genetic Programming Evolutionary Computation, IEEE World Congress on Computational Intelligence, pp. 1921-1928, 2008.

Carlos Goribar