https://doi.org/10.26089/NumMet.v27r435

Analysis of parallel complexity and scalability of OpenMP implementations of the matrix modification of the ant colony method for parametric optimization

Authors

  • Yurii P. Titov
  • Konstantin A. Kordover
  • Pavel A. Zhdanov
  • Alexander A. Zhdanov

Keywords:

ant colony optimization
parametric optimization
matrix algorithm
parallel computing
OpenMP
memory-bound
false sharing
memory hierarchy
scalability

Abstract

This paper is devoted to the development and analysis of a matrix modification of the ant colony optimization method (Matrix-ACO) for high-dimensional parametric optimization problems. A reduction in asymptotic complexity from O(K·n²) (canonical ACO) to O(K·n), where n is the number of parameters and K is the population size, is theoretically proven. Based on the analysis of arithmetic intensity, the algorithm’s belonging to the memory-bound class with a limit of ν ≈ 0.44 ops/byte is rigorously justified. An acceleration of up to 10.7 times on 18 threads was experimentally achieved on 7 processors of various architectures. Four scalability modes determined by the cache hierarchy are identified. For the Intel Alder Lake hybrid architecture, scaling patterns for P- and E-cores are determined. A block-based modification of the algorithm is proposed, providing nearly linear speedup by controlling the L2 residency of private buffers. Analytical relationships for selecting the optimal number of blocks are developed.


Downloads

Published

2026-10-01

Issue

Vol. 27 (2026): Issue 4.

Section

Parallel software tools and technologies

Authors

Yurii P. Titov

Moscow Aviation Institute - National Research University

• Associate Professor

Konstantin A. Kordover

Moscow Aviation Institute - National Research University

• Deputy Research Department Head

Pavel A. Zhdanov

Moscow Aviation Institute - National Research University

• Programmer

Alexander A. Zhdanov

Moscow Aviation Institute - National Research University

• Programmer

