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

Анализ параллельной сложности и масштабируемости OpenMP реализаций матричной модификации метода муравьиных колоний для параметрической оптимизации

Авторы

  • Ю. П. Титов
  • К. А. Кордовер
  • П. А. Жданов
  • А. А. Жданов

Ключевые слова:

метод муравьиных колоний
параметрическая оптимизация
матричный алгоритм
параллельные вычисления
OpenMP
memory-bound
ложное разделение кэша
иерархия памяти
масштабируемость

Аннотация

Статья посвящена разработке и анализу матричной модификации метода муравьиных колоний для задач параметрической оптимизации большой размерности. Теоретически доказано снижение асимптотической сложности с O(K·n²) для канонического метода муравьиных колоний до O(K·n) для матричной модификации, где n — число параметров, K — размер популяции. На основе анализа арифметической интенсивности строго обоснована принадлежность алгоритма к классу memory-bound с пределом ν ≈ 0.44 оп/байт. Экспериментально на 7 процессорах различных архитектур достигнуто ускорение до 10.7 на 18 потоках. Выявлены четыре режима масштабируемости, определяемые иерархией кэш-памяти. Для гибридной архитектуры Intel Alder Lake определены паттерны масштабирования для P- и E-ядер. Предложена блочная модификация алгоритма, обеспечивающая практически линейное ускорение за счет управления L2-резидентностью приватных буферов. Разработаны аналитические соотношения для выбора оптимального числа блоков.


Загрузки

Опубликован

2026-10-01

Выпуск

Том 27 (2026): Выпуск 4.

Раздел

Параллельные программные средства и технологии

Авторы

Ю. П. Титов

Московский авиационный институт (национальный исследовательский университет)

• доцент

К. А. Кордовер

Московский авиационный институт (национальный исследовательский университет)

• заместитель начальника научно-исследовательского отдела

П. А. Жданов

Московский авиационный институт (национальный исследовательский университет)

• программист

А. А. Жданов

Московский авиационный институт (национальный исследовательский университет)

• программист

Библиографические ссылки

  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

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.