Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Старооскольский технологический институт им. А.А. Угарова

(филиал) федерального государственного автономного

образовательного учреждения высшего образования «Национальный исследовательский университет «МИСиС»

Кафедра АИСУ

Реферат на тему:

«Муравьиные алгоритмы в решении задач оптимизации»

Проверил:

Д.т.н. Еременко Ю.И.

Старый Оскол - 2017г.

ОГЛАВЛЕНИЕ

• ВВЕДЕНИЕ
• 1. РЕШАЕМАЯ ЗАДАЧА
• 2. О МУРАВЬИНОМ АЛГОРИТМЕ
• 3. БАЗОВАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА
• 4. РЕЗУЛЬТАТЫ ИСПЫТАНИЙ БАЗОВОЙ ВЕРСИИ
• 5. ОПТИМИЗАЦИЯ №1
• 6. РЕЗУЛЬТАТЫ ОПТИМИЗАЦИИ №1
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


ВВЕДЕНИЕ

Алгоритмы муравья или оптимизация по принципу муравьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго), обладает специфическим свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве.[1] Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 90-х годов. На сегодняшний день уже получены хорошие результаты для оптимизации таких сложных комбинаторных задач, как задача коммивояжера, задача оптимизации маршрутов грузовиков, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых графиков, задача календарного планирования и многие другие.

Цель задачи добиться эффективной работы программы на компьютере с четырьмя процессорами 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 и улучшении кода.

2. О МУРАВЬИНОМ АЛГОРИТМЕ

Алгоритм в программе основан на поведении колонии муравьёв. Насекомые ищут источники питания, помечая пройденные пути феромонами, которые привлекают других муравьёв. Со временем феромоны испаряются, то есть, более длинные пути становятся менее привлекательными, чем более короткие, или те, по которым можно пройти быстро. В результате, чем короче или быстрее путь, тем больше муравьёв он способен заинтересовать, при этом, каждый из них, проходя по пути, делает его ещё привлекательнее.

На рисунке ниже показан пример транспортной сети. Сплошными линиями отмечены прямые маршруты между узлами, точечными - непрямые маршруты.

Пример транспортной сети

Простые компьютерные агенты способны, используя вероятностный подход, находить решения транспортных задач с использованием муравьиного алгоритма. Параллельные реализации этого алгоритма, отличающиеся, однако, некоторыми ограничениями, уже были исследованы в прошлом.

Так, в 2002-м году Маркус Рэндалл с соавторами опубликовал материал (A Parallel Implementation of Ant ColonyOptimization, Journal of Parallel and Distributed Computing 62), в котором показан подход к распараллеливанию задачи, приведший к приемлемому ускорению вычислений. Однако, в данной реализации для поддержания матрицы феромонов требовалось большое количество взаимодействий между «муравьями», которые действовали параллельно, при этом каждый из них был самостоятельной единицей модели. В результате производительность решения оказалась ограничена интерфейсом передачи сообщений (Message Passing Interface, MPI) между «муравьями».

В 2015-м был опубликован материал (Veluscek, M., T. Kalganova, P. Broomhead, A. Grichnik, Composite goal methods for transportation network optimization, Expert Systems with Applications 42), в котором описана методика оптимизации транспортной сети с использованием технологии OpenMP и общей памяти. Однако, такой подход хорошо подходит лишь для систем со сравнительно небольшим числом вычислительных ядер и потоков.

компьютер муравьиный алгоритм

3. БАЗОВАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА

Вот блок-схема базовой архитектуры параллельной реализации муравьиного алгоритма. Именно с неё начались эксперименты.

Схема неоптимизированной реализации муравьиного алгоритма

На этой схеме показано, как каждый «месяц» запускается множество итеративных процессов. В каждом из них в сеть «выпускают» группу «муравьёв», которые строят матрицы феромонов. Каждый итеративный процесс полностью независим, он исполняется в собственном потоке.

Здесь используется статическое распределение заданий, каждый поток OpenMP выполняет свою часть работы, находя локальное решение. После того, как все потоки завершат исполнение, главный поток сравнивает найденные ими локальные решения и выбирает лучшее, которое становится глобальным.

4. РЕЗУЛЬТАТЫ ИСПЫТАНИЙ БАЗОВОЙ ВЕРСИИ

Один из самых быстрых способов выяснить, эффективно ли масштабируется приложение при увеличении числа доступных ему вычислительных ядер, заключается в следующем. Сначала получают базовый показатель производительности на одном процессоре . Затем этот показатель сравнивают с результатами измерения производительности при запуске на нескольких процессорах, причём, как с применением технологии Hyper-Threading, так и без неё. В идеальном сценарии, если предположить, что производительность зависит лишь от числа вычислительных ядер, система с двумя сокетами должна показать производительность, которая вдвое больше, чем производительность системы с одним. Соответственно, четыре сокета должны дать четырёхкратный рост производительности.

