Accelerated parallel genetic programming tree evaluation with OpenCL

Inspired by the process of natural selection, genetic programming (GP) aims at automatically building arbitrarily complex computer programs. Being classified as an “embarrassingly” parallel technique, GP can theoretically scale up to tackle very diverse problems by increasingly adding computational power to its arsenal. With today’s availability of many powerful parallel architectures, a challenge is to take advantage of all those heterogeneous compute devices in a portable and uniform way. This work proposes both (i) a transcription of existing GP parallelization strategies into the OpenCL programming platform; and (ii) a freely available implementation to evaluate its suitability for GP, by assessing the performance of parallel strategies on the CPU and GPU processors from different vendors. Benchmarks on the symbolic regression and data classification domains were performed. On the GPU we could achieve 13 billion node evaluations per second, delivering almost 10 times the throughput of a twelve-core CPU.

► We propose a parallel GP implementation in OpenCL for accelerated tree evaluation.
► On the GPU we could achieve 13 billion node evaluations per second.
► The GPU throughput is highly sensitive to the underlying parallelization strategy.
► The GPUs are remarkably faster than the multi-core CPUs (up to 24 × speedup).