Матричная модификация метода муравьиных колоний с применением AVX-инструкций SIMD-процессоров для решения параметрических задач
Вестник Самарского государственного технического университета. Серия «Физико-математические науки» · 2026 · 30 (1) · 203-224
DOI: 10.14498/vsgtu2250 ↗Kurz gefasst
Fachartikel in der Zeitschrift Вестник Самарского государственного технического университета. Серия «Физико-математические науки», online erschienen am 10.03.2026. Verfasst von Vladimir Anatolievich Sudakov und 1 weiteren Autor:innen. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Analytical Center for the Government of the Russian Federation.
Abstract (Originalsprache)
Работа посвящена исследованию модификации метода муравьиных колоний (ACO) для решения параметрических задач. Рассматриваемый метод основан на поиске пути муравьями-агентами в параметрическом графе, где вершины соответствуют значениям параметров, а путь определяет результирующий набор значений. Предложенная матричная модификация ACO позволяет представить алгоритм в виде матричных преобразований с преимущественным использованием циклов фиксированной длины. Оптимальная структура графа предполагает разделение значений каждого параметра на слои с максимальным числом вершин в слое, равным пяти. Для ускорения вычислений предлагается использовать AVX-инструкции центрального процессора во внутренних циклах. Однако при пяти вершинах в слое применение AVX-инструкций неэффективно, поскольку требует кратности числа вершин четырем. В связи с этим разработана транспонированная модификация матричного метода, ориентированная на графы, содержащие 100 и более вершин в слое, что позволяет эффективно задействовать AVX-инструкции. Исследование предложенных модификаций выполнялось на различных аппаратных платформах, включая процессоры Intel и AMD. Установлено, что процессоры Intel 12-го и 13-го поколений более чем в два раза превосходят по производительности процессоры 8-го и 9-го поколений. Процессор AMD демонстрирует высокую эффективность при выполнении классического ACO, но уступает процессорам Intel при использовании матричных модификаций. Проанализированы различные структуры графов с числом вершин в слое 100, 1000 и 10000, решающих одну и ту же задачу. Наибольшую эффективность показала матричная модификация ACO с применением AVX-инструкций и директив OpenMP: время выполнения 500 итераций для 500 муравьев-агентов составляет 5--6 мс в расчете на один параметр. Различные матричные модификации демонстрируют близкие результаты, что объясняется высокой ресурсоемкостью поиска путей муравьями-агентами, который сложно поддается векторизации с помощью AVX.
Förderung
- Analytical Center for the Government of the Russian Federation
Zitieren
APA
Sudakov, V. A., & Titov, Y. P. (2026). Матричная модификация метода муравьиных колоний с применением AVX-инструкций SIMD-процессоров для решения параметрических задач. Вестник Самарского государственного технического университета. Серия «Физико-математические науки», 30(1), 203-224. https://doi.org/10.14498/vsgtu2250
Vancouver
Sudakov VA, Titov YP. Матричная модификация метода муравьиных колоний с применением AVX-инструкций SIMD-процессоров для решения параметрических задач. Вестник Самарского государственного технического университета. Серия «Физико-математические науки». 2026;30(1):203-224. doi:10.14498/vsgtu2250
BibTeX
@article{Sudakov2026,
author = {Sudakov, Vladimir Anatolievich and Titov, Yurii Pavlovich},
title = {Матричная модификация метода муравьиных колоний с применением AVX-инструкций SIMD-процессоров для решения параметрических задач},
journal = {Вестник Самарского государственного технического университета. Серия «Физико-математические науки»},
year = {2026},
volume = {30},
number = {1},
pages = {203--224},
doi = {10.14498/vsgtu2250}
}
EUVIMED