Accelerating Genetic Programming Using Graphics Processing Units
Tony E. Lewis · 2013
Evolution through natural selection offers the possibility of automatically generating functionally complex solutions to a wide range of problems. Methods such as Genetic Programming (GP) show the promise of this approach but tend to stagnate after relatively few generations. To research this issue, execution speed must be substantially improved. This thesis presents work to acceleratethe executionofsuch methods. TheworkusestheGraphicsProcessingUnit(GPU)totargettheevaluationofindividuals since this is the most time-consuming part of the run. Two models have been emerging for this: dynamically compiling each new generation of individuals for the GPU or using a single GPU interpreter, to which successive groups of individuals can be sent. Usingthelattermodel,aGPUinterpreterisconstructedtoimplementcyclicGP,an advanced form of GP that imposes several challenging implementation issues which are addressed. Accelerating the evaluation using the GPU is only part of the story. The next part of the work interleaves CPU and GPU computation to keep both chips as busy as possible with the tasks to which they are best suited and then to recruit multiple GPUs and CPUcores to furtheracceleratethe run. Using the former model, a compiling system is constructed and this is used to investigate two methods to overcome the primary difficulty with the approach: long compilation times. That system implements Tweaking Mutation Behaviour Learning (TMBL), a form focused on long term fitness growth and overcoming the previously mentioned stagnation issues. Further work optimises two CPU tasks highlighted by profiling: tournament selectionand individualcopying. These techniques are highly effective and permit much shorter run-times. This clears the way for research into stimulating long term fitness growth and hence for tackling new, complexproblems. 3