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 і розповімо про поетапне поліпшення коду. Забігаючи вперед, відзначимо, що наша методика оптимізація дозволила вивести програму на рівні продуктивності і масштабованості, близькі до теоретично можливим.

Про муравьином алгоритмі
Розповімо про алгоритм, який використовується в нашій програмі. Він заснований на поведінці колонії мурашок. Комахи шукають джерела живлення, позначаючи пройдені шляхи феромонами, які залучають інших мурах. З часом феромони випаровуються, тобто, більш довгі шляхи стають менш привабливими, ніж більш короткі, або ті, за якими можна пройти швидко. В результаті, чим коротше або швидше шлях, тим більше мурах він здатний зацікавити, при цьому, кожен з них, проходячи по шляху, робить його ще привабливішим.

На малюнку нижче показаний приклад транспортної мережі. Суцільними лініями відзначені прямі маршрути між вузлами, точковими – непрямі маршрути.


Приклад транспортної мережі

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

Так, в 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 і загальної пам'яті. Однак, такий підхід добре підходить лише для систем з порівняно невеликою кількістю обчислювальних ядер і потоків.

Базова реалізація алгоритму
Ось блок-схема базової архітектури паралельної реалізації мурашиного алгоритму. Саме з неї ми почали експерименти.


Схема неоптимізованого реалізації мурашиного алгоритму

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

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

Результати випробувань базової версії
Один з найшвидших способів з'ясувати, чи ефективно масштабується додаток при збільшенні числа доступних йому обчислювальних ядер, полягає в наступному. Спочатку отримують базовий показник продуктивності на одному процесорі (вузлі NUMA). Потім цей показник порівнюють з результатами вимірювання продуктивності при запуску на декількох процесорах, причому, як із застосуванням технології Hyper-Threading, так і без неї. В ідеальному сценарії, якщо припустити, що продуктивність залежить лише від кількості обчислювальних ядер, система з двома сокетами повинна показати продуктивність, яка вдвічі більше, ніж продуктивність системи з одним.Відповідно, чотири сокета повинні дати чотирикратне зростання продуктивності.

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


Випробування базової неоптимізованого реалізації алгоритму

Це зовсім не те, що нам потрібно, тому настав час дослідити програму з використанням VTune Amplifier.

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

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


Звіт Top Hotspots

Із звіту видно, що додаток витрачає багато часу на послідовне виконання коду, що безпосередньо впливає на паралельне використання ресурсів системи. Найбільш навантажений ділянку програми – це модуль виділення пам'яті із стандартної бібліотеки для роботи з рядками, який не досить добре масштабується при великому числі ядер. Це важлива знахідка. Справа в тому, що OpenMP використовує один спільний пул пам'яті, тому величезна кількість паралельних звернень з різних потоків до конструктору рядків або до модулю виділення пам'яті для об'єктів (з використанням оператора new), роблять пам'ять вузьким місцем. Якщо подивитися на показник СPU Usage, наведений нижче, можна виявити, що додаток, хоча і використовує всі 96 доступних ядер, робить це неефективно, навантажуючи їх лише в коротких проміжках часу.


Використання процесора

Якщо ж поглянути на те, чим зайняті потоки, ми побачимо, що навантаження на них не збалансована.


Незбалансована навантаження

Так, головний потік (Master) в кінці кожного місяця» виконує обчислення, а інші потоки нічого корисного не роблять.

Тепер, після аналізу коду, займемося його оптимізацією.

Оптимізація №1. Спільне використання MPI і OpenMP
Для того, щоб позбутися від великого набору потоків OpenMP, який присутній в базовій реалізації, ми використовували стандартний підхід «головний-підлеглий» і додали в наш додаток ще один рівень паралелізму. А саме, тепер за обчислення в рамках окремих ітерацій відповідають MPI-процеси, що виконуються паралельно, кожен з яких, у свою чергу, містить деяку кількість OpenMP-потоків. Тепер навантаження, пов'язані з виділенням пам'яті під рядка і об'єкти, згруповані за MPI-процесів. Така гібридна MPI-OpenMP реалізація алгоритму ACO показана на блок-схемі нижче.


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

