Logo image
Back
Two Simple Tricks for Fast Cache-Aware Parallel Particle Swarm Optimization
Conference proceeding

Two Simple Tricks for Fast Cache-Aware Parallel Particle Swarm Optimization

Jeff Hajewski and Suely Oliveira
2019 IEEE Congress on Evolutionary Computation (CEC), pp.1374-1381
06/2019
DOI: 10.1109/CEC.2019.8790219

View Online

Abstract

Particle Swarm Optimization is an example of a trivially parallelizable algorithm where good performance gains can be achieved through the use of a few OpenMP pragmas. Writing an efficient parallel PSO algorithm, however, is much more challenging because although particle updates can occur independently, they rely on a shared global state (the globally best particle). The difficulty of maintaining this global state can be seen in the large body of work studying the parallelization of PSO - almost uniformly these algorithms rely on a global synchronization step, which can result in idle cores and reduced parallel efficiency. In this work, we explore two techniques for implementing a fast, cache-aware parallel PSO algorithm: batching the creation of the random weights and reducing critical section contention via a relaxed consistency guarantee. Our technique shows impressive performance improvements over prior work, seeing more than 60% speed-up over naive paral-lelization and more than 10% speed-up over the cache-aware algorithm. This speed comes at a cost; while our method quickly reaches an approximate solution, it struggles in environments requiring a high level of resolution. Despite these trade-offs, our method is both easy to understand and implement and is widely transferable to other swarm intelligence algorithms.
 Convergence Data Oriented Design Graphics processing units Message passing Message systems Parallel processing Parallel PSO Particle swarm optimization Writing

Details

Metrics

4 Record Views
Logo image