В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчислення у гетерогенній багатопроцесорній системі. На прикладі задачі множення матриць побудований підхід до потокового моделювання процесів планування. Пропонується ігрова модель взаємодії, де стратегіями є вибір блоку розрізання матриці. Знайдені оцінки стану рівноваги та проведені експерименти, що підтверджують теоретично отримані результати. Побудована імітаційна модель, яка демонструє точки рівноваги Неша у грі взаємодії користувачів. Ключові слова: паралельні обчислення, теорія ігор, рівновага Неша, імітаційна модель. В работе исследуется игровая модель взаимодействия пользователей, выполняющих параллельные вычисления в гетерогенной многопроцессорной системе. Предложенный поход применяется к задаче умножения матриц с использованием планировщика мин-мин. Действием пользователей в этом случае является размер блоков, на которые разрезается матрица. Экспериментально полученные характеристики системы были использованы для настройки имитационной модели, что позволило измерить оценку времени завершения работы для всех возможных комбинаций разбиения задач по процессорам и построить поверхность времени окончания работы для каждого пользователя. Полученные результаты были обоснованы и обобщены на основе игрового подхода, в частности показано существования точки равновесия Неша в игре взаимодействия двух пользователей и найдены условия ее Парето неэффективности. Ключевые слова: параллельные вычисления, теория игр, потоковая модель, равновесие Неша, имитационная модель. This paper deals with a game model of users performing parallel computing in a heterogeneous multiprocessor system. The proposed approach is applied to the problem of matrix multiplication on the system with the scheduler of min-min type. The user's action is to choose the size of the blocks into which the matrix is cut. Each user tries to optimize own finish time, which leads to conflict. Using the game theoretic approach, we build game model and found the conditions of Nash equilibrium existence in the scheduling game of two users. Simulation program was built to provide experimental data.
1. Теоретико-ігрове моделювання процесів планування
Планувальник здійснює призначення миттєво.
Нехай задані дві квадратні матриці розмірності N N , результат множення яких необхідно обчислити. При використанні блочного алгоритму користувач задає розмір блоку n , в результаті чого формуються k
N 2
2 задач, кожна з яких буде мати складність O(n2 ) . Припустимо, що планувальник забезпечує пересилку n повідомлень на вузли за певним фіксованим алгоритмом, який завершує обчислення за час T (N , n) . Тоді задача користувача полягає у пошуку мінімуму функції:
T ( N , n) min .
Функція T (N , n) , взагалі кажучи, може мати багато локальних мінімумів (в залежності від обчислювальної системи та планувальника) оскільки існує мінімальна фіксована величина задачі.
Одним з розповсюджених підходів до аналізу таких задач полягає у дослідженні потокової моделі даного процесу [3].
Припустимо, що користувач вибрав вектор x Rm з компонентами xi , де xi 0 , xi k , i 1,..., m , k xi k . Всі таки вектори утворюють множину X (n) . Кожен компонент вектора x описує відсоток задач, i1 призначених для виконання на i -тому процесорі. Будемо брати до уваги тільки операції, множення. Таке спрощення дозволяє у явному вигляді виписати функції часу. Загальний час закінчення залежить від x , та дорівнює
T (x, X (n)) max xi Nn 2
.
i1,...,m pi Потокова модель передбачає можливість розділення задачі на «шматочки» розміру Nn2 , компонування з них підходящих підзадач та визначення загального часу при 0 .
Твердження 1 [6]. Мінімальний час закінчення обчислень (без пересилок) для потокової моделі з одним m 1 користувачем дорівнює T N 3 pi . Відповідно, користувач, для досягнення оптимального часу, має i1 розділити свою задачу таким чином, щоб вузол i отримав piT обчислень.
Функція Мінковського для множини X та вектора p Rm визначається наступним чином: Відомо, що ця функція опукла для опуклої X . Визначимо множину потужностей системи R r Rm : ri [0, pi ] та масштабуємо її наступним чином: Доведення. Розглянемо праву частину: R(n) (x) inf{ 0 : x R(n)} . Умова належності вектора x множині R записується у вигляді max xi
1 , отже i1,...,m pi Тоді X ( p) inf{ 0 : p X } .
R(n) 1
Nn2
R .
T (x, X (n)) R(n) (x) .
R(n) (x) inf 0 : max xi i1,...,m pi
.
Nn 2 В іншому вигляді max xi Nn2
. З властивостей функції R(n) (x) випливає, що мінімальний час i1,...,m pi Tmin xmXi(nn) R(n) (x) існує і єдиний. Для врахування пересилок потрібно зазначити, що алгоритм надсилає 2xi Nn елементів на відповідний вузол та приймає xin2 елементів. Отже, сумарний час закінчення з урахуванням пересилок дорівнює Твердження 2 [6]. Існує мінімум часу по x –
Ts (x, X (n)) max xi Nn2 xi n2 2Nn .
i1,...,m pi q xmXi(nn)Ts (x, X (n)) . Дискретна модель обчислення множення матриць. Нехай розмір блоку n може бути тільки цілим числом, причому таким, щоб k N 2 n2 теж було цілим. Тоді мінімізація часу буде проводитись по скінченній множині точок y Rm : yi {0,1,.., k}, Y (n) yi k,i 1,.., m .
i
Y (n) X (n) . Зрозуміло, що Введемо поняття планувальника. Спочатку користувач вибирає розмір блоку n , в результаті чого формується множина Y (n) . Ця множина описує всі можливі розташування задач на процесорах.
Планувальник відповідає за вибір конкретного y* Y (n) . В даній роботі ми розглянемо прості планувальники типу extr extr . Один з широко вживаних планувальників такого типу називається min min і він вибирає розподіл за наступним алгоритмом: 1)
формується черга з k задач, кожна обсягом обчислень Nn 2 ; 2) вибирається задача з найменшим обсягом обчислень. (в даній роботі розглядається випадок однакових задач, тому вибирається довільна);
3) задача надсилається на вільний процесор з найбільшою потужністю (тобто мінімізується час виконання), якщо вільних процесорів немає, чекаємо поки з’явиться; 4)
якщо залишились задачі у черзі, то повертаємось до пункту 2. Твердження 3. [6] Для будь-якого n виконуються нерівності:
Td (n) min T ( y, X (n)) min T (x, X (n)) .
yY (n) xX (n) 2. Некооперативна ігрова модель планування множення матриць Некооперативна гра описує ситуацію прийняття рішень гравцями за умов конфлікту інтересів. Під терміном гравець тут ми розуміємо користувача, який впливає на систему шляхом вибору стратегій – дій, які він може застосовувати. В залежності від дій його та інших учасників відбувається визначення виграшів гравців. Говорять, що гравець раціональний, якщо його дії спрямовані на максимізацію власного виграшу.
Якщо у грі приймають участь хоча б двоє учасників, можлива ситуація, коли перший гравець може покращити свій виграш за рахунок зменшення виграшу інших. В такому випадку кажуть про конфліктну взаємодію. Частинним випадком конфлікту є ситуація повністю протилежних інтересів - коли виграш одного є програшем іншого. Такі ігри називають антагоністичними або іграми з нульовою сумою. Зауважимо, що некооперативність не означає, що гравці взагалі не кооперуються, а тільки те, що немає зовнішніх причин, які б спричиняли координацію або узгодження їх стратегії. Будь-яка кооперація що може виникнути має виходити зі структури гри і визначатися функціями корисності учасників.
Гру називають статичною, якщо гравці приймають свої рішення одноразово, незалежно один від одного. В певному розумінні, статична гра не залежить від часу. Навіть якщо гравці приймають рішення протягом певного часового інтервалу, якщо вони не володіють інформацією щодо дій інших гравців, така гра є статичною.
У динамічних іграх гравці отримують певну інформацію щодо рішень інших учасників і можуть змінювати свою стратегію у часі, тобто приймають рішення більше одного разу. Динамічні ігри є найбільш складним для аналізу і відіграють важливу роль у дослідженні процесів у мережах [5, 6].
Опишемо задачу множення матриць у вигляді статичної некооперативної гри. Основні визначення.
При визначенні статичних ігор загальновживаною є стратегічна або нормальна форма, яка включає опис трьох компонентів: множини гравців, їх стратегій і виграшів.
Гравцями в даному випадку являються користувачі uiiL , L – множина індексів, які мають доступ до спільного ресурсу з m обчислювальних елементів з швидкістю роботи pi , i 1,..., m . Будемо вважати, що для кожного користувача задані квадратні матриці розмірності nl , l L . Тоді стратегіями користувачів є допустиме розбиття матриць на блоки kl Kl , l L . Після розбиття матриць, блоки потрапляють у планувальник, який надсилає їх на процесори згідно з певним визначеним алгоритмом роботи. Часом закінчення обчислень Tl , l L будемо називати час закінчення останньої задачі користувача ul . Кожен користувач намагається зменшити свій час закінчення і через обмеженість спільних ресурсів виграш одного користувача спричинить програш інших.
Будемо вважати, що виконуються наступні припущення: 1.
Вибрана множина можливих розмірів n j j1,...,s – стратегій користувачів, впорядкована за збільшенням.
2. Якщо користувачі вибрали однакові розміри блоків, то їх час завершення однаковий і дорівнює подвоєному індивідуальному часу для даного розміру блоку.
3.
Існує єдиний мінімум Td (n j ), j 1,..., s . Позначимо індекс стратегії, на якій він досягається j* . Планувальники мін-мін та макс-мін. Побудуємо платіжну матрицю гри за наступними правилами. Нехай гравці вибрали стратегії n1, n2 відповідно. Позначимо їх виграші T1(n1, n2 ) , T2 (n1, n2 ) 1. 2. 3.
Якщо n1 n2 , то виграш першого користувача дорівнює Td (n1) , другого Td (n1) Td (n2 ) . Якщо n1 n2 , то виграш першого користувача дорівнює Td (n1) Td (n2 ) , другого Td (n2 ) . Якщо n1 n2 , то виграш першого і другого користувача дорівнює 2Td (n1) .
Твердження 4. Нехай виконуються нерівність 2Td (n j* ) Td (n j*1) , тоді пара стратегій (n j* , n j* ) – рівновага Неша. В іншому разі рівновагою Неша будуть пара стратегій (n j*1, n j*1) .
Наслідок. Отримана рівновага Парето неефективна.
T1(n j* , n j* ) T1(n j*1, n j*1) , T2 (n j* , n j* ) T2 (n j*1, n j*1) . Це досить характерна ситуація для ігор такого типу.
Планувальники макс-макс та мін-макс.
Твердження 5. Нехай виконуються нерівність 2Td (n j* ) Td (n j*1) , тоді пара стратегій (n j*1, n j*1) – рівновага Неша. В іншому разі рівновагою Неша будуть пара стратегій (n j* , n j* )
3. Побудова імітаційної моделі Імітаційна модель дозволяє симулювати процес множення матриць у розподіленому середовищі враховуючи як час на власне обчислення так і передачу даних.
Розглянемо задачу множення двох N * N матриць M1 та M2. Позначимо за n кількість рядків матриці М1 та відповідно стовбців матриці М2. Таким чином отримуємо 2 підматриці n * N та N * n які і формують N N одну задачу, що буде відіслана планувальнику. Таких задач буде n * n . Проте в обох матрицях М1 та М2 у випадку якщо n не дільник N буде залишок рядків М1 та стовбців М2 відповідно. Позначимо розмір N залишка за m N n * . Тому до основних задач ще потрібно додати задачі множення матриць m * N та n N * n , матриць n * N та N * m і задачу множення m * N та N * m .
Тобто задача множення матриць (N,N) та (N,N) розбивається на такі підзадачі: 1. 2. 3.
Множення матриць N1* N 2 та N 2 * N3 потребує N1* N 3 * N 2 операцій множення та N1* N 3 * ( N 2 1) операцій додавання. Позначимо за AM коефіцієнт складності операції множення по відношенню до операції додавання. Тоді складність множення матриць N1* N 2 та N 2 * N3 можна виразити у одиницях операцій додавання як
C ( N1, N 2, N 3) N1* N 3 * (N 2 * AM N 2 1) . маючи складність задачі С ( кількість операцій додавання ) отримаємо t p Позначивши потужність обчислювального модуля за P ( кількість операцій додавання / секунду ) та C
.
P Також для множення матриць N1* N 2 та N 2 * N3 потрібно переслати N1* N 2 N 2 * N3 елементів до обчислювального вузла, та отримати результат у розмірі N1* N 3 елементів. Час на передачу даних обчислюється як tt latency N1* N 2 N 2 * N 3 N1* N 3 .
bandwidth Загальний час на обробку задачі t t p tt .
Для двох гравців вибираються n1 та n2, формуються задачі, додаються в загальний список та випадково перемішуются і подаються на планувальник. Час для кожного з гравців визначається як час прибуття від планувальника до гравця останньої його задачі. Симуляція реалізована у вигляді утиліти з параметрами консолі та дозволяє вибирати значення N, bandwidth, latency, потужності обчислювальних вузлів як множники номінальної потужності та межі перебору параметрів n1 і n2. Програма написана на мові C++ та умовно поділяється на дві логічні частини: модуль обробки параметрів та модуль симуляції.
Модуль обробки параметрів дозволяє задавати розмір матриць, режим одного гравця чи двох, межі перебору стратегій розрізання, параметри планувальника, характеристики обчислювальних модулів, параметрів мережі – bandwidth та latency без перекомпіляції програми через параметри командного рядка. Модуль симуляції генерує задачі для кожного з користувачів, зливає їх в один список та власне подає їх на симулятор, який повертає оброблені задачі з проставленими змінними часу початку та завершення роботи над задачею і номером обчислювального вузла, який обробляю цю задачу.
Етапи роботи симулятора:
перемішування списку очікуючих задач з метою емуляцїї отримання задач у випадковому порядку. 2) сортування списку очікуючих задач по складності у відповідності до пріорітетності задач та списку обчислювальних вузлів по потужності у відповідності до пріорітетності обчислювальних вузлів. Наприклад для minmax планувальника список очікуючих задач буде відсортованим від простої до складної, а список обчислювальних вузлів від потужного до повільного.
3) ініціалізація початкових задач для обчислювальних вузлів вилучаючи перші елементи з відсортованих списків очікуючих задач та вузлів, проставлення початкового часу, який на даний момент рівний 0, та обчислення часу очікуваного завершення виконання задачі. Структури з посиланням на задачу, обчислювальний вузол та даними про початок та завершення виконання задачі поміщаються у чергу з пріорітетом по найменшому часу завершення.
4) взяти з пріорітетної черги задачу, яка буде найближчою по часу наступною виконаною задачею. Прийняти час симуляції за час завершення взятої з черги задачі, додати задачу до списку виконаних задач разом із даними про час її завершення.
5) якщо список очікуючих задач не пустий, то вилучити перший елемент, поставити час початку як час симуляції, обчислити час завершення та додати у чергу з прірітетом, поставивши обчислювальний вузол як перший вільний із відсортованого списку вузлів.
6)
якщо пріорітетна черга не пуста, то повернутися на крок 4.
7) знайти у списку виконаних задач найпізніші повернені задачі для кожного з користувачів та повернути їх час завершення. Результати експериментів Рис. 1. Графік t від n для одного bandwidth = 1e9 для 3, 4 та 5 обчислювальних вузлів користувача при latency = 0.0, Рис. 2. Графік t від n для одного користувача при latency = 0.0, bandwidth = 1e9 та 3 обчислювальних вузлах Висновки
В роботі було розглянуто задачу ігрового моделювання процесів планування багатопроцесорними обчисленнями на прикладі задачі множення матриць. Отримані теоретичні оцінки існування стану рівноваги у грі планування двох користувачів для різних типів планувальників. Показано, що планувальники типу extr-extr розділяються на дві групи, як у певному сенсі є оберненими одна до другою (твердження 4 і 5). Показано, що отриманий стан рівноваги Неша є Парето-неефективним.
Побудована імітаційна модель на мові С++ та підтверджено теоретичні результати. Література 1. 2. 3. 4.