Теоретико-ігровий аналіз планувальників у багатопроцесорних системах. Імітаційна модель

Abstract

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

В работе исследуется игровая модель взаимодействия пользователей, выполняющих параллельные вычисления в гетерогенной многопроцессорной системе. Предложенный поход применяется к задаче умножения матриц с использованием планировщика мин-мин. Действием пользователей в этом случае является размер блоков, на которые разрезается матрица. Экспериментально полученные характеристики системы были использованы для настройки имитационной модели, что позволило измерить оценку времени завершения работы для всех возможных комбинаций разбиения задач по процессорам и построить поверхность времени окончания работы для каждого пользователя. Полученные результаты были обоснованы и обобщены на основе игрового подхода, в частности показано существования точки равновесия Неша в игре взаимодействия двух пользователей и найдены условия ее Парето неэффективности.

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.