ЗАСТОСУВАННЯ АНАЛІТИЧНИХ ІНСТРУМЕНТІВ ДЛЯ АВТОМАТИЗАЦІЇ НАЛАШТУВАННЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ



Запропоновано вдосконалення методу самоналаштування (автотьюнінгу) програм з використанням відомих засобів статистичного аналізу з метою пошуку оптимальної версії паралельної програми для конкретної мультипроцесорної платформи. Наведено результати практичного експерименту з налаштуванням паралельного алгоритму сортування.

Ключові слова: Watson Analytics, R, автотьюнінг, статистичне моделювання, паралельні алгоритми

APPLYING ANALYTICAL TOOLS TO AUTOMATE CONFIGURATION OF PARALLEL ALGHORITHM

An improving of self-configuring (auto-tuning) method for programs with using well-known tools of statistical analysis to find the optimal version of the parallel program fora specific multiprocessor platform is offered. Results of practical experiment with tuning of parallel algorithm of sorting are brought.

Keywords: Watson Analytics, R, auto-tuning, statistical modeling, parallel algorithms

Doroshenko A. U. – Prof. in Department ofautomation and Control in Technical Systems, NTUU “KPI”

Novak O. S. – postgraduate, Institute of Software Systems NAS of Ukraine

Ivanenko P. A. – junior research fellow, Institute of Software NAS of Ukraine

Starushyk A. M. – student, NTUU “KPI”

Ukraine, Kiev

Вступ

Питання найвищих показників продуктивності для паралельних програм є першорядним для розробників цього класу програмного забезпечення. Серед засобів для досягнення цієї мети в останні роки помітну роль грає метод налаштування та самоналаштування (автотьюнінгу) [1], що дозволяє автоматизувати цей процес для будь-якого обчислювального середовища. Цей метод простий у застосуванні і не залежить від якісних характеристик обчислювача та його операційної системи. Автотьюнінг використовує емпіричний підхід для отримання якісної оцінки оптимізованої програми. Це дозволяє уникнути складного моделювання виконання прикладної програми. Проте, самоналаштування нетривіальних програм потребує суттєвих часових затрат на проведення експериментальних викликів програми. В цій роботі запропоновано вдосконалення методу самоналаштування програм з використанням відомих засобів статистичного аналізу з метою скорочення пошуку оптимальної версії паралельної програми для конкретної мультипроцесорної платформи. Запропонований підхід полягає у автоматичному навчанні моделі на результатах “традиційних” циклів тьюнінгу й подальшій підміні частини запусків програми оцінкою з апроксимаційної моделі.

Метод автотьюнінгу

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

В цілому дії програми-тюнера є досить шаблонними – обрати/створити нову версію програми й отримати емпіричну оцінку її швидкодії. Тому останній недолік усувається автоматичним генеруванням автотьюнера з вихідного коду оптимізованої програми, що є характерною рисою розробленої авторами програмної системи автотьюнінгу TuningGenie (детально описана у роботах [2-3]). Завдяки такому підходу вихідна програма займається тільки розв'язанням її основної задачі й абстрагована від кількісних характеристик ОС, що значно спрощує її розробку. Також така абстракція дозволяє створювати прикладні програми, що зможуть автоматично оптимізуватися для виконання на апаратних засобах наступних поколінь.

У цій роботі зроблена спроба усунути головний недолік автотьюнінгу – істотні часові витрати на емпіричне оцінювання у цільовому середовищі великої множини варіантів вихідної паралельної програми – за допомогою використання статистичних засобів аналізу значних обсягів спостережень (позначимо множину через $C$). TuningGenie використовує експертне знання розробника оптимізованої програми для формування C (оформлюється у вигляді мета-даних у вихідному коді), що вже саме по собі мінімізує її розмір. Для додаткового скорочення С можна застосувати статистичне навчання, тобто емпіричну оцінку варіацій ${{C}^{ml}}\in C$ пропонується підмінити оцінками з апроксимаційної моделі. Нехай ${{C}^{emp}}=|C\backslash {{C}^{ml}}|$ - множина варіацій, які будуть оцінюватися емпірично. Насправді маємо двоїсту задачу: ${{T}_{tuning}}\to 0$ при $|{{C}^{emp}}|\to 0$ й водночас ${{C}^{emp}}$ має бути досить великою щоб точно “навчити” модель.

Автотьюнінг з використанням статистичного навчання

У широкому розумінні під терміном «навчання» розуміється, що стосовно якогось класу задач, їх продуктивність покращується при набутті досвіду [4].

Загальний підхід для такого типу задач полягає у проведенні наступних етапів дослідження:

$1)$ Аналіз записів і підготовка «сирих» даних до завантаження. Оскільки дані можуть приходити з різних джерел і в різних форматах, то потрібно все привести до єдиного вигляду.

$2)$ Підготовка даних. На цьому етапі вирішуються проблеми неповноти даних, шумів, суперечності в даних и т.п. Основні задачі цього етапу – очищення (заповнення відсутніх значень, видалення спотворених даних та випадкових викидів), перетворення (нормалізація для зниження спотворень), ущільнення (створення виборок даних для окремих атрибутів/груп атрибутів та дискретизація (перетворення неперервних атрибутів в категоріальні).

$3)$ Аналіз даних та побудова моделі.

$4)$ Перевірка моделі на тестовій виборці даних.

У контексті нашої задачі автотьюнінгу оціночними параметрами є:

