Game-theory analysis of multi-processor schedulers. Simulation model
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 wh...
Saved in:
| Date: | 2018 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
PROBLEMS IN PROGRAMMING
2018
|
| Subjects: | |
| Online Access: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/268 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Problems in programming |
| Download file: |  |
Institution
Problems in programming| _version_ | 1859501735966408704 |
|---|---|
| author | Ignatenko, O.P. Odobesku, V.I. |
| author_facet | Ignatenko, O.P. Odobesku, V.I. |
| author_sort | Ignatenko, O.P. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2024-04-28T11:37:23Z |
| description | 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.Problems in programming 2018; 2-3: 075-082 |
| first_indexed | 2025-07-17T10:05:08Z |
| format | Article |
| fulltext | |
| id | pp_isofts_kiev_ua-article-268 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:05:08Z |
| publishDate | 2018 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/19/64c8f71e0d00c7d5a23e943c07674819.pdf |
| spelling | pp_isofts_kiev_ua-article-2682024-04-28T11:37:23Z Game-theory analysis of multi-processor schedulers. Simulation model Теоретико-игровой анализ планировщиков в многопроцессорных системах. имитационная модель Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель Ignatenko, O.P. Odobesku, V.I. parallel scheduling; game theory; fluid model; Nash equilibrium; simulation UDC 004.7 параллельные вычисления; теория игр; потоковая модель; равновесие Неша; имитационная модель УДК 004.7 паралельні обчислення; теорія ігор; рівновага Неша; імітаційна модель УДК 004.7 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.Problems in programming 2018; 2-3: 075-082 В работе исследуется игровая модель взаимодействия пользователей, выполняющих параллельные вычисления в гетерогенной многопроцессорной системе. Предложенный поход применяется к задаче умножения матриц с использованием планировщика мин-мин. Действием пользователей в этом случае является размер блоков, на которые разрезается матрица. Экспериментально полученные характеристики системы были использованы для настройки имитационной модели, что позволило измерить оценку времени завершения работы для всех возможных комбинаций разбиения задач по процессорам и построить поверхность времени окончания работы для каждого пользователя. Полученные результаты были обоснованы и обобщены на основе игрового подхода, в частности показано существования точки равновесия Неша в игре взаимодействия двух пользователей и найдены условия ее Парето неэффективности.Problems in programming 2018; 2-3: 075-082 В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчислення у гетерогенній багатопроцесорній системі. На прикладі задачі множення матриць побудований підхід до потокового моделювання процесів планування. Пропонується ігрова модель взаємодії, де стратегіями є вибір блоку розрізання матриці. Знайдені оцінки стану рівноваги та проведені експерименти, що підтверджують теоретично отримані результати. Побудована імітаційна модель, яка демонструє точки рівноваги Неша у грі взаємодії користувачів.Problems in programming 2018; 2-3: 075-082 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-11-05 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/268 10.15407/pp2018.02.075 PROBLEMS IN PROGRAMMING; No 2-3 (2018); 75-82 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2018); 75-82 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2018); 75-82 1727-4907 10.15407/pp2018.02 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/268/262 Copyright (c) 2018 PROBLEMS OF PROGRAMMING |
| spellingShingle | parallel scheduling game theory fluid model Nash equilibrium simulation UDC 004.7 Ignatenko, O.P. Odobesku, V.I. Game-theory analysis of multi-processor schedulers. Simulation model |
| title | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_alt | Теоретико-игровой анализ планировщиков в многопроцессорных системах. имитационная модель Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_full | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_fullStr | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_full_unstemmed | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_short | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_sort | game-theory analysis of multi-processor schedulers. simulation model |
| topic | parallel scheduling game theory fluid model Nash equilibrium simulation UDC 004.7 |
| topic_facet | parallel scheduling game theory fluid model Nash equilibrium simulation UDC 004.7 параллельные вычисления теория игр потоковая модель равновесие Неша имитационная модель УДК 004.7 паралельні обчислення теорія ігор рівновага Неша імітаційна модель УДК 004.7 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/268 |
| work_keys_str_mv | AT ignatenkoop gametheoryanalysisofmultiprocessorschedulerssimulationmodel AT odobeskuvi gametheoryanalysisofmultiprocessorschedulerssimulationmodel AT ignatenkoop teoretikoigrovojanalizplanirovŝikovvmnogoprocessornyhsistemahimitacionnaâmodelʹ AT odobeskuvi teoretikoigrovojanalizplanirovŝikovvmnogoprocessornyhsistemahimitacionnaâmodelʹ AT ignatenkoop teoretikoígrovijanalízplanuvalʹnikívubagatoprocesornihsistemahímítacíjnamodelʹ AT odobeskuvi teoretikoígrovijanalízplanuvalʹnikívubagatoprocesornihsistemahímítacíjnamodelʹ |