Модификации матричного метода муравьиных колоний для параметрической оптимизации с применением GPU с технологией CUDA

Аннотация

Статья посвящена разработке и исследованию матричных модификаций метода муравьиных колоний (ACO) для решения параметрических задач оптимизации с использованием графических процессоров (GPU) на архитектуре CUDA. В отличие от большинства существующих исследований, фокусирующихся на задаче коммивояжера (TSP), предложенный метод специализирован для поиска оптимальных значений независимых параметров, что приводит к иной структуре графа и обуславливает необходимость разработки новых схем распараллеливания. Представлены оригинальные схемы параллелизма, включающие разделение алгоритма на три этапа и введение “параметрического параллелизма по измерениям задачи. Разработаны и протестированы различные стратегии распараллеливания и управления памятью: от базовой модификации MatrixACO-Basic до оптимизированных версий MatrixACO-Optimization (с warp-редукцией и оптимизацией хэш-таблицы) и MatrixACO-Transported (с транспонированным хранением данных). Эксперименты проводились на графических ускорителях NVIDIA Tesla V100 16GB SXM2, платформе Jetson ORIN и различных персональных компьютерах с использованием многомерных тестовых функций. Результаты показывают, что для задачи с 128 параметрами оптимизированная версия MatrixACO-Optimization обеспечивает время обработки одного слоя графа, равное 0.13 мс, что соответствует ускорению более чем в 30 раз по сравнению с оптимизированной CPU-реализацией на основе OpenMP, а в случае задачи с 65536 параметрами способствует ускорению почти в 45 раз. Для задачи с 512 параметрами GPU-реализация демонстрирует на 76% более высокую энергоэффективность по сравнению с CPU-версией, а также почти восьмикратное (в 7.9 раза) снижение Energy-Delay Product. Исследование подтверждает необходимость создания специализированных GPU-реализаций для параметрических задач и выявляет отличную масштабируемость предложенных алгоритмов.