Протестуємо те, що у нас вийшло, з використанням VTune Amplifier

Аналіз оптимізованої реалізації алгоритму з допомогою VTune Amplifier XE
Ми досліджуємо оптимізований варіант програми за тією ж методикою, за якою вивчали його базову версію. На малюнку нижче показаний звіт Top Hotspots, за яким можна судити про те, що тепер програма витрачає менше часу на операції з виділення пам'яті для рядків.


Звіт Top Hotspots

А ось – гістограми використання процесора в базовій (ліворуч) і оптимізованої версії програми.


Гістограми використання процесора

Ось як тепер виглядає завантаження потоків. Видно, що вона збалансована значно краще, ніж раніше.


Збалансована навантаження

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


Використання процесора

На жаль, поки ще занадто багато часу витрачається на очікування в потоках OpenMP і при обміні даними MPI, коли MPI-процес, який знаходить найкраще рішення, надсилає дані головному процесу для оновлення файлу з результатами. Ми припустили, що це відбувається з-за того, що система виявляється перевантажена комунікаційними операціями MPI.

MPI використовує інтерфейс розподіленої пам'яті, при цьому кожен процес працює з окремим пулом пам'яті. В результаті, модифікація об'єктів і структур даних одним процесом не видно іншим, але при цьому дані між процесами повинні передаватися з використанням механізмів MPI Send і Receive. Те ж саме стосується і передачі головному процесу найкращого рішення, знайденого в поточному місяці».

Знайдене глобальне рішення – це складний об'єкт C++, який складається з певної кількості об'єктів похідних класів, розумних покажчиків з даними і інших об'єктів з шаблонів STL. Так як за замовчуванням комунікаційні операції MPI не підтримують обмін складними об'єктами C++, для використання механізмів Send і Receive потрібно серіалізація, в ході якої об'єкти конвертуються в байтові потоки перед відправкою, а потім, після отримання, потоки знову перетворюються в об'єкти.

Навантаження, створювана серіалізацією, постійна. Вона виникає, найбільше, раз у «місяць» (або зовсім не виникає, якщо головний процес, що має ранг 0, знайде найкраще рішення, яке буде визнано глобальною), незалежно від кількості запущених MPI-процесів. Це дуже важливо для того, щоб звести до мінімуму комунікаційні операції MPI при переході до виконання програми на безлічі ядер.

На наведеному вище малюнку додаткові навантаження виділені жовтим (комунікаційні операції MPI) і червоним кольорами (очікування і перевантаження).

Результати оптимізації №1
Гібридна MPI-OpenMP версія програми показала набагато кращі результати в плані балансування навантаження між MPI-процесами і потоками OpenMP. Так само вона продемонструвала набагато більш ефективне використання великої кількості ядер, доступних у системах із процесорами Intel Xeon E7-8890. Ось як виглядають результати тестування поточного варіанту програми в порівнянні з базовим.


Порівняння результатів базової і оптимізованої версії програми

Тут можна бачити, що програма значно краще масштабується при зростанні числа доступних ядер. Зростання продуктивності спостерігається і при включенні Hyper-Threading.
Ми досягли непоганих результатів, але роботи по оптимізації поки не завершені. Скористаємося бібліотекою Intel TBB для подальшого поліпшення продуктивності нашого коду.

Оптимізація №2. Застосування Intel TBB
Вивчаючи найбільш навантажені ділянки коду для гібридної MPI-OpenMP реалізації програми, ми помітили, що значна частка часу виконання все ще припадає на стандартну бібліотеку для роботи з рядками. Ми вирішили перевірити, чи поліпшить ситуацію використання бібліотеки динамічного виділення пам'яті з Intel TBB. Ця бібліотека пропонує кілька шаблонів виділення пам'яті, які схожі на стандартний клас std:allocator з STL, крім того, сюди ж входять scalable_allocator і cache_aligned_allocator. Ці шаблони допомагають вирішити дві найважливіші групи проблем паралельного програмування.

