A parallel particle swarm optimization framework based on a fork-join thread pool using a work-stealing mechanism
A parallel particle swarm optimization framework based on a fork-join thread pool using a work-stealing mechanism
复制标题
DOI：
10.1016/j.asoc.2023.110537
复制
发表时间：
2023-09
期刊：
影响因子：
--
通讯作者：
Ming Li;Linhao Huang;Gangyan Xu;Kong Biao
中科院分区：
文献类型：
--
作者：
Ming Li;Linhao Huang;Gangyan Xu;Kong Biao
粒子群优化（PSO）是一种最流行的优化算法，已被采用在各个领域，包括设计，调度和生物化学。但是，该算法在处理高维或多目标优化问题时，计算时间较长。并行粒子群算法被提出来提高其计算效率，并已进行了许多研究。然而，在并行程序设计中很少考虑底层系统设计，这可能对计算效率产生不可忽视的影响，造成底层优化与高层算法设计之间的鸿沟。因此，本文提出了一种基于线程池的多核并行异步粒子群算法（PAPSO）框架，并采用跨层次的方法来弥补这一差距。设计并进行了一系列的实验，以检查如何上述方法可以提高并行执行效率的PSO与OpenMP框架和非并行PSO相比。实验结果表明，PAPSO算法能够显著提高PSO算法的计算效率，与OpenMP算法相比，其优化率接近20%。此外，它实现了高达4.5个线程的近似线性加速。粒子通信实验表明，在不同邻域大小的情况下，非阻塞通信协议能有效地保持计算耗时在同一水平上.最后，工作窃取机制在一般计算场景下平均实现了16%的改进，在不平衡工作负载场景下保持了高达16%的改进。一般来说，本文的主要贡献是，我们创新的线程池管理的概念与fork-join模型的并行PSO充分利用多核CPU的并行计算，通过多线程编程。
Particle Swarm Optimization (PSO) is one of the most popular optimization algorithms that has been adopted in various fields, including design, scheduling, and biochemistry. However, the algorithm is time-consuming when facing high-dimensional or multi-objective optimizing problems. Parallel PSO is thus proposed to improve its computing efficiency, and many studies have been conducted. However, the low-level system design is seldom considered in parallel programming, which may have a nonnegligible impact on computing efficiency, creating a gap between low-level optimization and high-level algorithm design. Therefore, this paper proposes a Parallel Asynchronous PSO (PAPSO) framework based on thread pools utilizing multicore processors and adopts a cross-level approach to bridge the gap. A series of experiments are designed and conducted to examine how the aforementioned method can improve the parallel execution efficiency of PSO compared with the OpenMP framework and nonparallel PSO. Results indicate that PAPSO can significantly improve PSO computing efficiency by reducing the elapsed time, approaching approximately 20% optimization compared with OpenMP. Additionally, it achieves an approximately linear speedup of up to 4.5 threads. In addition, the particle communication experiment shows that the nonblocking communication protocol is effective for maintaining the computing elapsed time in the same level facing different neighborhood sizes. Finally, the work-stealing mechanism achieves an average of 16% improvement for general computing scenarios and maintain up to 16% improvement for imbalanced workload scenarios. Generally, the major contribution of this paper is that we innovate the thread pooling management concept with the fork-join model in parallelizing PSO to make sufficient use of multiple core CPUs for parallel computing through multithread programming.