На рисунке ниже можно увидеть результаты испытаний базовой версии приложения. Сейчас наш код далёк от идеала. После того, как число сокетов превысило два (48 ядер), программа масштабируется не слишком хорошо. На четырёх же сокетах с включенной технологией Hyper-Threading (192 логических ядра) производительность даже ниже чем при использовании одного сокета.

Испытание базовой неоптимизированной реализации алгоритма

Анализ базовой реализации алгоритма с помощью VTune Amplifier XE

Для того, чтобы выяснить, что же мешает приложению нормально работать на нескольких процессорах, мы воспользуемся Hotspot-анализом VTune Amplifier XE 2016. Будем искать наиболее нагруженные участки программы. При проведении замеров в VTune Amplifier использовалась уменьшенная рабочая нагрузка (384 итеративных процесса) для того, чтобы ограничить размер собираемых данных.

На рисунке ниже показан отчёт VTune. В частности, нас интересуют показатели в группе Top Hotspots и показатель Serial Time, который позволяет узнать время, приходящееся на последовательное исполнение кода.

Отчёт Top Hotspots

Из отчёта видно, что приложение тратит много времени на последовательное исполнение кода, что напрямую воздействует на параллельное использование ресурсов системы. Самый нагруженный участок программы - это модуль выделения памяти из стандартной библиотеки для работы со строками, который не масштабируется достаточно хорошо при большом числе ядер. Это важная находка. Дело в том, что OpenMP использует один разделяемый максимальный кусок памяти, поэтому огромное количество параллельных обращений из разных потоков к конструктору строк или к модулю выделения памяти для объектов, делают память узким местом. Если посмотреть на показатель СPU Usage, приведённый ниже, можно обнаружить, что приложение, хотя и использует все 96 доступных ядер, делает это неэффективно, нагружая их лишь в коротких промежутках времени.

Использование процессора

Если же взглянуть на то, чем заняты потоки, мы увидим, что нагрузка на них не сбалансирована.

Несбалансированная нагрузка

Так, главный поток (Master) в конце каждого «месяца» выполняет вычисления, а остальные потоки ничего полезного в это время не делают.

Теперь, после анализа кода, займёмся его оптимизацией.

5. ОПТИМИЗАЦИЯ №1.

Для того, чтобы избавиться от большого набора потоков OpenMP, который присутствует в базовой реализации, мы использовали стандартный подход «главный-подчинённый» и добавили в наше приложение ещё один уровень параллелизма. А именно, теперь за вычисления в рамках отдельных итераций отвечают MPI-процессы, исполняемые параллельно, каждый из которых, в свою очередь, содержит некоторое количество OpenMP-потоков. Теперь нагрузки, связанные с выделением памяти под строки и объекты, распределены по MPI-процессам. Такая гибридная MPI-OpenMP реализация алгоритма ACO показана на блок-схеме ниже.

Оптимизированная реализация №1

Протестируем то, что у нас получилось, с использованием VTune Amplifier. Мы исследуем оптимизированный вариант приложения по той же методике, по которой изучали его базовую версию. На рисунке ниже показан отчёт Top Hotspots, по которому можно судить о том, что теперь программа тратит меньше времени на операции по выделению памяти для строк.

Отчёт Top Hotspots

Гистограммы использования процессора

Вот как теперь выглядит загрузка потоков. Видно, что она сбалансирована значительно лучше, чем ранее.

На рисунке ниже можно видеть, что все доступные 96 ядер загружены практически полностью.

6. РЕЗУЛЬТАТЫ ОПТИМИЗАЦИИ №1

Гибридная MPI-OpenMP версия программы показала гораздо лучшие результаты в плане балансировки нагрузки между MPI-процессами и потоками OpenMP. Так же она продемонстрировала гораздо более эффективное использование большого числа ядер, доступных в системах с процессорами Intel Xeon E7-8890. Вот как выглядят результаты тестирования текущего варианта программы в сравнении с базовым.

Сравнение результатов базовой и оптимизированной версий программы

Здесь можно видеть, что программа значительно лучше масштабируется при росте числа доступных ядер. Рост производительности наблюдается и при включении Hyper-Threading.

ЗАКЛЮЧЕНИЕ

Исследование базовой параллельной реализации муравьиного алгоритма позволило выявить проблемы с масштабированием, связанные с механизмами выделения памяти для строк и конструкторами объектов.

Первый этап оптимизации, благодаря применению гибридного подхода, использующего MPI и OpenMP, позволил достичь лучшего использования ресурсов процессора, что значительно повысило производительность.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Интеллектуальные системы принятия решений и управления/Еременко Ю.И.-Старый Оскол: ООО Оскольская Типография ,2010.-183 с.

2.Введение в OpenMP [Электронный ресурс]. // URL: https://software.intel.com/ru-ru/blogs/2011/11/21/openmp-c

3. 96 вычислительных ядер и оптимизация кода муравьиного алгоритма поиска маршрутов [Электронный ресурс] URL: https://habrahabr.ru/company/intel/blog/311618/

Размещено на Allbest.ru