Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель
В даній роботі досліджується ігрова модель взаємодії користувачів, що виконують паралельні обчислення у гетерогенній багатопроцесорній системі. На прикладі задачі множення матриць побудований підхід до потокового моделювання процесів планування. Пропонується ігрова модель взаємодії, де стратегіями є...
Saved in:
| Published in: | Проблеми програмування |
|---|---|
| Date: | 2018 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/144585 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель / О.П. Ігнатенко, В.Я. Одобеску // Проблеми програмування. — 2018. — № 2-3. — С. 75-82. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862616200350007296 |
|---|---|
| author | Ігнатенко, О.П. Одобеску, В.Я. |
| author_facet | Ігнатенко, О.П. Одобеску, В.Я. |
| citation_txt | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель / О.П. Ігнатенко, В.Я. Одобеску // Проблеми програмування. — 2018. — № 2-3. — С. 75-82. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблеми програмування |
| 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.
|
| first_indexed | 2025-12-07T13:09:05Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-144585 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T13:09:05Z |
| publishDate | 2018 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Ігнатенко, О.П. Одобеску, В.Я. 2018-12-30T16:52:29Z 2018-12-30T16:52:29Z 2018 Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель / О.П. Ігнатенко, В.Я. Одобеску // Проблеми програмування. — 2018. — № 2-3. — С. 75-82. — Бібліогр.: 7 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/144585 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. uk Інститут програмних систем НАН України Проблеми програмування Паралельне програмування. Розподілені системи і мережі Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель Game-theory analysis of multi-processor schedulers. Simulation model Article published earlier |
| spellingShingle | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель Ігнатенко, О.П. Одобеску, В.Я. Паралельне програмування. Розподілені системи і мережі |
| title | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_alt | Game-theory analysis of multi-processor schedulers. Simulation model |
| title_full | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_fullStr | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_full_unstemmed | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_short | Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель |
| title_sort | теоретико-ігровий аналіз планувальників у багатопроцесорних системах. імітаційна модель |
| topic | Паралельне програмування. Розподілені системи і мережі |
| topic_facet | Паралельне програмування. Розподілені системи і мережі |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144585 |
| work_keys_str_mv | AT ígnatenkoop teoretikoígroviianalízplanuvalʹnikívubagatoprocesornihsistemahímítacíinamodelʹ AT odobeskuvâ teoretikoígroviianalízplanuvalʹnikívubagatoprocesornihsistemahímítacíinamodelʹ AT ígnatenkoop gametheoryanalysisofmultiprocessorschedulerssimulationmodel AT odobeskuvâ gametheoryanalysisofmultiprocessorschedulerssimulationmodel |