General Purpose Genetic Programming on Graphics Processing Units

GP GP GPU

General Purpose Genetic Programming on Graphics Processing Units

The use of Graphics Processing Units (GPUs) in scientific computing is becoming increasingly common. GPUs are low cost parallel processors that can readily be exploited for many types of general purpose computation. Recently, the computational intelligence community has started to develop for the GPU platform. This web page is primarily dedicated to the use of GPUs as a platform for Genetic Programming.

Publications

(Newest first)

A Fast High Quality Pseudo Random Number Generator for Graphics Processing Units *W. B. Langdon*
Limited numerical precision of nVidia GeForce 8800 GTX and other GPUs requires careful implementation of PRNGs. The Park-Miller PRNG is programmed using G80's native Value4f floating point in RapidMind C++. Speed up is more than 40. Code is available via ftp cs.ucl.ac.uk genetic/gpcode/random-numbers/gpu_park-miller.tar.gz

Download	Bibtex	WCCI 2008

Linear Genetic Programming GPGPU on Microsoft’s Xbox 360 Garnett Wilson and Wolfgang Banzhaf
We describe how to harness the graphics processing abilities of a consumer video game console (Xbox 360) for general programming on graphics processing unit (GPGPU) purposes. In particular, we implement a linear GP (LGP) system to solve classification and regression problems. We conduct inter- and intra-platform benchmarking of the Xbox 360 and PC, using GPU and CPU implementations on both architectures. Platform benchmarking confirms highly integrated CPU and GPU programming flexibility of the Xbox 360, having the potential to alleviate typical GPGPU decisions of allocating particular functionalities to CPU or GPU.

Download	Bibtex	WCCI 2008

Generating Massive High-Quality Random Numbers using GPU *Wai-Man Pang, Tien-Tsin Wong and Pheng-Ann Heng*
Pseudo-random number generators (PRNG) have been intensively used in many stochastic algorithms in artificial intelligence, computer graphics and other scientific computing. However, the current commodity GPU design does not facilitate the efficient implementation of high-quality PRNGs that require high-precision integer arithmetics and bitwise operations. In this paper, we propose a framework to generate a high-quality PRNG shader for all kinds of GPUs. We adopt the cellular automata (CA) PRNG to facilitate high speed and parallel random number generation. The configuration of the CA PRNG is completed automatically by optimizing an objective function that accounts for quality of generated random sequences. To visually evaluate the result, we apply the best PRNG shader to photon mapping. Timing statistics show that our GPU parallelized PRNG is much faster than a pure CPU implementation.

Download	Bibtex	WCCI 2008

SOMGPU: An Unsupervised Pattern Classifier on Graphical Processing Unit *Raghavendra D. Prabhu*
Graphical Processing Units (GPUs) have been, lately used for general purpose tasks owing to their implicit parallel nature. One such task is that of pattern classification. Highly parallel tasks like these suffer from performance loss owing to the sequential nature of Central Processing Unit (CPU). To match the image processing power of human brain even slightly, this problem beckons the utilization of enormous computational power and parallel environs of GPUs. Unless there is a task which can be parallelized to the required extent the gain obtained is lost owing to the overhead involved. Thus, it is equally important to understand some limitations of GPU before venturing in this direction and deal with it appropriately to obtain satisfactory results. Artificial Neural Networks (ANN) are found to be appropriate while dealing with pattern recognition problems. Kohonen's Self Organizing Map (SOM) has been used for classification out of other approaches for its implicit parallel nature, albeit with minor modifications to make it suit the parallel environment. nVIDIA GeForce 6150 Go with Microsoft Research Accelerator as the high level library has been chosen as the platform to provide this environment.

Download	Bibtex	WCCI 2008

