GPU-Parallel SubTree Interpreter for Genetic Programming

Genetic Programming (GP) is a computationally intensive technique but its nature is embarrassingly parallel. Graphic Processing Units (GPUs) are many-core architectures which have been widely employed to speed up the evaluation of GP. In recent years, many works have shown the high performance and efficiency of GPUs on evaluating both the individuals and the fitness cases in parallel. These approaches are known as population parallel and data parallel. This paper presents a parallel GP interpreter which extends these approaches and adds a new parallelization level based on the concurrent evaluation of the individual's subtrees. A GP individual defined by a tree structure with nodes and branches comprises different depth levels in which there are independent subtrees which can be evaluated concurrently. Threads can cooperate to evaluate different subtrees and share the results via GPU's shared memory. The experimental results show the better performance of the proposal in terms of the GP operations per second (GPops/s) that the GP interpreter is capable of processing, achieving up to 21 billion GPops/s using a NVIDIA 480 GPU. However, some issues raised due to limitations of currently available hardware are to be overcomed by the dynamic parallelization capabilities of the next generation of GPUs.