EUVIMEDEUVIMED entdecken
Crossref

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

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

Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie) · 01.10.2026 · 27 (4) · 559-584

DOI: 10.26089/nummet.v27r435 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), online erschienen am 01.10.2026. Verfasst von Yurii P. Titov und 3 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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

Zitieren

APA

Titov, Y. P., Kordover, K. A., Zhdanov, P. A., & Zhdanov, A. A. (2026). Analysis of parallel complexity and scalability of OpenMP implementations of the matrix modification of the ant colony method for parametric optimization. Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie), 27(4), 559-584. https://doi.org/10.26089/nummet.v27r435

Vancouver

Titov YP, Kordover KA, Zhdanov PA, Zhdanov AA. Analysis of parallel complexity and scalability of OpenMP implementations of the matrix modification of the ant colony method for parametric optimization. Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie). 2026;27(4):559-584. doi:10.26089/nummet.v27r435

BibTeX
@article{Titov2026,
  author = {Titov, Yurii P. and Kordover, Konstantin A. and Zhdanov, Pavel A. and Zhdanov, Alexander A.},
  title = {Analysis of parallel complexity and scalability of OpenMP implementations of the matrix modification of the ant colony method for parametric optimization},
  journal = {Numerical Methods and Programming (Vychislitel'nye Metody i Programmirovanie)},
  year = {2026},
  volume = {27},
  number = {4},
  pages = {559--584},
  doi = {10.26089/nummet.v27r435}
}
Kostenlos starten →