Page 104 - 49A Field Guide to Genetic Programming

90 10 Fast and Distributed Genetic Programming

of computers. Each GP individual and its fitness cases are sent across the
network to a different compute node. The central node waits for the compute
nodes to return their individuals’ fitnesses. Since individuals and fitness
values are typically stored in small data structures, this can be quite efficient
since transmission overheads are limited.
The central node is an obvious bottleneck. Also, a slow compute node
or a lengthy fitness case will slow down the whole GP population, since
eventually its result will be needed before moving onto the next generation.

10.4.2 GP Running on GPUs

Modern PC graphics cards contain powerful graphics processing units
(GPUs) including a large number of computing components. For exam-
ple, it is not atypical to have 128 streaming processors on a single PC’s
graphics card. In the last few years there has been an explosion of interest
in porting scientific or general purpose computation to mass market graphics
cards (Owens, Luebke, Govindaraju, Harris, Kruger, Lefohn, and Purcell,
2007).
Indeed, the principal manufactures (nVidia and ATI) claim faster than
Moore’s Law (Moore, 1965) increase in performance, suggesting that GPU
floating point performance will continue to double every twelve months,
rather than the 18–24 months observed for electronic circuits in general and
personal computer CPUs in particular. In fact, the apparent failure of PC
CPUs to keep up with Moore’s law in the last few years makes GPU comput-
ing even more attractive. Even today’s bottom-of-the-range GPUs greatly
exceed the floating point performance of their hosts’ CPU. However, this
speed comes at a price, since GPUs provide a restricted type of parallel pro-
cessing, often referred to a single instruction multiple data (SIMD) or single
program multiple data (SPMD). Each of the many processors simultaneously
runs the same program on different data items.
There have been a few genetic programming experiments with GPUs
(Chitty, 2007; Ebner, Reinhardt, and Albert, 2005; Harding and Banzhaf,
2007; Langdon and Banzhaf, 2008; Langdon and Harrison, 2008; Loviscach
and Meyer-Spradow, 2003; Meyer-Spradow and Loviscach, 2003; Reggia,
Tagamets, Contreras-Vidal, Jacobs, Weems, Naqvi, Winder, Chabuk, Jung,
and Yang, 2006). So far, in GP, GPUs have just been used for fitness eval-
uation.
Harding and Banzhaf (2007) used the Microsoft research GPU develop-
ment DirectX TM tools to compile (using a technique originally developed by
Harris and Buxton (1996)) a whole population of Cartesian GP network pro-
grams into a single GPU program which was loaded onto a laptop’s GPU to
run the fitness cases. Chitty (2007) used a conversion technique, somewhat
like an interpreter, to automatically convert each GP tree into a program