Перша група – проблеми масштабування. Вони виникають із-за того, що механізми виділення пам'яті іноді змушені конкурувати за єдиний загальний пул, причому, з-за вихідного послідовного пристрою програми, за один раз пам'ять може виділити лише один потік.

Друга група проблем пов'язана із загальним доступом до ресурсів. Наприклад, можлива ситуація, коли два потоку намагаються отримати доступ до різних словами одного і того ж рядка кеша. Так як найменша одиниця обміну інформацією між процесорними кэшами – це рядок, що вона буде передаватися між процесорами навіть тоді, коли кожен з них працює з різними словами в рядку. Помилковий загальний доступ здатний пошкодити продуктивності, так як переміщення рядка кеша може займати сотні тактових циклів.

Особливості роботи з Intel TBB
Один з найпростіших способів з'ясувати, чи піде додатком на користь використання Intel TBB, полягає в заміні стандартної функції динамічного виділення пам'яті на функцію бібліотеки Intel TBB libtbbmalloc_proxy.so.2. Для цього достатньо завантажити бібліотеку при запуску програми використовуючи змінну оточення LB_PRELOAD (не змінюючи виконуваний файл) або зв'язати виконуваний файл з бібліотекою.

Настройка зв'язку файлу з бібліотекою: 
-ltbbmalloc_proxy
Встановлення змінної оточення LD_PRELOAD для завантаження бібліотеки
$ export LD_PRELOAD=libtbbmalloc_proxy.so.2

Результати оптимізації №2
Вирішуючи найважливішу проблему масштабування, що виникає при використанні стандартних механізмів виділення пам'яті, бібліотека динамічного виділення пам'яті з Intel TBB дає додатково 6% продуктивності в порівнянні з гібридною MPI-OpenMP версією програми.


Поліпшення продуктивності в результаті використання Intel TBB

Оптимізація №3. Пошук найкращої комбінації процесів MPI і потоків OpenMP
На даному етапі ми вирішили зайнятися дослідженням впливу на продуктивність різних комбінацій процесів MPI і потоків OpenMP при однаковому навантаженні. В експерименті використовувалися всі 192 доступних логічних ядра, тобто, були задіяні 4 процесора і включена технологія Hyper-Threading. В ході випробувань ми виявили оптимальне співвідношення процесів MPI і потоків OpenMP. А саме, найкращого результату вдалося досягти, використовуючи 64 процесу MPI, кожен з яких виконував 3 потоку OpenMP.


Порівняння продуктивності для різних комбінацій процесів MPI і потоків OpenMP.

Підсумки
Дослідження базової паралельної реалізації мурашиного алгоритму дозволило виявити проблеми з масштабуванням, пов'язані з механізмами виділення пам'яті для рядків і конструкторами об'єктів.

Перший етап оптимізації, завдяки застосуванню гібридного підходу, що використовує MPI і OpenMP, дозволив досягти кращого використання ресурсів процесора, що значно підвищило продуктивність. Однак, програма все ще витрачала занадто багато часу на виділення пам'яті.

На другому етапі, завдяки бібліотеці для динамічного виділення пам'яті з Intel TBB, вдалося підвищити продуктивність ще на 6%.

У ході третього етапу поліпшення продуктивності було з'ясовано, що для нашої програми краще всього підходить комбінація з 64 процесів MPI, в кожному з яких виконується по 3 потоку OpenMP. При цьому код добре працює на всіх 192-х логічних ядрах. Ось підсумкові результати оптимізації.


Результати оптимізації

У підсумку, після всіх поліпшень, програма запрацювала 5.3 рази швидше, ніж її базова версія. Вважаємо, це гідний результат, який вартий зусиль, витрачених на дослідження та оптимізацію коду.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.