References

  1. A. Colorni, M. Dorigo and M. Vittorio, “Distributed Optimization by Ant Colonies,” Proceedings of the First European Conference on Artificial Life. Paris, France, January 1991 (Elsevier Publishing, 1991), pp. 134–142.
  2. M. Dorigo and L. M. Gambardella, “Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem,” Evolutionary Computation, IEEE Transactions. textbf1.1, 53–66 (1997).
    doi 10.1109/4235.585892
  3. M. Dorigo, V. Maniezzo and A. Colorni, “Positive Feedback as a Search Strategy,” In Technical Report 91-016, Politecnico di Milano, Italy, 1991.
  4. L. M. Gambardella and M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem,” In Machine Learning Proceedings 1995, Morgan Kaufmann , pp. 252–260.
    doi 10.1016/B978-1-55860-377-6.50039-6
  5. B. Bullnheimer, R. F. Hartl and C. Strauss, “Applying the Ant System to the Vehicle Routing Problems,” Annals of Operations Research. 79, 109–123 (1998).
    doi 10.1007/978-1-4615-5775-3_20
  6. T. Stützle and H. H. Hoos, “MAX–MIN Ant System,” Future Generation Computer Systems. 16 (8), 889–914 (2000).
    doi 10.1016/S0167-739X(00)00043-1
  7. O. G. Cordon, I. F. de Viana, and F. Herrera, “Analysis of the Best-Worst Ant System and Its Variants on the QAP,” Proc. in Third International Workshop, ANTS 2002, M. Dorigo, G. Di Caro, M. Sampels (eds), Brussels, Belgium, September 12–14, 2002(Springer Berlin Heidelberg, 2002), pp. 228–234.
    doi 10.1007/3-540-45724-0_20
  8. M. Randall, A. A. Lewis, “A Parallel Implementation of Ant Colony Optimization,” Journal of Parallel and Distributed Computing. 62 (9), 1421–1432 (2002).
    doi 10.1006/jpdc.2002.1854
  9. M. Dorigo, T. Stützle, Ant Colony Optimization(MIT Press, Cambridge, Massachusetts, 2004).
  10. H. Bai, D. OuYang, X. Li, at al., “MAXMIN Ant System on GPU with CUDA,” In 2009 Fourth International Conference on Innovative Computing, Information and Control (ICICIC), Kaohsiung, Taiwan, December 7–9, 2009 (IEEE Computer Society), pp. 801–804.
    doi 10.1109/ICICIC.2009.255
  11. D. M. Chitty, “Applying ACO to Large Scale TSP Instances,” In: F. Chao et al. (Eds.) Advances in Computational Intelligence Systems. UKCI 2017 (Intelligent Systems and Computing, Springer, Cham), 650 (2018).
    doi 10.1007/978-3-319-66939-7_9
  12. R. Skinderowicz, “The GPU-based parallel Ant Colony System,” Journal of Parallel and Distributed Computing. 98, 48–60 (2016).
    doi 10.1016/j.jpdc.2016.04.014
  13. D. Zhang, X. You, S. Liu, K. Yang,” Multi-Colony Ant Colony Optimization Based on Generalized Jaccard Similarity Recommendation Strategy,” IEEE Access. 7, 157303-157317 (2019).
    doi 10.1109/ACCESS.2019.2949860
  14. R. Skinderowicz,” Implementing a GPU-based parallel MAX–MIN Ant System,” Future Generation Computer Systems. 106, 277–295 (2020).
    doi 10.1016/j.future.2020.01.011
  15. Z. B. Huan, G. T. Fu, T. H. Fa, at al.,” High Performance Ant Colony System Based on GPU Warp Specialization with a Static-Dynamic Balanced Candidate Set Strategy,” Future Generation Computer Systems. 125, 136–150 (2021).
    doi 10.1016/j.future.2021.06.041
  16. I. N. Sinitsyn, Y. P. Titov,” Control of Set of System Parameter Values by the Ant Colony Method,” Autom. Remote Control, 84, 893–903 (2023).
    doi 10.1134/S0005117923080106
  17. V. Sudakov, Y. Titov,” Matrix-Based ACO for Solving Parametric Problems Using Heterogeneous Reconfigurable Computers and SIMD Accelerators,” Mathematics, 13 (1284), (2025).
    doi 10.3390/math13081284
  18. V. A. Sudakov, Y. P. Titov,” Investigation of the Parametric Graph Model in the Ant Colony Method,” Math. Models Comput. Simul. 17, 126–136 (2025).
    doi 10.1134/S2070048224700996
  19. I. E. Fedotov, Models of Parallel Programming(SOLON-Press, Moscow, 2012) [in Russian].
  20. V. V. Voevodin and Vl. V. Voevodin, The Parallel Computing(BHV-Petersburg, St. Petersburg, 2002) [in Russian].
  21. I. N. Sinitsyn, Y. P. Titov, “Investigation of algorithms for cyclic search for additional solutions when optimizing the order of hyperparameters by the ant colony method,” High Availability Systems. 19 (1), 59–73 (2023).
    http://radiotec.ru/en/journal/Highly_available_systems/number/2023-1/article/23354 Cited September 21, 2026.
  22. ACO_SIMD/OMP C++ Optimal at main cdot kalengul/ACO_SIMD cdot GitHub,
    https://github.com/kalengul/ACO_SIMD/tree/main/OMP
  23. S. K. Mishra,” Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method,” University Library of Munich, Germany, MPRA Paper. 2718 (2006).
    https://mpra.ub.uni-muenchen.de/2718/ Cited September 21, 2026.
  24. B. N. Chetverushkin, V. A. Sudakov, Y. P. Titov,” Graph Condensation for Large Factor Models,” Dokl. Math. 109, 246–251 (2024).
    doi 10.1134/S1064562424702090

License

Copyright (c) 2026 Ю. П. Титов, К. А. Кордовер , П. А. Жданов, А. А. Жданов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.