Hybrid autotuning model with statistic modelling

The paper presents well known autotuning model modified with statistic modelling in order to narrow a space of search for optimal variation of the program. Proposed method was applied to optimization of hybrid parallel sorting algorithm. Experiment results on multicore system are provided.Problems i...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автори:	Doroshenko, А.Yu., Ivanenko, P.A., Novak, O.S.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	autotuning statistical modelling automation of software development process UDC 681.5
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/210
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-210
record_format	ojs
resource_txt_mv	ppisoftskievua/41/4373526427a06f18d977a839a3235d41.pdf
spelling	pp_isofts_kiev_ua-article-2102024-04-28T11:59:06Z Hybrid autotuning model with statistic modelling Гибридная модель автотьюнинга с использованием статистического моделирования Гібридна модель автотьюнінгу з використанням статистичного моделювання Doroshenko, А.Yu. Ivanenko, P.A. Novak, O.S. autotuning; statistical modelling; automation of software development process UDC 681.5 автотьюнинг; статистическое моделирование; автоматизация разработки программного обеспечения УДК 681.5 автотьюнінг; статистичне моделювання; автоматизація розробки програмного забезпечення УДК 681.5 The paper presents well known autotuning model modified with statistic modelling in order to narrow a space of search for optimal variation of the program. Proposed method was applied to optimization of hybrid parallel sorting algorithm. Experiment results on multicore system are provided.Problems in programming 2016; 4: 27-32 Разработана модификация известного метода автоматической оптимизации (автотьюнинга) программ с использованием статистического моделирования для сужения области поиска оптимального варианта программы. Предложенный метод опробован на оптимизации параллельного гибридного алгоритма сортировки. Приведены результаты практического эксперимента на мультипроцессорной системе.Problems in programming 2016; 4: 27-32 Розроблена модифікація відомого методу самоналаштування (автотьюнінгу) програм з використанням статистичного моделювання з метою звуження простору пошуку оптимального варіанта програми. Запропонований метод застосовано до оптимізації паралельного гібридного алгоритму сортування. Наведено результати практичного експерименту на мультипроцесорній системі.Problems in programming 2016; 4: 27-32 Інститут програмних систем НАН України 2018-07-03 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/210 10.15407/pp2016.04.027 PROBLEMS IN PROGRAMMING; No 4 (2016); 27-32 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2016); 27-32 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2016); 27-32 1727-4907 10.15407/pp2016.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/210/202 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:59:06Z
collection	OJS
language	Ukrainian
topic	autotuning statistical modelling automation of software development process UDC 681.5
spellingShingle	autotuning statistical modelling automation of software development process UDC 681.5 Doroshenko, А.Yu. Ivanenko, P.A. Novak, O.S. Hybrid autotuning model with statistic modelling
topic_facet	autotuning statistical modelling automation of software development process UDC 681.5 автотьюнинг статистическое моделирование автоматизация разработки программного обеспечения УДК 681.5 автотьюнінг статистичне моделювання автоматизація розробки програмного забезпечення УДК 681.5
format	Article
author	Doroshenko, А.Yu. Ivanenko, P.A. Novak, O.S.
author_facet	Doroshenko, А.Yu. Ivanenko, P.A. Novak, O.S.
author_sort	Doroshenko, А.Yu.
title	Hybrid autotuning model with statistic modelling
title_short	Hybrid autotuning model with statistic modelling
title_full	Hybrid autotuning model with statistic modelling
title_fullStr	Hybrid autotuning model with statistic modelling
title_full_unstemmed	Hybrid autotuning model with statistic modelling
title_sort	hybrid autotuning model with statistic modelling
title_alt	Гибридная модель автотьюнинга с использованием статистического моделирования Гібридна модель автотьюнінгу з використанням статистичного моделювання
description	The paper presents well known autotuning model modified with statistic modelling in order to narrow a space of search for optimal variation of the program. Proposed method was applied to optimization of hybrid parallel sorting algorithm. Experiment results on multicore system are provided.Problems in programming 2016; 4: 27-32
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/210
work_keys_str_mv	AT doroshenkoayu hybridautotuningmodelwithstatisticmodelling AT ivanenkopa hybridautotuningmodelwithstatisticmodelling AT novakos hybridautotuningmodelwithstatisticmodelling AT doroshenkoayu gibridnaâmodelʹavtotʹûningasispolʹzovaniemstatističeskogomodelirovaniâ AT ivanenkopa gibridnaâmodelʹavtotʹûningasispolʹzovaniemstatističeskogomodelirovaniâ AT novakos gibridnaâmodelʹavtotʹûningasispolʹzovaniemstatističeskogomodelirovaniâ AT doroshenkoayu gíbridnamodelʹavtotʹûnínguzvikoristannâmstatističnogomodelûvannâ AT ivanenkopa gíbridnamodelʹavtotʹûnínguzvikoristannâmstatističnogomodelûvannâ AT novakos gíbridnamodelʹavtotʹûnínguzvikoristannâmstatističnogomodelûvannâ
first_indexed	2024-09-16T04:07:34Z
last_indexed	2024-09-16T04:07:34Z
_version_	1818568172734775296
fulltext	Інструментальні засоби та середовища програмування © А.Ю. Дорошенко, П.А. Іваненко, О.С. Новак, 2016 ISSN 1727-4907. Проблеми програмування. 2016. № 4 27 УДК 681.5. А.Ю. Дорошенко, П.А. Іваненко, О.C. Новак ГІБРИДНА МОДЕЛЬ АВТОТЬЮНІНГУ З ВИКОРИСТАННЯМ СТАТИСТИЧНОГО МОДЕЛЮВАННЯ Розроблена модифікація відомого методу самоналаштування (автотьюнінгу) програм з використан- ням статистичного моделювання з метою звуження простору пошуку оптимального варіанта програ- ми. Запропонований метод застосовано до оптимізації паралельного гібридного алгоритму сортуван- ня. Наведено результати практичного експерименту на мультипроцесорній системі. Ключові слова: автотьюнінг, статистичне моделювання, автоматизація розробки програмного забезпе- чення. Вступ Питання оптимального викорис- тання обчислювальних ресурсів було й залишається актуальним у процесі роз- робки будь-якого програмного забезпе- чення – від мобільних додатків до склад- них клієнт-серверних систем. Парадигма автотьюнінгу [1], яка за останнє десяти- річчя стала стандартом для вирішення задачі оптимізації програмних додатків, дозволяє повністю автоматизувати цей процес для будь-якого обчислювального середовища. Її популярність зумовлена в першу чергу простотою застосування й незалежністю від якісних характеристик обчислювача та його операційної системи. Автотьюнінг традиційно використовує емпіричний підхід для отримання якісної оцінки оптимізованої програми (під якістю зазвичай розуміють швидкодію й точність результату). Такий підхід дозво- ляє уникнути моделювання виконання додатку, що є безумовно складною зада- чею, а також є точним – важко запропо- нувати щось більш точне ніж виконання програми у цільовому середовищі. Проте, автотьюнінг будь-яких нетривіальних програмних додатків потребує суттєвих часових затрат. В даній публікації розглядається гібридний підхід до з використанням техніки машинного нав- чання. Запропонований підхід полягає у автоматичному навчанні моделі на ре- зультатах “традиційних” циклів тьюнінгу й подальшій підміні частини запусків програми оцінкою з апроксимаційної моделі. Методологія автотьюнінгу Для досягнення максимальної ефективності програми необхідне її додаткове налаштування (тьюнінг) під обчислювальне середовище (ОС), у якому вона буде виконуватися. Як вже було сказано, сучасна методологія самона- лаштування (автотьюнінгу) дозволяє автоматизувати це налаштування. Ідея автотьюнінгу полягає у емпіричному оцінюванні декількох варіантів програми й вибору найкращого. Традиційно підбір виконує окрема програма-тюнер, а основними критеріями оцінки є швидкодія й точність отриманих результатів. Методологія автотьюнінгу активно досліджується у міжнародній науковій спільноті (університети Берклі, Карлсруе та Токіо). Вона вже довела свою універ- сальність й ефективність проте не поз- бавлена недоліків, серед яких традиційно виділяють значний час роботи авто- тьюнера й необхідність його написання. В цілому дії програми-тюнера є досить шаблонними – обрати/створити нову версію програми й отримати емпі- ричну оцінку її швидкодії. Тому останній недолік усувається автоматичним генеру- ванням автотьюнера з вихідного коду оптимізованої програми, що є характе- ристичною рисою програмної системи автотьюнінгу TuningGenie (детально описана у роботах [2–3]). Завдяки такому підходу вихідна програма займається тільки розв’язанням її основної задачі й Інструментальні засоби та середовища програмування 28 абстрагована від кількісних характеристик ОС, що значно спрощує її розробку. Також така абстракція дозволяє створювати прог- рамні додатки, що будуть автоматично оптимізуватися для виконання на апарат- них засобах наступних поколінь (при- наймні доки не зміниться багатоядерна архітектура обчислювачів). Ця стаття висвітлює результати роботи над усуненням головного недоліку автотьюнінгу – істотними часовими за- тратами, які зумовлені необхідністю емпі- ричного оцінювання у цільовому сере- довищі великої множини варіантів вихід- ної паралельної програми (позначимо множину через C ). TuningGenie вико- ристовує експертне знання розробника оптимізованої програми для формування C (оформлюється у вигляді мета-даних у вихідному коді), що вже саме по собі мінімізує її розмір. Для додаткового скорочення C ) можна застосувати машинне навчання, тобто емпіричну оцінку варіацій CC ml  пропонується підмінити оцінками з апроксимаційної моделі. Нехай \|\\| mlemp CCC  – множина варіацій, які будуть оцінюватися емпірично. Насправді маємо двоїсту задачу: 0tuningT при 0\|\| empC й водночас empC має бути досить великою щоб точно “навчити” модель. Наступний підрозділ пояснює деталі побудови моделі й дає теоретичну оцінку скорочення часу tuningT . Модель автотьюнінгу з використанням статистичного навчання Для початку, визначимо що ми ма- ємо на увазі під терміном «навчання». У широкому розумінні можна вважати що програма отримує досвід (оцінку) E стосо- вно якогось класу задач T при замірах про- дуктивності P якщо її продуктивність для задач T оцінених за допомогою P покра- щується при набутті досвіду E [4]. Машинне навчання тісно пов’язане (і часто перетинається) з обчислювальною статистикою, дисципліною, яка також фо- кусується на прогнозуванні шляхом засто- сування комп’ютерів. Воно має тісні зв’язки з математичною оптимізацією, те- орією матриць, лінійною алгеброю та ко- пулами, які забезпечують цю галузь мето- дами, теорією та прикладними областями. Машинне навчання іноді з’єднують з до- буванням даних [5], де друга підгалузь фокусується більше на дослідницькому аналізі даних, і є відомою як навчання без учителя [6]. Як правило, задачі машинного нав- чання в залежності від природи «сигналу» поділяють на такі категорії [7]:  навчання з учителем. Системі надаються приклади входів та їхніх бажа- них виходів, задані «вчителем», і метою є навчання загального правила, яке відобра- жає входи на виходи;  навчання без учителя. Алгори- тмові навчання не дається жодних міток, залишаючи його самому знаходити струк- туру в своєму вході. Навчання без учителя може бути метою саме по собі (виявлення прихованих закономірностей у даних), або засобом досягнення мети (навчання ознак);  навчання з підкріпленням. Комп’ютерна програма взаємодіє з дина- мічним середовищем, у якому вона має виконувати певну мету (наприклад, таку як водіння авто) без учителя, який явно казав би їй, чи підійшла вона близько до мети. Іншим прикладом є навчання грі через гру із суперником. Загалом, можна описати загальний підхід для такого типу задач [8]: 1) аналіз записів і підготовка «си- рих» даних до завантаження. Оскільки дані можуть приходити з різних джерел і в різних форматах, то потрібно все привести до єдиного вигляду; 2) підготовка даних. На цьому етапі вирішуються проблеми неповноти даних, шумів, суперечності в даних и т. п. Основні задачі цього етапу – очищення (заповнення відсутніх значень, видалення спотворених даних та випадкових вики- дів), перетворення (нормалізація для зни- ження спотворень), ущільнення (створення виборок даних для окремих атрибутів/груп атрибутів та дискретизація (перетворення неперервних атрибутів в категоріальні); Інструментальні засоби та середовища програмування 29 3) аналіз даних та побудова моде- лі; 4) перевірка моделі на тестовій виборці даних. У контексті нашої задачі авто- тьюнінгу оціночними параметрами є:  T – цільова функція автотьюні- нгу – швидкодія алгоритму, що вимірю- ється у (мілі)секундах, оптимізований ал- горитм має бути якнайшвидшим;  P – метрика для числової оцін- ки параметрів виконання алгоритму, до яких, зокрема, належить кількість парале- льних потоків алгоритму;  E – статистичні спостереження виконання алгоритму, що оптимізується. Суть методу полягає у зменшенні кількості запусків автотьюнера за допомо- гою побудови апроксимаційної моделі, що дозволить “відкинути” найменш вірогідні заміри. При цьому апроксимація моделі відбувається завдяки скороченню розмір- ності вхідних параметрів множини C . Засоби статистичного моделювання В подальшому, для статистичного аналізу системи використовувалась мова R. R – мова програмування для статистичних обчислень, аналізу та представлення даних в графічному вигляді [9]. Але вибір інструменту в даному випадку не принциповий, і загалом можна використовувати й інший інструментарій: Python, Julia, S, Matlab і т. д. Так як при статистичному аналізі ми оперуємо частотними характеристи- ками, то для їх наглядного відображення зручно використовувати коробковий графік (від англ. “boxplot”) [10]. Приклад коробкового графіка показано на рис. 1. Нижня та верхня сторона «ящика» відповідає першому і третьому квантилям, група всередині коробки – другий кван- тиль (медіана). Кінці «вусів» можуть представляти собою декілька можливих значень – мінімум та максимум даних, граничне значення в межах 1.5 IQR (межквартільний діапазон, від англ. «interquartile range») від нижньо- го/верхнього квантиля, 1 σ вище/нижче середніх даних, 9-а та 91-а процентилі чи 2-а та 98-а процентилі. Тому варто зауважити, що для всіх далі приведених графіків вуса коробкових графіків відповідають граничним значенням в межах 1.5 IQR від відповідного квантиля. Рис. 1. Приклад коробкового графіка Практичний експеримент Як приклад алгоритму для авто- тьюнінгу було обрано адаптивний алго- ритм сортування який виконує сортування злиттям чи вставкою у залежності від роз- міру блоку числового масиву з даними [9]. Алгоритм був реалізований на мові Java. Аналіз даних та побудова моделей відбувалися з використанням мови R. R – мова програмування для статистичних обчислень, аналізу та представлення да- них в графічному вигляді [10]. Але вибір інструменту в даному випадку не принци- повий, і загалом можна використовувати й інший інструментарій: Python, Julia, S, Matlab і т. д. Сам експеримент складався з декі- лькох стандартних етапів: підготовка та завантаження записів роботи автотьюнера в середовище R, побудова моделі з вико- ристанням методів машинного навчання на навчальній вибірці даних та перевірка мо- делі на контрольній вибірці даних. Варто підкреслити, що використо- вувалось два різних набори даних – мак- симально повний для емпіричного аналізу Інструментальні засоби та середовища програмування 30 системи та мінімально достатній для пере- вірки моделі. В рамках даного експерименту ви- конувалось сортування набору в випа- дкових чисел, а як можливі параметри автотьюнера маємо }{ ThTcn,C  , де Tcn – кількість потоків виконують обчис- лення одночасно, Th – розмір блоку при якому буде використовуватися інший ал- горитм сортування. Як метрика для оцінки моделі з заданими Tcn та Th використову- ється T – час виконання алгоритму для Tcn та Th . При }16,14,12,10,8,6,4,2{Tcn , Th [1,800] та k =10 очікуваний час вико- нання автотьюнера , де exT – час, потрібний на один запуск ав- тотьюнера. Наведені далі графіки відображають залежність часу виконання цільового алго- ритму від вхідних параметрів. Ці данні потрібні на етапі емпіричного аналізу для того, щоб максимально зменшити розмір- ність системи та скоротити запуски авто- тьюнера (рис. 2). В контексті поставленої задачі мо- жна помітити, що вплив кількості потоків оказує на систему більший вплив ніж роз- мір блоку (рис. 3). Це можна побачити за наявністю двох явно виражених кластерів даних на першому графіку. Рис. 2. Вхідні дані моделі Рис. 3. Частотний розподіл швидкодії за кількістю паралельних потоків Для швидкої оцінки моделі викори- стовуємо числове інтегрування методом прямокутників (табл. 1). Цей крок дозво- лить на ранньому етапі відкинути заздале- гідь непідходящі варіанти при мінімальній кількості реальних запусків автотьюнера. Таблиця 1. Наближена оцінка швидкодії Tc n 2 4 6 8 10 12 14 16 Va lu e 71 73 1 45 22 5 45 26 9 41 01 9 41 18 4 41 35 9 40 39 8 42 41 9 Як вибіркову функцію використовуємо },)min({ TcnkxTcnxTcnnew  де k – коефіцієнт, що впливає на макси- мально допустиме відхилення від мініма- льного значення. При чому, збільшення k значно збільшує час побудови моделі, але при цьому зменшує вірогідність отримати локальний (а не глобальний) мінімум після побудови моделі. В даному випадку ми звужуємо ко- ло пошуку до }.16,14,12,10,8{Tcn Оцінивши частотний розподіл після першого спрощення моделі (рис. 4), можна звузити коло пошуку то }14{Tcn , що зводить складність задачі з екпоненційної )( nCO до лінійної )(nO (табл. 2). Інструментальні засоби та середовища програмування 31 Рис. 4. Частотний розподіл після першого спрощення моделі Таблиця 2. Частотний розподіл після пер- шого спрощення моделі 8 10 12 14 16 Мін 928 931 946 922 942 Нижній квар- тиль 970 972 984 965 1000 Медіана 1000 1001 1007 984 1037 Верхній квар- тиль 1044 1050 1054 1021 1079 Макс 1148 1165 1154 1102 1190 Таким чином, виконавши статисти- чне дослідження системи, стало можливим виконати скорочення розмірності моделі для зменшення часу роботи автотьюнера з до , причому 4 2 (6.410 810 ) *k Tcn . Практичний експеримент виконува- вся на комп’ютері з процесором Intel Core i7 2.3 GHz (4 ядра, 256KB L2 Cache, 6MB L3 cache) та 16 GB DDR3@1600 MHz RAM. Оптимальний варіант сортування показав мультипроцесорне прискорення 08.2)4( W й ефективність %08.52)4( E %75.47)8( E (рис. 5). Рис. 5. Остаточний частотний розподіл швидкодії алгоритму Висновки В роботі розглянуто гібридний ме- тод автотьюнінгу с використанням статис- тичного моделювання. Цей метод дозволяє значною мірою позбутися головної слаб- кості методології автотьюнінгу, а саме суттєво скоротити загальний час пошуку оптимального варіанту програми за раху- нок використання статистичної моделі для звуження області пошуку. Для практично- го експерименту обрано відносно просту задачу оптимізації паралельного алгорит- му сортування чисел. Результати експери- менту підтвердили ефективність запропо- нованого методу й доцільність подальшого розвитку підходу, а саме використання більш складних апроксимаційних функцій та проведення експериментів з паралель- ними програмами більшої обчислювальної й семантичної складності. 1. Naono K., Teranishi K., Cavazos J., Suda R. Software Automatic Tuning From Concepts to State-of-the-Art Results. Springer; 1st Edition. Edition, 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. – P. 139–158. 3. Иваненко П.А., Дорошенко А.Ю. Метод ав- томатической генерации автотюнеров для Інструментальні засоби та середовища програмування 32 параллелных программ // Кибернетика и системный анализ. – 2014. – № 3. – С. 75–83. 4. Tom M. Mitchell. Machine learning // mcGraw-Hill Science/Engineering/Math., 1997. 5. Mannila, Heikki. Data mining: machine learning, statistics, and databases // Eighth International Conference on Scientific and Statistical Database Systems, 1996. 6. Friedman, Jerome H. Data Mining and Statistics: What's the connection? // Proceedings of the 29th Symposium on the Interface Between Computer Science and Statistics, 1998. 7. Russell, Stuart, Norvig, Peter. Artificial Intelligence: A Modern Approach (2nd edition) // Prentice Hall. 8. Jiawei Han, Micheline Kamber, Jian Pei. Data mining: Cencepts and Techniques, 3rd edition // Morgan Kaufmann, 2011. 9. Thomas H.Cormen. Algorithms unlocked // The MIT Press, 2009. 10. Michael J.Crawley. The R Book // John Wiley & Sons Ltd, 2007. References 1. Naono K., Teranishi K., Cavazos J., Suda R. Software Automatic Tuning From Concepts to State-of-the-Art Results. Springer; 1st Edition. Edition, 2010. 2. Ivanenko P.A, Doroshenko A.Y., Zhereb K.A. TuningGenie: Auto-Tuning Framework Based on Rewriting Rules // 10th International Con- ference, ICTERI 2014, Kherson, Ukraine, June 9-12, 2014, Revised Selected Papers. – P. 139–158. 3. Ivanenko P.A, Doroshenko A.Y. Method for automated generation of autotuners for parallel applications // Cybernetics and system analisys. – 2014. – N 3. – С. 75–83. 4. Tom M. Mitchell. Machine learning // mcGraw-Hill Science/Engineering/Math., 1997. 5. Mannila, Heikki. Data mining: machine learning, statistics, and databases // Eighth International Conference on Scientific and Statistical Database Systems, 1996. 6. Friedman, Jerome H. Data Mining and Statistics: What's the connection? // Proceedings of the 29th Symposium on the Interface Between Computer Science and Statistics, 1998. 7. Russell, Stuart, Norvig, Peter. Artificial Intelligence: A Modern Approach (2nd edition) // Prentice Hall. 8. Jiawei Han, Micheline Kamber, Jian Pei. Data mining: Cencepts and Techniques, 3rd edition // Morgan Kaufmann, 2011. 9. Thomas H.Cormen. Algorithms unlocked // The MIT Press, 2009. 10. Michael J.Crawley. The R Book // John Wiley & Sons Ltd, 2007. Одержано 03.10.2016 Про авторів: Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп’ютерних обчислень, професор кафедри автоматики та управ- ління в технічних системах НТУУ “КПІ”. Кількість наукових публікацій в українських виданнях – більше 150. Кількість наукових публікацій в іноземних виданнях – понад 30. Індекс Хірша – 4. http://orcid.org/0000-0002-8435-1451, Іваненко Павло Андрійович, молодший науковий співробітник. http://orcid.org/0000-0001-5437-9763, Новак Олександр Сергійович, аспірант. http://orcid.org/0000-0002-1665-7360. Місце роботи авторів: Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 3559. E-mail: a-y-doroshenko@ukr.net, paiv@ukr.net, novak.as@i.ua mailto:a-y-doroshenko@ukr.net mailto:paiv@ukr.net mailto:novak.as@i.ua

Hybrid autotuning model with statistic modelling

Репозитарії

Схожі ресурси