Two Simple Tricks for Fast Cache-Aware Parallel Particle Swarm Optimization
Jeff Hajewski, Suely Oliveira · 2019
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 parallelization 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.