Page 23 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2016 3rd Student Computer Science Research Conference. Koper: University of Primorska Press, 2016
P. 23
PGPU Implementation of CMA-ES
Aleksandar Tošic´ Matjaž Šuber
Faculty of Mathematics, Natural Sciences and Faculty of Mathematics, Natural Sciences and
Information Technologies Information Technologies
University of Primorska University of Primorska
aleksandar.tosic@upr.si matjaz.suber@student.upr.si
ABSTRACT ES (Covariance Matrix Adaptation Evolution Strategy) is
an evolutionary algorithm for non-linear or non-convex con-
In the last decade, a lot of hope has been put into Gen- tinuous optimization problems. It is considered as state-of-
eral Purpose computing on Graphical Processing Units with the-art in evolutionary computation and has been adopted
optimization algorithms being among the most researched as one of the standard tools for continuous optimization. It
[10, 6, 12, 13]. Unfortunately, the shift in programming is based on the principle of biological evolution, where in
paradigms and computation models makes implementation each iteration new candidate solutions are generated.
of existing algorithms non-trivial. Some algorithms are sim-
ply not suitable for implementation on a single Instruction Choosing the framework was relatively straight forward. Most
Multiple Data (SIMD) model. To overcome the tedious- frameworks are not mature enough or proprietary, hence
ness of programming GPU’s a number of frameworks be- we chose openCl. OpenCL (Open Computing Language) is
came available with Compute Unified Device Architecture the first truly open and royalty-free programming standard
(CUDA) [9] being the most popular proprietary and Open for general-purpose computations on heterogeneous systems.
Computing Language (OpenCL) [8] leading in the field of It allows programmers to preserve their expensive source
open-source frameworks. With the help of OpenCL we im- code investment and easily target multi-core CPUs, GPUs,
plemented the Covariance Matrix Adaptation Evolution Strat- and the new APUs. It improves the speed and responsive-
egy (CMA-ES) [4] in a Metaheuristic Algorithms in Java ness of a wide spectrum of applications. OpenCL is defined
(jMetal) framework [1, 2]. We tested both CPU and OpenCL with four models, namely Platform model, Execution model,
implementations on different hardware configurations and Memory model, and Programming model [3]. The most im-
problem sets available in jMetal. Additionally we explain portant beeing the execution model that deals with the load-
the details of our implementation and show a comparison of ing and executing kernels on the GPU and Memory model,
computation results. handling the allocation of GPU memory and the transfer of
data between host memory and GPU memory.
Keywords
The main challenge is to adapt the kernels and memory
Covariance Matrix Adaptation Evolution Strategy(CMA), models depending on the hardware specifications namely,
Numerical Optimisation, Evolutionary Algorithm, GPGPU, work-group sizes, compute units, etc. In this paper present
jMetal, OpenCL empirical results comparing the standard algorithm with
our GPGPU implementation. Additionally, we show results
1. INTRODUCTION comparing two platforms from different hardware manufac-
turers to eliminate the potential bias of openCl implemen-
Computation on graphics processing units has received a lot tation.
of attention in the past. Mainly because of the availability
of hardware that was driven mostly by the gaming industry 2. IMPLEMENTATION
[7]. As more complex rendering engines were developed, the
need to harness the GPU capabilities grew. Manufacturers The main loop in the CMA-ES algorithm consists of three
gave more access and control over their hardware trough main parts and it runs until termination criterion is met.
frameworks. In the first part the algorithm samples new population of
solutions, for k = 1, ..., λ, in the second part it reorders the
In this paper we present an implementation of a popular sampled solutions based on the fitness function and finally
evolutionary inspired algorithm called CMA-ES. The CMA- it updates the covariance matrix as described in [5].
The execution model defines how the OpenCL environment
is configured on the host and how kernels are executed on the
device. Before a host can request that a kernel is executed
on a device, a context must be configured on the host that
coordinates the host-device interaction and keeps track of
the kernels that are created for each device. Each kernel
contain a unit of code (function) which is executed on a
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 23
Ljubljana, Slovenia, 12 October
Aleksandar Tošic´ Matjaž Šuber
Faculty of Mathematics, Natural Sciences and Faculty of Mathematics, Natural Sciences and
Information Technologies Information Technologies
University of Primorska University of Primorska
aleksandar.tosic@upr.si matjaz.suber@student.upr.si
ABSTRACT ES (Covariance Matrix Adaptation Evolution Strategy) is
an evolutionary algorithm for non-linear or non-convex con-
In the last decade, a lot of hope has been put into Gen- tinuous optimization problems. It is considered as state-of-
eral Purpose computing on Graphical Processing Units with the-art in evolutionary computation and has been adopted
optimization algorithms being among the most researched as one of the standard tools for continuous optimization. It
[10, 6, 12, 13]. Unfortunately, the shift in programming is based on the principle of biological evolution, where in
paradigms and computation models makes implementation each iteration new candidate solutions are generated.
of existing algorithms non-trivial. Some algorithms are sim-
ply not suitable for implementation on a single Instruction Choosing the framework was relatively straight forward. Most
Multiple Data (SIMD) model. To overcome the tedious- frameworks are not mature enough or proprietary, hence
ness of programming GPU’s a number of frameworks be- we chose openCl. OpenCL (Open Computing Language) is
came available with Compute Unified Device Architecture the first truly open and royalty-free programming standard
(CUDA) [9] being the most popular proprietary and Open for general-purpose computations on heterogeneous systems.
Computing Language (OpenCL) [8] leading in the field of It allows programmers to preserve their expensive source
open-source frameworks. With the help of OpenCL we im- code investment and easily target multi-core CPUs, GPUs,
plemented the Covariance Matrix Adaptation Evolution Strat- and the new APUs. It improves the speed and responsive-
egy (CMA-ES) [4] in a Metaheuristic Algorithms in Java ness of a wide spectrum of applications. OpenCL is defined
(jMetal) framework [1, 2]. We tested both CPU and OpenCL with four models, namely Platform model, Execution model,
implementations on different hardware configurations and Memory model, and Programming model [3]. The most im-
problem sets available in jMetal. Additionally we explain portant beeing the execution model that deals with the load-
the details of our implementation and show a comparison of ing and executing kernels on the GPU and Memory model,
computation results. handling the allocation of GPU memory and the transfer of
data between host memory and GPU memory.
Keywords
The main challenge is to adapt the kernels and memory
Covariance Matrix Adaptation Evolution Strategy(CMA), models depending on the hardware specifications namely,
Numerical Optimisation, Evolutionary Algorithm, GPGPU, work-group sizes, compute units, etc. In this paper present
jMetal, OpenCL empirical results comparing the standard algorithm with
our GPGPU implementation. Additionally, we show results
1. INTRODUCTION comparing two platforms from different hardware manufac-
turers to eliminate the potential bias of openCl implemen-
Computation on graphics processing units has received a lot tation.
of attention in the past. Mainly because of the availability
of hardware that was driven mostly by the gaming industry 2. IMPLEMENTATION
[7]. As more complex rendering engines were developed, the
need to harness the GPU capabilities grew. Manufacturers The main loop in the CMA-ES algorithm consists of three
gave more access and control over their hardware trough main parts and it runs until termination criterion is met.
frameworks. In the first part the algorithm samples new population of
solutions, for k = 1, ..., λ, in the second part it reorders the
In this paper we present an implementation of a popular sampled solutions based on the fitness function and finally
evolutionary inspired algorithm called CMA-ES. The CMA- it updates the covariance matrix as described in [5].
The execution model defines how the OpenCL environment
is configured on the host and how kernels are executed on the
device. Before a host can request that a kernel is executed
on a device, a context must be configured on the host that
coordinates the host-device interaction and keeps track of
the kernels that are created for each device. Each kernel
contain a unit of code (function) which is executed on a
StuCoSReC Proceedings of the 2016 3rd Student Computer Science Research Conference 23
Ljubljana, Slovenia, 12 October