SOMGPU: An Unsupervised Pattern Classifier on Graphical Processing Unit *Raghavendra D. Prabhu*
Graphical Processing Units (GPUs) have been, lately used for general purpose tasks owing to their implicit parallel nature. One such task is that of pattern classification. Highly parallel tasks like these suffer from performance loss owing to the sequential nature of Central Processing Unit (CPU). To match the image processing power of human brain even slightly, this problem beckons the utilization of enormous computational power and parallel environs of GPUs. Unless there is a task which can be parallelized to the required extent the gain obtained is lost owing to the overhead involved. Thus, it is equally important to understand some limitations of GPU before venturing in this direction and deal with it appropriately to obtain satisfactory results. Artificial Neural Networks (ANN) are found to be appropriate while dealing with pattern recognition problems. Kohonen's Self Organizing Map (SOM) has been used for classification out of other approaches for its implicit parallel nature, albeit with minor modifications to make it suit the parallel environment. nVIDIA GeForce 6150 Go with Microsoft Research Accelerator as the high level library has been chosen as the platform to provide this environment.

Download	Bibtex	WCCI 2008

Evolution of Image Filters on Graphics Processor Units Using Cartesian Genetic Programming *Simon Harding*
Graphics processor units are fast, inexpensive parallel computing devices. Recently there has been great interest in harnessing this power for various types of scientific computation, including genetic programming. In previous work, we have shown that using the graphics processor provides dramatic speed improvements over a standard CPU in the context of ﬁtness evaluation. In this work, we use Cartesian Genetic Programming to generate shader programs that implement image ﬁlter operations. Using the GPU, we can rapidly apply these programs to each pixel in an image and evaluate the performance of a given ﬁlter. We show that we can successfully evolve noise removal ﬁlters that produce better image quality than a standard median ﬁlter.

Download	Bibtex	WCCI 2008

Speedup of Fuzzy Logic Through Stream Processing on Graphics Processing Units *Nicholas Harvey, Robert Luke, James M. Keller and Derek Anderson*
As the size and operator complexity of a fuzzy logic system increases, computational tractability becomes a problem. There is a significant amount of parallelism in both the creation of the fuzzy rule base and in fuzzy inference. Traditional processors (CPUs) cannot take full advantage of this natural parallelism. Graphics Processing Units (GPUs) speed up rule construction and inference by utilizing up to 128 processing units operating in parallel. Normally, these processors are used to perform high speed graphics calculations for video games, movies, and other areas of intense graphical work. In this paper, a method is discussed for speeding up fuzzy logic by structuring it into a format such that it resembles the standard rendering procedure for a graphics pipeline based on rasterization.

Download	Bibtex	WCCI 2008

Evolving GeneChip Correlation Predictors on Parallel Graphics Hardware *W. B. Langdon*
A GPU is used to datamine five million correlations between probes within Affymetrix HG-U133A probesets across 6685 human tissue samples from NCBI's GEO database. These concordances are used as machine learning training data for genetic programming running on a Linux PC with a RapidMind OpenGL GLSL backend. GPGPU is used to identify technological factors influencing High Density Oligonuclotide Arrays (HDONA) performance. GP suggests mismatch (PM/MM) and Adenosine/Guanine ratio influence microarray quality. Initial results hint that Watson-Crick probe self hybridisation or folding is not important. Under GPGPGPU an nVidia GeForce 8800 GTX interprets 300 million GP primitives/second (300 MGPops, approx 8 GFLOPS).

Download	Bibtex	WCCI 2008

GPU Based Extraction of Moving Objects without Shadows Under Intensity Changes *Shinji Fukui, Yuji Iwahori and Robert J. Woodham*
This paper proposes a GPU based algorithm for extracting moving objects in real time. The whole process of the proposed approach is handled on GPU. GPU is used for acceleration and the proposed approach increases processing speed dramatically. The method uses a* component and b* component of CIELAB color space without extracting shadow areas as moving objects. It is robust to intensity changes because an estimated background image is generated and moving objects are extracted using background subtraction of the estimated background image and the observed image. The proposed method reduces the times for transferring calculation results from GPU into CPU and the opposite transfer. Reducing the transfer times contributes to speeding up of the proposed method. Results are demonstrated with experiments on real data.

Download	Bibtex	WCCI 2008

