Many-Threaded Differential Evolution on the GPU
Differential evolution (DE) is an efficient populational meta-heuristic optimization algorithm that has been applied to many difficult real-world problems. Due to the relative simplicity of its operations and real-encoded data structures, it is very suita
- PDF / 929,254 Bytes
- 27 Pages / 439.36 x 666.15 pts Page_size
- 109 Downloads / 219 Views
tract Differential evolution (DE) is an efficient populational meta-heuristic optimization algorithm that has been applied to many difficult real-world problems. Due to the relative simplicity of its operations and real-encoded data structures, it is very suitable for a parallel implementation on multicore systems and on the GPUs that nowadays reach peak performance of hundreds and thousands of giga FLOPS (floating-point operations per second). In this chapter, we present a simple yet highly parallel implementation of differential evolution on the GPU using the CUDA (Compute Unified Device Architecture) architecture and demonstrate its performance on selected test problems.
1 Introduction Differential evolution (DE) is a popular meta-heuristic optimization algorithm belonging to the wide family of evolutionary algorithms (EAs). As with many other evolutionary algorithms, it aims to solve the optimization problems by a simulated evolution of a population of candidate solutions. The population of candidates evolved by the algorithm performs a massively parallel search through the problem domain towards globally optimal solutions. The candidate solutions can be seen as individual points on the fitness landscape of the solved problem that are iteratively and in many directions at once moved towards promising regions on the fitness landscape. The implicit parallelism of the algorithm makes it even more interesting for an implementation on a truly parallel platform.
P. Kr¨omer () J. Platoˇs V. Sn´asˇel A. Abraham ˇ - Technical University of Ostrava, 17. listopadu 12, Ostrava, IT4Innovations, VSB Czech Republic e-mail: [email protected]; [email protected]; [email protected]; [email protected] S. Tsutsui and P. Collet (eds.), Massively Parallel Evolutionary Computation on GPGPUs, Natural Computing Series, DOI 10.1007/978-3-642-37959-8 7, © Springer-Verlag Berlin Heidelberg 2013
121
122
P. Kr¨omer et al.
In this chapter, we present a fine-grained implementation of DE designed specifically for super parallel SIMD (single-instruction multiple-data) devices such as the GPUs. The SIMD hardware found in the modern day GPUs supports parallel execution of hundreds of threads at the same time and the software drivers and runtime libraries allow efficient scheduling of tens of thousands of threads. General-purpose computing on graphics processing units (GPGPU) can use either commodity hardware such as the GPUs used primarily for computer graphics and entertainment or GPU coprocessors designed to perform massively parallel computations in the first place. This chapter is organized in the following way: in Sect. 2, the basic principles of differential evolution and some of its applications are presented. Section 3 gives a brief overview of GPU computing, the CUDA platform, and recent implementations of differential evolution on GPUs. Many-threaded differential evolution is presented in Sect. 4, and its performance on selected test problems, first reported in [16] and [17], is described in Sect. 5.
2 Differential
Data Loading...
