LCS & GBML Central

Abstract  General Purpose computing over Graphical Processing Units (GPGPUs) is a huge shift of paradigm in parallel computing that
promises a dramatic increase in performance. But GPGPUs also bring an unprecedented level of complexity in algorithmic design
and software development. In this paper we describe the challenges and design choices involved in parallelizing a hybrid of
Genetic Algorithm (GA) and Local Search (LS) to solve MAXimum SATisfiability (MAX-SAT) problem on a state-of-the-art nVidia
Tesla GPU using nVidia Compute Unified Device Architecture (CUDA). MAX-SAT is a problem of practical importance and is often
solved by employing metaheuristics based search methods like GAs and hybrid of GA with LS. Almost all the parallel GAs (pGAs)
designed in the last two decades were designed for either clusters or MPPs. Unfortunately, very little research is done on
the implementation of such algorithms over commodity graphics hardware. GAs in their simple form are not suitable for implementation
over the Single Instruction Multiple Thread (SIMT) architecture of a GPU, and the same is the case with conventional LS algorithms.
In this paper we explore different genetic operators that can be used for an efficient implementation of GAs over nVidia GPUs.
We also design and introduce new techniques/operators for an efficient implementation of GAs and LS over such architectures.
We use nVidia Tesla C1060 to perform several numerical tests and performance measurements and show that in the best case we
obtain a speedup of 25×. We also discuss the effects of different optimization techniques on the overall execution time.

Abstract  Parallel and distributed methods for evolutionary algorithms have concentrated on maintaining multiple populations of genotypes,
where each genotype in a population encodes a potential solution to the problem. In this paper, we investigate the parallelisation
of the genotype itself into a collection of independent chromosomes which can be evaluated in parallel. We call this multi-chromosomal evolution
(MCE). We test this approach using Cartesian Genetic Programming and apply MCE to a series of digital circuit design problems
to compare the efficacy of MCE with a conventional single chromosome approach (SCE). MCE can be readily used for many digital
circuits because they have multiple outputs. In MCE, an independent chromosome is assigned to each output. When we compare
MCE with SCE we find that MCE allows us to evolve solutions much faster. In addition, in some cases we were able to evolve
solutions with MCE that we unable to with SCE. In a case-study, we investigate how MCE can be applied to to a single objective
problem in the domain of image classification, namely, the classification of breast X-rays for cancer. To apply MCE to this
problem, we identify regions of interest (RoI) from the mammograms, divide the RoI into a collection of sub-images and use
a chromosome to classify each sub-image. This problem allows us to evaluate various evolutionary mutation operators which
can pairwise swap chromosomes either randomly or topographically or reuse chromosomes in place of other chromosomes.

Abstract  The availability of low cost powerful parallel graphics cards has stimulated the port of Genetic Programming (GP) on Graphics
Processing Units (GPUs). Our work focuses on the possibilities offered by Nvidia G80 GPUs when programmed in the CUDA language.
In a first work we have showed that this setup allows to develop fine grain parallelization schemes to evaluate several GP
programs in parallel, while obtaining speedups for usual training sets and program sizes. Here we present another parallelization
scheme and optimizations about program representation and use of GPU fast memory. This increases the computation speed about
three times faster, up to 4 billion GP operations per second. The code has been developed within the well known ECJ library
and is open source.