Genetic Programming on GPUs for Image Processing *Simon Harding and Wolfgang Banzhaf*
The evolution of image ﬁlters using Genetic Programming is a relatively unexplored task. This is most likely due to the high computational cost of evaluating the evolved programs. We use the parallel processors available on modern graphics cards to greatly increase the speed of evaluation. Previous papers in this area dealt with noise reduction and edge detection. Here we demonstrate that other more complicated processes can also be successfully evolved, and that we can reverse engineer the output from ﬁlters used in common graphics manipulation programs.

Download	Bibtex	Technical report

Population Parallel GP on the G80 GPU *Denis Robilliard, Virginie Marion-Poty and Cyril Fonlupt*
The availability of low cost powerful parallel graphics cards has stimulated a trend to port GP on Graphics Processing Units (GPUs). Previous works on GPUs have shown evaluation phase speedups for large training cases sets. Using the CUDA language on the G80 GPU, we show it is possible to efficiently interpret several GP programs in parallel, thus obtaining speedups also for small training sets starting at less than 100 training cases. Our scheme was embedded in the well-known ECJ library, providing an easy entry point for owners of G80 GPUs.

Download Slides Code download	Bibtex	EuroGP 2008

A SIMD interpreter for Genetic Programming on GPU Graphics Cards W.B. Langdon and W. Banzhaf
Mackey-Glass chaotic time series prediction and nuclear protein classification show the feasibility of evaluating genetic programming populations directly on parallel consumer gaming graphics processing units. Using a Linux KDE computer equipped with an nVidia GeForce 8800 GTX graphics processing unit card the C++ SPMD interpretter evolves programs at giga GP operation per second (895 million GPops). We use the RapidMind general processing on GPU (GPGPU) framework to evaluate an entire population of a quarter of a million individual programs on a non-trivial problem in 4 seconds. An efficient reverse polish notation (RPN) tree based GP is given.

Download Slides Code download	Bibtex	EuroGP 2008

Fast Genetic Programming on GPUs *Simon Harding and Wolfgang Banzhaf*
As is typical in evolutionary algorithms, fitness evaluation in GP takes the majority of the computational effort. In this paper we demonstrate the use of the Graphics Processing Unit (GPU) to accelerate the evaluation of individuals. We show that for both binary and floating point based data types, it is possible to get speed increases of several hundred times over a typical CPU implementation. This allows for evaluation of many thousands of fitness cases, and hence should enable more ambitious solutions to be evolved using GP.

Download	Bibtex	Euro GP, 2007

Fast Genetic Programming and Artificial Developmental Systems on GPUs *Simon Harding and Wolfgang Banzhaf*
In this paper we demonstrate the use of the Graphics Processing Unit (GPU) to accelerate Evolutionary Computation applications, in particular Genetic Programming approaches. We show that it is possible to get speed increases of several hundred times over a typical CPU implementation, catapulting GPU processing for these applications into the realm of HPC. This increase in performance also extends to artificial developmental systems, where evolved programs are used to construct cellular systems. Feasibility of this approach to efficiently evaluate artificial developmental systems based on cellular automata is demonstrated.

Download	Bibtex	HPCS, 2007

A data parallel approach to genetic programming using programmable graphics hardware *Darren M. Chitty*
In recent years the computing power of graphics cards has increased significantly. Indeed, the growth in the computing power of these graphics cards is now several orders of magnitude greater than the growth in the power of computer processor units. Thus these graphics cards are now beginning to be used by the scientific community as low cost, high performance computing platforms. Traditional genetic programming is a highly computer intensive algorithm but due to its parallel nature it can be distributed over multiple processors to increase the speed of the algorithm considerably. This is not applicable for single processor architectures but graphics cards provide a mechanism for developing a data parallel implementation of genetic programming. In this paper we will describe the technique of general purpose computing using graphics cards and how to extend this technique to genetic programming. We will demonstrate the improvement in the performance of genetic programming on single processor architectures which can be achieved by harnessing the computing power of these next generation graphics cards.

Download	Bibtex	GECCO, 2007