$·$ T – цільова функція автотьюнінгу – швидкодія алгоритму, що вимірюється у (мілі)секундах, оптимізований алгоритм має бути якнайшвидшим.

$·$ Tcn – метрика для числової оцінки виконання алгоритму – кількість паралельних потоків алгоритму.

$·$ Th – порогове значення розміру числового масиву, при якому відбувається зміна методу сортування.

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

Практичний експеримент

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

Алгоритм був реалізований на мові Java. Цільовою платформою для паралельного виконання була мультиядерна архітектура мікропроцесора Intel Core i7 3.2 GHz (4 ядра, 256KB L2 Cache, 6MB L3 cache) та 16 GB DDR3@1600 MHz RAM.

Аналіз даних та побудова моделей відбувалися з використанням мови R для програмування статистичних обчислень, аналізу та подання даних в графічному вигляді [5] та аналітичного системи ІВМ Watson Analytics [6]. Останній застосовувався для автоматизації частини підготовчої роботи та попереднього виявлення залежностей між оціночними параметрами виконання алгоритму.

Вхідними даними для аналізу є набір спостережень часу виконання алгоритму сортування при різних значення оціночних параметрів, отриманий за допомогою автотьюнера [2] (Рис. 1).

Рис. 1. Вхідні дані спостережень.

При аналізі даних Watson Analytics виявив явну корреляцію між кількістью потоків та результуючим часом виконання (рис. 2).

Рис. 2. Результат аналізу за допомогою Watson Analytics

За допомогою додаткової підготовки даних (розбиття початкового набору даних у відповідності до кількості потоків), можна отримати додаткову інформацію про наявність ще й явної залежності між часом виконання та розміром блока (при низькій кількості потоків) (рис. 3).

Рис. 3. Залежність часу виконання від порогового значення Th при Tcn = 2

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

При $Tcn=\left\{2,4,6,8,10,12,14,16 \right\}$, $Th=\left[ 1,800 \right]$ та k = 10 очікуваний час виконання автотюнера ${{T}_{oest}}=6.4*{{10}^{4}}*{{T}_{ex}}$, де ${{T}_{ex}}$ – час потрібний на 1 запуск автотьюнера.

Наведені вище графіки від Watson Analytics відображають залежність часу виконання цільового алгоритму від вхідних параметрів. В контексті поставленої задачі можна помітити:

$1)$ присутній явний тренд на зменшення часу виконання при збільшенні кількості потоків;

$2)$ вплив кількості потоків має більший вплив на систему, аніж порогове значення розміру масиву.

Далі, для уточнення вибору параметрів оптимального налаштування алгоритму було застосовано засоби статистичного моделювання R [5].

На рис. 4, отриманому за допомогою R,зображено частотний розподіл залежності часу виконання алгоритму від кількості потоків, з якого видно, що запуски паралельного алгоритму з 2,4 та 6 потоками явно не можуть бути серед кандидатів на найкращий час виконання, тому на всіх наступних графіках ці заміри будуть відкинуті як очевидно неперспективні (з точки зору задачі автотьюнінгу).

Рис. 4. Частотний аналіз вхідних даних

Подальше уточнення параметрів алгоритму було отримане, застосувавши аналіз усереднених значень часу виконання на інтервалі кількості потоків від 8 до 16 (див. таблицю 1).

Таблиця 1 – частотний розподіл для Tcn = [8,16]

І нарешті, звернемо увагу також на залежність часу виконання від порогового значення розміру масиву. Явний тренд до зменшення часу виконання спостерігається при збільшенні розміру масиву та існує тільки за низької кількості потоків (рис.5)

Рис. 5. Залежність часу виконання від Th для Tcn = 4 (зліва) та Tcn = 14 (справа).

Таким чином, виконавши статистичне дослідження системи, стало можливим виконати скорочення розмірності моделі для зменшення часу роботи автотьюнера з $6.4*{{10}^{4}}*{{T}_{ex}}$ до $\left( 8*{{10}^{2}}+k*Tcn\right)*{{T}_{ex}}$, причому $\left( 6.4*{{10}^{4}}-8*{{10}^{2}} \right)\gg k*Tcn$.

Оптимальний варіант сортування показав достатньо високі показники продуктивності: мультипроцесорне прискорення W(4) = 2.08 й ефективність E(4) = 52.08% .

Висновки

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

Перелік посилань:

$1.$ K. Naono, K. Teranishi, J. Cavazos, R. Suda: Software Automatic Tuning From Concepts to State-of-the-Art Results. Springer; 1st Edition. edition. ISBN: 1441969349 (2010)

$2.$ Ivanenko P.A, Doroshenko A.Y., Zhereb K. A. TuningGenie: Auto-Tuning Framework Based on Rewriting Rules // 10th International Conference, ICTERI 2014, Kherson, Ukraine, June 9-12, 2014, Revised Selected Papers - pp 139-158.

$3.$ Иваненко П.А., Дорошенко А.Ю. Метод автоматической генерации автотюнеров для параллелных программ // Кибернетика и системный анализ №3 2014 – с.75-83

$4.$ Tom M. Mitchell. Machine learning // mcGraw-HillScience/Engineering/Math., 1997, ISBN: 0070428077

$5.$ Michael J. Crawley. The R Book // JohnWiley & Sons Ltd, 2007, ISBN: 978040515068/

Mar 27, 2017