EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Матричная модификация метода муравьиных колоний с применением AVX-инструкций SIMD-процессоров для решения параметрических задач

Vladimir Anatolievich Sudakov, Yurii Pavlovich Titov

Вестник Самарского государственного технического университета. Серия «Физико-математические науки» · 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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →