Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автори:	Ігнатенко, О.П., Іваненко, П.А., Синецький, О.Б., Ніколенко, О.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2015
Назва видання:	Проблеми програмування
Теми:	Моделі та засоби паралельних і розподілених програм
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/117092
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах / О.П. Ігнатенко, П.А. Іваненко, О.Б. Синецький, О.В. Ніколенко // Проблеми програмування. — 2015. — № 3. — С. 14-23. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-117092
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1170922025-02-23T17:27:36Z Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах Game model of user interaction in heterogeneous distributed environments Ігнатенко, О.П. Іваненко, П.А. Синецький, О.Б. Ніколенко, О.В. Моделі та засоби паралельних і розподілених програм В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчислення у гетерогенній багатопроцесорній системі. Запропонований підхід моделювання застосовується до задачі множення матриць з планувальником мін-мін. Дією користувачів у даному випадку є розмір блоку на яку розрізається матриця. Експериментально отримані характеристики системи були використані для налаштування імітаційної моделі, що дозволило виміряти оцінку часу завершення роботи для всіх можливих комбінацій розбиття задач по процесорам та побудувати поверхню залежності часу закінчення роботи для кожного користувача. Отримані результати були обґрунтовані і узагальнені на базі ігрового підходу, зокрема, показано існування точки рівноваги Неша для взаємодії двох користувачів та знайдені умови її Парето неефективності. 2015 Article Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах / О.П. Ігнатенко, П.А. Іваненко, О.Б. Синецький, О.В. Ніколенко // Проблеми програмування. — 2015. — № 3. — С. 14-23. — Бібліогр.: 11 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/117092 004.7 uk Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Моделі та засоби паралельних і розподілених програм Моделі та засоби паралельних і розподілених програм
spellingShingle	Моделі та засоби паралельних і розподілених програм Моделі та засоби паралельних і розподілених програм Ігнатенко, О.П. Іваненко, П.А. Синецький, О.Б. Ніколенко, О.В. Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах Проблеми програмування
description	В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчислення у гетерогенній багатопроцесорній системі. Запропонований підхід моделювання застосовується до задачі множення матриць з планувальником мін-мін. Дією користувачів у даному випадку є розмір блоку на яку розрізається матриця. Експериментально отримані характеристики системи були використані для налаштування імітаційної моделі, що дозволило виміряти оцінку часу завершення роботи для всіх можливих комбінацій розбиття задач по процесорам та побудувати поверхню залежності часу закінчення роботи для кожного користувача. Отримані результати були обґрунтовані і узагальнені на базі ігрового підходу, зокрема, показано існування точки рівноваги Неша для взаємодії двох користувачів та знайдені умови її Парето неефективності.
format	Article
author	Ігнатенко, О.П. Іваненко, П.А. Синецький, О.Б. Ніколенко, О.В.
author_facet	Ігнатенко, О.П. Іваненко, П.А. Синецький, О.Б. Ніколенко, О.В.
author_sort	Ігнатенко, О.П.
title	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
title_short	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
title_full	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
title_fullStr	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
title_full_unstemmed	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
title_sort	ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах
publisher	Інститут програмних систем НАН України
publishDate	2015
topic_facet	Моделі та засоби паралельних і розподілених програм
url	https://nasplib.isofts.kiev.ua/handle/123456789/117092
citation_txt	Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах / О.П. Ігнатенко, П.А. Іваненко, О.Б. Синецький, О.В. Ніколенко // Проблеми програмування. — 2015. — № 3. — С. 14-23. — Бібліогр.: 11 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT ígnatenkoop ígrovamodelʹvzaêmodííkoristuvačívugeterogennihrozpodílenihseredoviŝah AT ívanenkopa ígrovamodelʹvzaêmodííkoristuvačívugeterogennihrozpodílenihseredoviŝah AT sinecʹkijob ígrovamodelʹvzaêmodííkoristuvačívugeterogennihrozpodílenihseredoviŝah AT níkolenkoov ígrovamodelʹvzaêmodííkoristuvačívugeterogennihrozpodílenihseredoviŝah AT ígnatenkoop gamemodelofuserinteractioninheterogeneousdistributedenvironments AT ívanenkopa gamemodelofuserinteractioninheterogeneousdistributedenvironments AT sinecʹkijob gamemodelofuserinteractioninheterogeneousdistributedenvironments AT níkolenkoov gamemodelofuserinteractioninheterogeneousdistributedenvironments
first_indexed	2025-11-24T02:22:19Z
last_indexed	2025-11-24T02:22:19Z
_version_	1849636620180914176
fulltext	Моделі та засоби паралельних і розподілених програм © О.П. Ігнатенко, П.А. Іваненко, О.Б. Синецький, О.В. Ніколенко, 2015 14 ISSN 1727-4907. Проблеми програмування. 2015. № 3 УДК 004.7 О.П. Ігнатенко, П.А. Іваненко, О.Б. Синецький, О.В. Ніколенко ІГРОВА МОДЕЛЬ ВЗАЄМОДІЇ КОРИСТУВАЧІВ У ГЕТЕРОГЕННИХ РОЗПОДІЛЕНИХ СЕРЕДОВИЩАХ В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчис- лення у гетерогенній багатопроцесорній системі. Запропонований підхід моделювання застосовується до задачі множення матриць з планувальником мін-мін. Дією користувачів у даному випадку є розмір блоку на яку розрізається матриця. Експериментально отримані характеристики системи були викорис- тані для налаштування імітаційної моделі, що дозволило виміряти оцінку часу завершення роботи для всіх можливих комбінацій розбиття задач по процесорам та побудувати поверхню залежності часу за- кінчення роботи для кожного користувача. Отримані результати були обґрунтовані і узагальнені на базі ігрового підходу, зокрема, показано існування точки рівноваги Неша для взаємодії двох користувачів та знайдені умови її Парето неефективності. Вступ В даній роботі проведені дослі- дження з застосування методів теорії ігор для аналізу процесів планування у склад- них гетерогенних обчислювальних систе- мах. На таких системах побудована, зок- рема, технологія хмарних обчислень. Бу- демо розглядати проблему планування ре- сурсів за умов конкуренції між користува- чами [1]. Хмарна система надає послуги великій кількості користувачів, при цьому її ресурси (пропускна здатність, буфери, потужність вузлів) обмежені. Користувачі (люди, програми, сервіси) є неоднорідни- ми у своїх запитах і можуть діяти неперед- бачуваним чином. Необхідно розділити ресурси між конкуруючими користувача- ми ефективним та справедливим (макси- мально задовольняючи користувачів) чи- ном. Сучасні прикладні наукові задачі вимагають значних обчислювальних ресу- рсів, тому задача оптимізації виконання обчислювальних задач у багатопроцесор- них середовищах займає чи не найперше місце в процесі розробки високопродукти- вних програм. Ефективне виконання обчи- слень вимагає використання ефективних паралельних алгоритмів, швидкодія яких у свою чергу залежить від конкретного се- редовища виконання. Необхідність опти- мізації виникає тому, що на етапі проекту- вання застосування частіше за все інфор- мація про середовище виконання відсутня. І навіть якщо конфігурація відома, то май- же неможливо визначити таку конфігура- цію програми, за якої обчислення будуть виконуватися з максимально ефективним використанням ресурсів системи. Також слід пам’ятати, що програма, оптимізована під конкретну обчислювальну платформу, не зможе показати максимальну швидко- дію на будь-якій іншій відмінній платфор- мі. Саме тому зазвичай усі релевантні для швидкодії параметри виносяться в деяку зовнішню конфігурацію, значення якої змінюють під час оптимізації. Складність такої оптимізації полягає у тому, що зв’язок між цими параметрами не є тривіа- льним, тому оптимізація майже завжди зводиться до повного перебору всіх мож- ливих конфігурацій. За виключенням три- віальних задач кількість та область значень цих параметрів визначають множину всіх можливих конфігурацій значної потужнос- ті, що робить такий підхід неможливим без автоматизації. Також слід зауважити, що часто оптимальна конфігурація не є інтуї- тивно очевидною. Можна відзначити, наприклад, роботи [2–5]. Відносно нова парадигма програм- ної автоматичної оптимізації (для зручнос- ті будемо використовувати скорочений термін «автотюнінг») вважається перспек- тивним програмним підходом, який до- зволяє науковцям та інженерам ефективно використовувати безперервно зростаючі обчислювальні потужності супер- комп’ютерів з точки зору витраченого ча- су й енергії [6]. Сфера її застосування простягається від наукових до загально- Моделі та засоби паралельних і розподілених програм 15 цільових обчислень й не обмежується су- перкомп’ютерами. Підклас застосувань, оптимізація яких може виконуватися ав- тотюнерами, підпадають ресурсоємні прикладні програми, швидкість й ефекти- вність виконання яких залежить від кон- фігурації обчислювального середовища (кількість процесорів, обсяг оперативної пам’яті, розмір кешу процесора та при- строїв зчитування інформації, пропускна здатність мережі тощо) й які мають меха- нізми адаптації чи дозволяють легко їх інтегрувати. Фактично цей клас задач включає усі нетривіальні застосування для будь-яких середовищ – від платформ для розподілених обчислень до мобільних пристроїв. Автотюнери успішно розв’я- зують описану вище проблему, а саме: до- зволяють створювати максимально ефек- тивні в будь-яких обчислювальних середо- вищах застосування з мінімальним людсь- ким втручанням у процес оптимізації. З розвитком та ускладненням хмар- них сервісів виникає проблема побудови ефективних алгоритмів забезпечення їх безперешкодної роботи. Одним з перспек- тивних напрямків розвитку є теоретико- ігровий підхід [4, 7, 8], який дозволяє по- будувати аналітичні моделі та дослідити динаміку системи з багатьма конфліктую- чими за ресурси користувачами. Хмарні обчислення стали новим на- прямком розвитку інформаційних техно- логій, об’єднавши у собі ідеї комп’ютерних мереж та обчислювальних дата центрів. Власне хмара – це можли- вість надавати сервіси користувачам через мережу Інтернет. Таким чином, ключовим елементом роботи хмарної системи є ефективні алго- ритми надання сервісів користувачам. Су- часна хмарна система існує у середовищі постійних змін. Змінюються технології, протоколи та програмне забезпечення. Змінюються користувачі, їх пріоритети, задачі і поведінка. Всі ці зміни є неперед- бачуваними. Тому теорія ігор, яка вже має історію успішного застосування до розв’язання задач маршрутизації, плану- вання, керування потоками даних і перева- нтаженнями, є головним напрямком аналі- тичного моделювання хмарних систем. Аналітичне моделювання дозволяє формалізувати роботу системи, поведінку користувачів і залучити їх у побудовану модель. Кожен гравець тут є автономним агентом, що прагне отримати певну части- ну обчислювального ресурсу. Припускаю- чи, що гравці діють раціонально – тобто максимізують свою функцію корисності можна здійснити аналіз отриманої гри. Ключовим елементом аналізу є пошук то- чки рівноваги та її характеристика. Рівно- вага – це одна з головних ідей теорії ігор. Буквально – рівноважний стан відповідає ситуації, коли гравці досягли максимуму своїх функцій корисності. В залежності від зовнішніх факторів можливі стійкі і не- стійкі рівноваги. Взагалі, концепцій рівно- ваги в іграх існує більш ніж два десятки. Найбільш відомою є рівновага за Нешем: множина стратегій гравців утво- рюють рівновагу за Нешем, якщо ніхто з них не може покращити свою функцію ко- рисності змінюючи окремо свою страте- гію. Іншими словами кожен гравець вико- ристовує найкращу можливу стратегію у відповідь на стратегії своїх опонентів. Задача множення матриць В роботах [2, 5] була побудована аналітична модель алгоритму множення матриць у залежності від конкретної кон- фігурації обчислювальної системи з метою пошуку оптимального розв’язку. В даній роботі будемо вважати, що обчислювальні вузли не зв’язані один з одним і не можуть обмінюватись напряму даними. Кожен вирішує свою задачу не- залежно і повертає користувачу результат по закінченню. Нехай система складається з m обчислювальних елементів та кожен з них характеризується швидкістю роботи ip , mi ,...,1 – тобто кількістю операцій з плаваючою точкою за секунду, які він може здійснити. Далі у статті будемо вважати, що процесори впорядковані за зменшенням потужності. Обчислювачі з’єднані лініями зв’язку з планувальни- ком, який передає задачі та приймає від них результат. Будемо вважати, що лінії зв’язку ідентичні та мають швидкість пе- редачі даних q . Моделі та засоби паралельних і розподілених програм 16 В роботі [2] описаний паралельний алгоритм, який виконує множення матриць за найкоротший час для довільної кількос- ті неоднорідних процесорів. Нагадаємо ос- новні результати. Будемо вважати, що виконуються наступні припущення: 1) всі процесори починають робо- ту одночасно; 2) планувальник здійснює призна- чення миттєво. Нехай задані дві квадратні матриці розмірністю NN  , результат множення яких необхідно обчислити. При викорис- танні блочного алгоритму користувач за- дає розмір блоку n , який визначає елемен- тарні задачі, які будуть виконуватися в об- числювальній системі. Таким чином, алгоритм сформує 2 2 n N k  задач, кожна з яких буде мати складність )( 2nO . Припустимо, що плану- вальник забезпечує пересилку повідомлень на вузли за певним фіксованим детермініс- тичним алгоритмом, який завершує обчис- лення за час ).( nNT . Тоді задача користу- вача полягає у пошуку мінімуму функції: min),( nNT . Функція ),( nNT , взагалі кажучи, може мати багато локальних мінімумів (в залежності від обчислювальної системи та планувальника) оскільки існує мінімальна фіксована величина задачі. При перепла- нуванні блоку з одного процесора на ін- ший відбувається дискретна зміна часу ви- конання. Тому задача визначення глобаль- ного мінімуму є складною. Одним з розповсюджених підходів до аналізу таких задач полягає у дослі- дженні потокової моделі даного процесу. Припустимо, що користувач вибрав вектор mRx з компонентами ix , де 0ix , kxi  , mi ,...,1 , kx k i i  1 . Всі такі вектори утворюють множину )(nX . Ко- жен компонент вектора x описує відсоток задач, призначених для виконання на i -му процесорі. Будемо брати до уваги тільки операції множення. Таке спрощення до- зволяє у явному вигляді виписати функції часу. Загальний час закінчення залежить від x , та дорівнює           i i mi p Nnx nXxT 2 ,...,1 max))(,( . Потокова модель передбачає мож- ливість розділення задачі на «шматочки» розміру 2Nn , компонування з них під- ходящих підзадач та визначення загально- го часу при 0 . Твердження 1 [2]. Мінімальний час закінчення обчислень (без пересилок) для потокової моделі з одним користувачем дорівнює 1 1 3             m i ipNT . Відповідно, користувач, для досягнення оптимального часу, має розділити свою задачу таким чином, щоб вузол i отримав Tpi обчислень. Розглянемо в даній роботі більш за- гальний підхід, який може бути корисним при перенесенні результатів на більш складні системи. Функція Мінковського для множи- ни X та вектора mRp визначається на- ступним чином: }:0inf{)( XppX   . Відомо, що ця функція опукла для опуклої X . Визначимо множину потужностей системи ]},0[:{ ii m prRrR  та масш- табуємо її наступним чином: R Nn nR 2 1 )(  . Тоді )())(,( )( xnXxT nR . Доведення. Розглянемо праву час- тину: )}(:0inf{)()( nRxxnR   . Умо- ва належності вектора x множині R запи- сується у вигляді Моделі та засоби паралельних і розподілених програм 17 1max ,...,1         i i mi p x , отже                2,...,1 )( max:0inf)( Nnp x x i i mi nR   . У іншому вигляді           i i mi p Nnx 2 ,...,1 max . З властивостей функції )()( xnR випливає, що мінімальний час )(min )( )( min xT nR nXx    існує і єдиний. Для врахування пересилок потрібно за- значити, що алгоритм надсилає Nnxi2 елементів на відповідний вузол та приймає 2nxi елементів. Отже, сумарний час закін- чення з урахуванням пересилок дорівнює            q Nnnx p Nnx nXxT i i i mi s )2( max))(,( 22 ,...,1 . Твердження 2. Існує мінімум часу по x – ))(,(min )( nXxTs nXx . Доведення. Оскільки x належить компактній множині, а функція )(xTs не- перервна та опукла (максимум лінійних функцій), то мінімум існує. Дискретна модель обчислення множення матриць. Нехай розмір блоку n може бути тільки цілим числом, причо- му таким, щоб 2 2 n N k  теж було цілим. Тоді мінімізація часу буде здійснюватись за скінченною множиною точок             miky kyRy nY i i i m ,..,1, },,..,1,0{: )( . Зрозуміло, що )()( nXnY  . Введемо поняття планувальника. Спочатку користувач вибирає розмір бло- ку n , в результаті чого формується мно- жина )(nY . Ця множина описує всі мож- ливі розташування задач на процесорах. Планувальник відповідає за вибір конкретного )(* nYy  . В даній роботі ми розглянемо прості планувальники типу extrextr . Один з широко вживаних плану- вальників такого типу називається minmin і він вибирає розподіл за наступним алго- ритмом: 1) формується черга з k задач, кожна обсягом обчислень 2Nn ; 2) вибирається задача з наймен- шим обсягом обчислень (в даній роботі розглядається випадок однакових задач, тому вибирається довільна); 3) задача надсилається на вільний процесор з найбільшою потужністю (тобто мінімізується час виконання), якщо віль- них процесорів немає, чекаємо поки з’явиться; 4) якщо залишились задачі у черзі, то повертаємось до п. 2. В результаті роботи алгоритму по- перше буде визначено вектор y , який опи- сує яка кількість задач потрапила на який обчислювальний вузол, по-друге, буде ви- значено час закінчення останньої задачі. Для порівняння опишемо, також, планува- льник maxmax : 1) формується черга з k задач, ко- жна обсягом обчислень 2Nn ; 2) вибирається задача з найбільшим обсягом обчислень. (в даній роботі розгля- дається випадок однакових задач, тому ви- бирається довільна); 3) задача надсилається на вільний процесор з найменшою потужністю; 4) якщо залишились задачі у черзі, то повертаємось до п. 2. Для дослідження часу закінчення у дис- кретній моделі зафіксуємо розмір блоку n . Твердження 3. Для будь-якого n виконуються нерівності: ))(,(min))(,(min)( )()( nXxTnXyTnT nXxnYy d   , )()(minmin nTnT d . Доведення. Зрозуміло, що мінімум існує. Легко представити приклад неєди- Моделі та засоби паралельних і розподілених програм 18 ності мінімуму )(nTd (два рівних процесо- ри і розбиття, що не ділиться навпіл). Оскільки )()( nXnY  , то перша нерівність виконується. Друга нерівність виконується, оскі- льки )(nTd – мінімум. Некооперативна ігрова модель обчислення множення матриць Некооперативна гра описує ситуа- цію прийняття рішень гравцями за умов конфлікту інтересів. Під терміном гравець тут ми розуміємо користувача, який впли- ває на систему шляхом вибору стратегій – дій, які він може застосовувати. В залеж- ності від дій його та інших учасників від- бувається визначення виграшів гравців. Говорять, що гравець раціональний, якщо його дії спрямовані на максимізацію влас- ного виграшу. Якщо у грі приймають участь хоча б двоє учасників, можлива ситуація, коли перший гравець може покращити свій ви- граш за рахунок зменшення виграшу ін- ших. В такому випадку кажуть про конф- ліктну взаємодію. Частинним випадком конфлікту є ситуація повністю протилеж- них інтересів – коли виграш одного є про- грашем іншого. Такі ігри називають анта- гоністичними або іграми з нульовою су- мою. Зауважимо, що некооперативність не означає, що гравці взагалі не кооперу- ються, а тільки те, що немає зовнішніх причин, які б спричиняли координацію або узгодження їх стратегії. Будь-яка коопера- ція що може виникнути має виходити зі структури гри і визначатися функціями корисності учасників. Гру називають статичною, якщо гравці приймають свої рішення одноразо- во, незалежно один від одного. В певному розумінні, статична гра не залежить від часу. Навіть якщо гравці приймають рі- шення протягом певного часового інтерва- лу, якщо вони не володіють інформацією щодо дій інших гравців, така гра є статич- ною. У динамічних іграх гравці отриму- ють певну інформацію щодо рішень інших учасників і можуть змінювати свою стра- тегію у часі, тобто приймають рішення бі- льше одного разу. Динамічні ігри є най- більш складним для аналізу і відіграють важливу роль у дослідженні процесів у ме- режах. Опишемо задачу множення матриць у вигляді статичної некооперативної гри. Основні визначення При визначенні статичних ігор за- гальновживаною є стратегічна або норма- льна форма, яка включає опис трьох ком- понентів: множини гравців, їх стратегій і виграшів. Гравцями в даному випадку явля- ються користувачі   Liiu  , L – множина індексів, які мають доступ до спільного ресурсу з m обчислювальних елементів з швидкістю роботи ip , mi ,...,1 . Будемо вважати, що для кожного користувача за- дані квадратні матриці розмірності ln , Ll . Тоді стратегіями користувачів є до- пустиме розбиття матриць на блоки ll Kk  , Ll . Після розбиття матриць, блоки потрапляють у планувальник, який надсилає їх на процесори згідно з певним визначеним алгоритмом роботи. Часом за- кінчення обчислень lT , Ll будемо нази- вати час закінчення останньої задачі кори- стувача lu . Кожен користувач намагається зменшити свій час закінчення і через об- меженість спільних ресурсів виграш одно- го користувача спричинить програш ін- ших. Будемо вважати, що виконуються наступні припущення: 1) використовується планувальник Мін-мін; 2) вибрана множина можливих ро- змірів   sjjn ,...,1 – стратегій користувачів, впорядкована за збільшенням; 3) якщо користувачі вибрали одна- кові розміри блоків, то їх час завершення однаковий і дорівнює подвоєному індиві- дуальному часу для даного розміру блоку; 4) існує єдиний мінімум ),( jd nT sj ,...,1 . Позначимо індекс стратегії, на якій він досягається j . Моделі та засоби паралельних і розподілених програм 19 Побудуємо платіжну матрицю гри за наступними правилами. Нехай гравці вибрали стратегії 21, nn відповідно. Позна- чимо їх виграші ),( 211 nnT , ),( 212 nnT . 1. Якщо 21 nn  , то виграш пер- шого користувача дорівнює )( 1nTd , друго- го )()( 21 nTnT dd  . 2. Якщо 21 nn  , то виграш пер- шого користувача дорівнює )()( 21 nTnT dd  , другого )( 2nTd . 3. Якщо 21 nn  , то виграш пер- шого і другого користувача дорівнює )(2 1nTd . Твердження 3. Нехай виконуються нерівність )()(2 1*   jdjd nTnT , тоді пара стратегій ),( jj nn – рівновага Неша. Доведення. Запишемо визначення рівноваги Неша в точці ),( jj nn : ),(),( ** 111 jjjj nnTnnT   , ),(),( 122   jjjj nnTnnT . Застосуємо до цих нерівностей пра- вила визначення виграшів: )(2),( 1 jdjj nTnnT  , )(),( 111 *   jdjj nTnnT . Аналогічно для другого користува- ча. Виконання нерівності )(2 jd nT )( 1  jd nT , таким чином, гарантує рівно- вагу Неша. Твердження 4. Нехай виконуються нерівність )()(2 1   jdjd nTnT , тоді рів- новагою Неша будуть пара стратегій ),( 11  jj nn . Доведення. Запишемо визначення рівноваги Неша в точці ),( 11  jj nn : ),(),( 11111   jjjj nnTnnT , ),(),( 12112 jjjj nnTnnT   . Запишемо виграші для першої нері- вності: )()(),( 111 jdjdjj nTnTnnT   , )(2),( 1111 *   jdjj nTnnT . Оскільки )()(2 1   jdjd nTnT , то ),(),( 11111   jjjj nnTnnT . Для іншого користувача – аналогіч- но. Наслідок. Отримана рівновага Па- рето неефективна. ),(),( 1111   jjjj nnTnnT , ),(),( 1122 **   jjjj nnTnnT . Це досить характерна ситуація для ігор та- кого типу [4]. Імітаційна модель Імітаційне моделювання розбиття користувачами задач та їх виконання в ро- зподіленому середовищі було проведено за допомогою програмного пакету CloudSim, призначеному для моделювання хмарних обчислень. Фреймворк CloudSim було розроб- лено в Університеті Мельбурна як допомі- жний засіб аналізу розподілених та хмар- них середовищ, що міг би бути застосова- ний як дослідниками, так і галузевими фа- хівцями. Можливості програмного пакету дозволяють визначати та задавати власти- вості таких сутностей як центр обробки даних (ЦОД, datacenter); вузол, що знахо- диться в ЦОД, з визначенням параметрів швидкодії процесора та обсягу оператив- ної пам’яті; віртуальна машина, що запу- щена на вузлі ЦОД і використовує певну частину його ресурсів; та, нарешті, задачі для виконання (cloudlet), що характеризу- ється обчислювальною складністю і обся- гом даних, що пересилаються мережею. В межах цього дослідження було розглянуто таку логічну схему взаємодії користувачів з хмарним середовищем (рис. 1). Користувачі незалежно один від одного надсилають до хмарного середо- Моделі та засоби паралельних і розподілених програм 20 вища задачі, що потребують обчислення (в даному дослідженні в якості таких задач було вибрано задачі множення матриць). Рис. 1. Схема взаємодії користувачів і хма- рної платформи Кожен користувач перед відсилкою може розбити свою задачу на довільну кількість менших підзадач, що дозволить виконати обчислення паралельно. Всі користуваць- кі задачі надходять на зовнішній інтер- фейс хмарного ЦОД і потрапляють на спеціальний вузол-планувальник, задачею якого є розподіл отриманих завдань між вузлами хмари відповідно до заданої по- літики планування. Отримавши свої підзадачі, вузли виконують обчислення і надсилають результати назад користува- чам, які виконують об’єднання результа- тів обчислень. Для побудови імітаційної моделі в програмному пакеті CloudSim було роз- роблено клас Scheduler, що представляє планувальник. Він містить дані про наявні задачі, що потребують обчислень, та віль- ні обчислювальні ресурси. Оперуючи та- кою інформацією, планувальник розподі- ляє задачі між вузлами відповідно до од- нієї з чотирьох змодельованих політик планування – Min-Min, Min-Max, Max- Min та Max-Max. Крім того, для коректно- го обчислення затримок, пов’язаних з пе- ресилкою даних мережею було доопра- цьовано механізм мережевої взаємодії, наявний в CloudSim таким чином, щоб він враховував будь-яку топологію локальної мережі хмарного ЦОД. На побудованій імітаційній моделі було проведено серію експериментів для випадку одного користувача, що намага- ється мінімізувати свій час, змінюючи розбиття задачі множення двох матриць розмірністю 1200x1200. Отримана залеж- ність часу виконання від кількості підза- дач у розбитті показана на рис. 2. Рис. 2. Графік залежності загального часу обчислень від кількості підзадач в розбитті Крім того, на імітаційній моделі було проведено ряд експериментів для двох гравців з аналогічними умовами (матриці 1200x1200, змінні розбиття) та різними по- літиками планування для підтвердження отриманих теоретично результатів. Графік для політики Min-Min показано на рис. 3, і він демонструє добру узгодженість з тео- ретичними результатами. Рис. 3. Графік залежності часу від розбиття для двох гравців при політиці Min- Min (виділено точку мінімуму) Експериментальні дані Для перевірки імітаційної моделі було створено сервісно-орієнтовану систему розподіленого виконання задач (рис. 4). Вона представляє собою декілька класичних REST [9] сервісів, які взаємо- діють між собою через HTTP протокол. Розпочнемо її опис з розгляду діаграми компонентів. Моделі та засоби паралельних і розподілених програм 21 Рис. 4. Компоненти системи виконання задач Користувачі надсилають свої задачі до сервісу планування (далі СП). В системі є лише один планувальник який упорядковує задачі згідно з обраною стратегією. Для експерименту було реалізовано чотири статичні стратегії планування: min-min, min-max, max-min та max-max [10]. Оскільки для даного дослідження було обрано задачу множення матриць, а саме її блочний алгоритм множення, то складність/вага задачі визначалася розміром блоку. У випадку коли обидва користувачі надсилали блоки однакової розмірності – порядок визначався випадково. Далі задачі надсилаються до сер- вісів виконання (далі СВ). В системі таких сервісів може бути багато й кожен з них представляє один або декілька виконавців які знаходяться в одному середовищі й займаються безпосередньо обробкою за- дач. Усі виконавці в межах кожного се- редовища гомогенні й мають індекс продуктивності згідно з яким СП обирає якому виконавцю надіслати задачу. Відстеженням статусу виконавців займа- ється сервіс планування. Під кожну задачу резервується окремий виконавець який вважається зайнятим доки СП не отримає результат задачі. Запити від СП обслуго- вуються асинхронно – СВ відповідає по- відомленням зі статус-кодом 202 (Accep- ted) [11] одразу після пересилки задачі виконавцю. СП розсилає задачі тільки коли в системі є вільні виконавці. Якщо таких немає – задачі чекають на ресурсі в черзі СП. СВ відповідає за надсилання результату обробки задачі виконавцем до СП. Як вже було вказано раніше – СП вивільняє виконавця тільки після того як отримає результат задачі від СВ. На цьому обробка задачі вважається завершеною й користувач може отримати її результат. Усі сервіси були написані на Java 8 з використанням Spring Framework 4.1. Для повідомлень використовувався формат JSON. До експерименту було залучено два середовища (рис. 5):  один вузол кластера з двома процесорами Quad Core Intel Xeon E5405 2GHz й 16 GB DDR2 @667 Mhz RAM спільної пам’яті;  ноутбук з процесором Intel Core i7 2.3 GHz (4 cores + HyperThreading) та 16 GB DDR3 @1600 MHz RAM. Наступна діаграма пояснює розташування компонентів системи (для компактності на ній не зображено сервіси виконання). Рис. 5. Експериментальне середовище Моделі та засоби паралельних і розподілених програм 22 Сервіс планування задач був розміщений на кластері разом з сервісом виконання з сімома виконавцями. На ноутбуці працював сервіс виконання й шість виконавців. Вплив декомпозиції задачі на час обчислень Варто зауважити що розмір розбиття вихідної задачі користувачем впливає не лише на порядок виконання задач а й на час розрахунків. Разом з розміром задачі змінюються часові затрати на пересилання даних й загальний “чис- тий” час обчислень. Останнє твердження варто пояснити більш детально. Для демонстрації розглянемо (рис. 6) залежність загального “чистого” часу мно- ження двох квадратних матриць розміром 1200х1200 елементів від величини розбиття (вісь абсцис) у другому се- редовищі (ноутбук). Рис. 6. Вплив декомпозиції Для розбиття 400х400 загальна кількість блоків рівна дев’яти і тому “чистий” час розраховується як 9 * Т400. Фактично це час, який потрібен на обрахування задачі на одному процесорі. Як видно з графіка – найкращий час маємо для розбиття на блоки розмірністю 600х600. За такого розбиття послідовне множення матриць буде виконуватися на 21% швидше ніж при розбитті на блоки по 200 елементів. Такий результат пояснюєть- ся тим що для обрахування такого блоку необхідно мати блок 1200х600 елементів першої матриці й 600х1200 з другої. Разом з результатом множення (600х600) це 1.8 млн. елементів. В експерименті множилися цілі числа типу Integer, який займає в Java 4 байта. Тому загальний обсяг необхідної пам’яті рівний ~6.86 МБ, що дуже близько до розміру L3 кеша (6 МБ). Тобто при множенні блоками 600х600 елементів усі данні майже повністю уміщуються в процесорний кеш, який значно швидший за оперативну пам’ять. Слід зауважити що така декомпози- ція не буде оптимальною за умови пара- лельного обчислення декількох блоків але ідея залишається незмінною – найкращий час буде у випадку з найбільш оптималь- ним використанням процесорного кешу. Висновки В роботі розвивається новий підхід до аналізу хмарних обчислень, який поля- гає у теоретико-ігровому моделюванні си- стеми планування та її взаємодії з користу- вачами. На прикладі задачі множення мат- риць була експериментально побудована гетерогенна кластерна система та реалізо- вано планувальник Мін-мін. Експеримен- тально отримані характеристики системи були використані для налаштування іміта- ційної моделі, розробленої у середовищі моделювання CloudSim. Це дозволило ви- міряти оцінку часу завершення роботи для всіх можливих комбінацій розбиття задач по процесорам та побудувати поверхню залежності часу закінчення роботи для ко- жного користувача. Отримані результати були обґрун- товані й узагальнені на базі теоретико- ігрового підходу, зокрема показано існу- вання точки рівноваги Неша для взаємодії двох користувачів та знайдені умови її Па- рето неефективності. 1. Wei, Guiyi, et al. A game-theoretic method of fair resource allocation for cloud computing services // The journal of supercomputing – 2010, 54.2. – P. 252–269. 2. Ігнатенко О.П., Парусімов Г.В., Синецький О.Б. Одна модель виконання обчислень у гетерогенних розподілених середовищах // Проблеми програмування. – 2015. – № 1. – С. 15–24. 3. Grosu D., Chronopoulos A.T. A Game- Theoretic Model and Algorithm for Load Balancing in Distributed Systems, Моделі та засоби паралельних і розподілених програм 23 Proceedings of IEEE IPDPS 2002, The 16th International Parallel and Distributed Processing Symposium, 4th Workshop on Advances in Parallel and Distributed Computational Models (APDCM'02), Fort Lauderdale, Florida, 15–19 April 2002. – P. 146–153. 4. Kameda, Hisao, and Eitan Altman Inefficient noncooperation in networking games of common-pool resources // Selected Areas in Communications, IEEE Journal on 26.7. – 2008. – P. 1260–1268. 5. Дорошенко А.Ю., Ігнатенко О.П., Іваненко П.А. Про одну модель оптимального роз- поділу ресурсів у багатопроцесорних сере- довищах // Проблеми програмування. – 2011. – № 1. – С. 21–28. 6. Naono K., Teranishi K., Cavazos J., Suda R. Software Automatic Tuning From Concepts to State-of-the-Art Results. Springer, 2010. 240 p. 7. Андон Ф.И., Игнатенко А.П. Моделирова- ние конфликтных процессов в сети Интер- нет // Кибернетика и системный анализ. – 2013. – № 4. – C. 153–162. 8. Ignatenko O., Synetskyi O. Evolutionary Game of N Competing AIMD Connections // In Information and Communication Tech- nologies in Education, Research, and Indust- rial Applications. Springer International Pub- lishing. – 2014. – P. 325–342. 9. Fielding R.T., Taylor R.N. Principled Design of the Modern Web Architecture // In Proceedings of the 2000 International Confe- rence on Software Engineering (ICSE 2000). Limerick, Ireland. – 2000. – C. 407–416. 10. Magoules F., Pan J., Teng F. Cloud Computing Data-Intensive Computing and Scheduling. Chapman & Hall/CRC. – 2012. – 231 p. 11. Http status code definitions: http://www.w3.org/Protocols/rfc2616/rfc2616 -sec10.html Одержано 25.03.2015 Про авторів: Ігнатенко Олексій Петрович, кандидат фізико-математичних наук, старший науковий співробітник, Іваненко Павло Андрійович, молодший науковий співробітник, Синецький Олександр Борисович, аспірант, Ніколенко Оксана Валеріївна, молодший науковий співробітник. Місце роботи авторів: Інститут програмних систем НАН України, 03187, Київ-187, Проспект Академіка Глушкова, 40. Тел.: 526 6025. E-mail: o.ignatenko@gmail.com http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html http://www.w3.org/Protocols/rfc2616/rfc2616-sec10.html mailto:o.ignatenko@gmail.com

Ігрова модель взаємодії користувачів у гетерогенних розподілених середовищах

Репозитарії

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