96 вычислительных ядер и оптимизация кода муравьиного алгоритма поиска маршрутов
Сегодня поговорим об оптимизации кода, который реализует муравьиный алгоритм нахождения оптимальных путей на графах. Узкие места в программе будем искать с помощью
Intel VTune Amplifier XE 2016 Update 2, а оптимизировать с использованием
MPI, OpenMP и библиотеки Intel Threading Building Blocks.
Наша цель заключается в том, чтобы добиться эффективной работы программы на компьютере с четырьмя процессорами
Intel Xeon E7-8890 v4. Система оснащена 512 Гб оперативной памяти, на ней установлена Linux 3.10.0-327.el7.x86_64, код компилировался с помощью Intel Parallel Studio XE 2016 U2.
Проблема поиска оптимального маршрута в транспортной сети известна как «задача коммивояжёра». На практике это, например, нахождение оптимальных путей перевозок товаров. Изначально «эффективность» в задачах такого рода означала выбор наиболее дешёвого пути, но за последние несколько десятилетий понятие «стоимость маршрута» расширилось. Теперь сюда включают и воздействие на окружающую среду, и цену энергоресурсов, и время. В дополнение к этому, глобализация бизнеса и цепочек поставок привели к тому, что размеры и сложность транспортных сетей, а значит – и моделей, на которых базируются расчёты, значительно выросли. Теперь типичные задачи оптимизации маршрутов классифицируют как НП-трудные. Обычно для решения таких задач не подходят детерминированные методы.
С развитием распределённых и многоядерных вычислительных систем были разработаны и успешно применены эвристические методы решения задач, в частности – так называемый муравьиный алгоритм (Ant Colony Optimization, ACO). Сейчас мы рассмотрим процесс анализа базовой реализации ACO и расскажем о поэтапном улучшении кода. Забегая вперёд, отметим, что наша методика оптимизация позволила вывести программу на уровни производительности и масштабируемости, близкие к теоретически достижимым.
Подробнее