EvoApplications 2012 EvoPAR Abstracts

A Fair Comparison of Modern CPUs and GPUs Running the Genetic Algorithm under the Knapsack Benchmark

Jiri Jaros, Petr Pospochal

The paper introduces an optimised multicore CPU implementation of the genetic algorithm and compares its performance with a fine-tuned GPU version. The main goal is to show the true performance relation between modern CPUs and GPUs and eradicate some of myths surrounding GPU performance. It is essential for the evolutionary community to provide the same conditions and designer effort to both implementations when benchmarking CPUs and GPUs. Here we show the performance comparison supported by architecture characteristics narrowing the performance gain of GPUs.

Validating a Peer-to-Peer Evolutionary Algorithm

Juan Luis Jimenez Laredo, Pascal Bouvry, Sanaz Mostaghim, Juan-J Merelo-Guervos

We propose a simple experiment for validating a Peer-to-Peer Evolutionary Algorithm in a real computing infrastructure in order to verify that results meet those obtained by simulations. The validation method consists of conducting a well characterised experiment in a large computer cluster of up to a number of processors equal to the population estimated by the simulator. We argue that the validation stage is usually missing in the design of large-scale distributed meta-heuristics given the difficulty of harnessing a large number of computing resources. That way, most of the approaches in the literature focus on studying the model viability throughout a simulation-driven experimentation. However, simulations assume idealistic conditions that can influence the algorithmic performance and bias results when conducted in a real platform. Therefore, we aim at validating simulations by running a real version of the algorithm. Results show that the algorithmic performance is rather accurate to the predicted one whilst times-to-solutions can be drastically decreased when compared to the estimation of a sequential run.

OpenCL Implementation of Particle Swarm Optimization: A Fair Comparison between CPU and GPU Performances

Stefano Cagnoni, Alessandro Bacchini, Luca Mussi

GPU-based parallel implementations of algorithms are usually compared against the corresponding sequential versions compiled for a single-core CPU machine, without taking advantage of the multi-core and SIMD capabilities of modern processors. This leads to unfair comparisons, where speed-up figures are much larger than what could actually be obtained if the CPU-based version were properly parallelised and optimised. The availability of OpenCL, which compiles parallel code for both GPUs and multi-core CPUs, has made it much easier to compare execution speed of different architectures fully exploiting each architecture's best features. We tested our latest parallel implementations of Particle Swarm Optimisation (PSO), compiled under OpenCL for both GPUs and multicore CPUs, and separately optimised for the two hardware architectures. Our results show that, for PSO, a GPU-based pluralisation is still generally more efficient than a multi-core CPU-based one. However, the speed-up obtained by the GPU-based with respect to the CPU-based version is by far lower than the orders-of-magnitude figures reported by the papers which compare GPU-based parallel implementations to basic single-thread CPU code.

FlexGP: Genetic Programming on the Cloud

Dylan Sherry, Kalyan Veeramachaneni, James McDermott, Una-May O'Reilly

We describe FlexGP, which we believe to be the first large-scale genetic programming cloud computing system. We took advantage of existing software and selected a socket based, client-server architecture and an island-based distribution model. We developed core components required for deployment on Amazon's Elastic Compute Cloud. Scaling the system to hundreds of nodes presented several unexpected challenges and required the development of software for automatically managing deployment, reporting, and error handling. The system's performance was evaluated on two metrics, performance and speed, on a difficult symbolic regression problem. Our largest successful FlexGP runs reached 350 nodes and taught us valuable lessons for the next phase of scaling.

Migration and Replacement Policies for Preserving Diversity in Dynamic Environments

David Millan-Ruiz, Jose Ignacio Hidalgo

We resolve the difficulties arising from the configuration and fine-tuning of a Parallel Genetic Algorithm (PGA) based on the Island Model, when the application domain is highly dynamic. This way, the reader will find a number of useful guidelines for setting up a PGA in a real, representative dynamic environment. To achieve this purpose, we examine different (existing and new) migration and replacement policies for three different topologies. Of course, there are many other factors that affect the performance of a PGA such as the topology, migrant selection, migration frequency, amount of migrants, replacement policy, number of processing nodes, synchronism type, configuration in the isolated islands, diversity of policies in different islands, etc which are also considered as a part of this study. The pivotal point of all the experiments conducted is the preservation of diversity by means of an appropriate balance between exploration and exploitation in the PGA's search process when the application domain is highly dynamic and strong time constraints arise. The experimental phase is performed over two problem instances from a real-world dynamic environment which is the multi-skill call centre.

Distributed Simulated Annealing with MapReduce

Atanas Radenski

Simulated annealing's high computational intensity has stimulated researchers to experiment with various parallel and distributed simulated annealing algorithms for shared memory, message-passing, and hybrid-parallel platforms. MapReduce is an emerging distributed computing framework for large-scale data processing on clusters of commodity servers; to our knowledge, MapReduce has not been used for simulated annealing yet. We investigate the applicability of MapReduce to distributed simulated annealing in general, and to the TSP in particular. We (i) design six algorithmic patterns of distributed simulated annealing with MapReduce, (ii) instantiate the patterns into MR implementations to solve a sample TSP problem, and (iii) evaluate the solution quality and the speedup of the implementations on a cloud computing platform, Amazon's Elastic MapReduce. Some of our patterns integrate simulated annealing with genetic algorithms. The paper can be beneficial for those interested in the potential of MapReduce in computationally intensive nature-inspired methods in general and simulated annealing in particular.

Pool-based Distributed Evolutionary Algorithms using an Object Database

Juan-J Merelo-Guervos, Antonio Mora, J. Albert Cruz, Anna I Esparcia

We present the mapping of an evolutionary algorithm to the CouchDB object store. This mapping decouples the population from the evolutionary algorithm, and allows a distributed and asynchronous operation of clients written in different languages. In this paper we present initial tests which prove that the novel algorithm design still performs as an evolutionary algorithm and try to find out what are the main issues concerning it, what kind of speedups should we expect, and how all this affects the fundamentals of the evolutionary algorithm.

A Library to Run Evolutionary Algorithms in the Cloud using MapReduce

Pedro Fazenda, James McDermott, Una-May O'Reilly

We discuss ongoing development of an evolutionary algorithm library to run on the cloud. We relate how we have used the Hadoop open-source MapReduce distributed data processing framework to implement a single "island" with a potentially very large population. The design generalises beyond the current, one-off kind of MapReduce implementations. It is in preparation for the library becoming a modelling or optimisation service in a service oriented architecture or a development tool for designing new evolutionary algorithms.
W.B.Langdon 14 March 2012