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

Аннотация

В данной работе рассматриваются особенности применения параллельных модификаций дискретного метода муравьиных колоний (Ant Colony Optimization, ACO) при дискретизации непрерывных критериев с заданной точностью. Особое внимание уделяется двум ключевым модификациям: ACOCNI и ACOCCyN, которые используют промежуточное хранилище путей муравьев-агентов, реализованное в виде хэш-таблиц с разделением на 3 этапа: подготовка и нормализация матриц; поиск путей популяцией из K муравьев-агентов; испарение весов-феромона и занесение весов-феромона от муравьев-агентов. Важной частью исследования являются структуры параметрического графа, включая декомпозицию на степенные слои, позволяющие проводить дискретизацию. Даются рекомендации по применению высокоуровневых примитив параллелизации (нитей, CUDA GPU, OpenMP и потоков операционной системы) позволяющих осуществлять вычисления по отдельным слоям графа. Количество потоков в таких реализациях определяется по результатам решения задачи дискретной оптимизации (количество потоков максимизируется) с учетом ограничения CPU или GPU и требования кратности числа потоков и количества слоев параметрического графа. Для применения SIMD вычислений с помощью специальных инструкций SSE/AVX и расширенных регистров YMM/XMM требуется изменение алгоритма, так как инструкции осуществляют параллельные операции по внутренним циклам. Для обеспечения кратности 4 ячейкам данных внутренних циклов предложены расширения оптимальной структуры параметрического графа до 100 вершин в одном слое, модификация алгоритма, работающая с транспонированными матрицами на этапе подготовки и нормализации, и специализированный граф с максимальным количеством вершин в одном слое равным 4. Экспериментальные исследования на процессорах включая процессоры AMD Ryzen и Intel Core различных поколений показали, что применение специального графа даёт небольшое преимущество во времени выполнения алгоритма, однако статистически значимые различия наблюдаются только в отдельных случаях. Причина несущественного влияния состоит в том, что время выполнения этапа составляет не более 2% от общего времени выполнения алгоритма.