CUDA and OpenCL-based asynchronous PSO
Youssef S. G. Nashed, Alessandro Bacchini, Stefano Cagnoni, Luca Mussi · 2011
In ‘synchronous ’ PSO, positions and velocities of all particles are updated in turn in each ‘generation’, after which each particle’s new fitness is evaluated. The value of the social attractor is only updated at the end of each generation, when the fitness values of all particles are known. The ‘asynchronous ’ version of PSO, instead, allows the social attractors to be updated immediately after evaluating each particle’s fitness, which causes the swarm to move more promptly towards newly-found optima. In asynchronous PSO, the velocity and position update equations can be applied to any particle at any time, in no specific order. The most common GPU implementations of PSO assign one thread per particle and do not take full advantage of the GPU power in evaluating the fitness function in parallel. Parallelization only occurs on the number of particles of a swarm and ignores the dimensions of the function. In our parallel implementations: (i) we designed the thread parallelization to be as fine-grained as possible, considering that, in PSO, velocity and position update occur independently over each dimension; (ii) we implemented an ’asynchronous ’ PSO which, despite updating all particles in parallel, allows each of them to update the social attractor without waiting for all other particles ’ fitness values to be evaluated. A block diagram representing the GPU execution of our parallel asynchronous PSO is shown in Figure 1. 1.1 Synchronous CUDA-PSO The synchronous implementation [4] we previously developed using CUDA comprises three stages (kernels), namely: positions update, fitness evaluation, and bests update, implemented as three CUDA kernels which must be executed sequentially; synchronization occurs at the end of each kernel run. While allowing for virtually any swarm size, this implementation requires synchronization points where all the particles ’ data has to be saved into slow global memory to be read by the next kernel. This frequent access to global memory has been the main justification behind the asynchronous implementation.