=Paper= {{Paper |id=Vol-1844/10000088 |storemode=property |title=Game Theoretic Analysis of Multi-Processor Schedulers: Matrix Multiplication Example |pdfUrl=https://ceur-ws.org/Vol-1844/10000088.pdf |volume=Vol-1844 |authors=Oleksii Ignatenko |dblpUrl=https://dblp.org/rec/conf/icteri/Ignatenko17 }} ==Game Theoretic Analysis of Multi-Processor Schedulers: Matrix Multiplication Example== https://ceur-ws.org/Vol-1844/10000088.pdf 
Game Theoretic Analysis of Multi-Processor Schedulers:
          Matrix Multiplication Example


                                     Oleksii Ignatenko
                        1 Institute of Software Systems NAS Ukraine

                                o.ignatenko@gmail.com



       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 sched-
       uler 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 us-
       ers. We developed simulation model to verify the results.


       Keywords. parallel computing, schedulers, game theory, Nash equilibrium, Pa-
       reto efficiency.


       Key Terms. MathematicalModel, MultiAgentSystem, Infrastructure


1      Introduction

Modern scientific problems require significant computing resources, so the problem
of resource optimization in multiprocessor environments is very important. Nowa-
days, computing algorithms operate in complex heterogeneous environments. It is
common to have a distributed computational unit with many simultaneous programs
from different users competing for computing and network resources. In most cases,
the user is unable to control the distribution of resources. The allocation algorithms
may contain defects and inefficiency and this can lead to a significant increase in
processing time. That is why distributed computing requires efficient algorithms
providing a flexible and stable allocation of resources. The problem is to deal with
unfair and uneven access to resources, caused by heterogeneity of users and their
tasks where each user is a rational agent that tries to increase its share of resources.
This could bring the system to the inefficient equilibrium. A key element is an effi-
cient algorithm for load distribution – scheduler, providing services to users.
The idea of this work is to apply the game-theoretic approach to the problem of
scheduling and allocation of computing resources in a dynamic heterogeneous envi-
ronment with many competitive users.
In this work we consider heterogeneous multi-processor computing system and asso-
ciated constraint set a finite pool of processor resources (for each node), and limited
link capacity. Our goal is to specify work schedule for each node in the way that the
computing time (the time when the latest task is finished) is the smallest. This sched-
ule also should satisfy all defined constraints. This is the classical multiprocessor
scheduling problem, investigated in many works starting from [1]. It is well known
that this problem is NP-hard. One possible solution is to reduce scheduling complexi-
ty by using fluid model setup [2]. Another approach to this problem is to consider a
game-theoretic approach, which is the current trend in networks and computing sys-
tems [3]. In this work we construct static non-cooperative game for load balancing
problem in single-class job distributed systems. This problem is investigated by many
authors in cooperative (optimal) and game-oriented settings (see [4 - 7] for refer-
ences). Here, we propose a new analysis of scheduler for matrix multiplication prob-
lem in game setup. The proposed approach is applied to the problem of matrix multi-
plication on 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 eventually brings the system to an equilibrium state. This equilibrium is de-
fined by scheduler’s type, so characteristic of equilibrium is important for scheduling
policy analysis.
As a result, we presented conditions for the existence of Nash equlibrium end proved
Pareto inefficiency. Finally, we implement simulations using CloudSim package [8]
and provide experiments on a heterogeneous multi-processor system to verify simula-
tion and theoretic models.


2    Matrix Multiplication Model

      We consider an analytic computational model of parallel matrices multiplication
developed in papers [9, 10]. It is assumed that computation nodes cannot interact and
share data. Every node is connected with scheduler. Scheduler receives computational
tasks from users and sends them to an available processor (according to its resource
allocation algorithm). Every single processor works on its task and returns result. Let
us fix notation. Consider the heterogeneous multi-processor system of m computa-
tional elements, and every element has capacity 𝑝𝑖 , 𝑖 = 1, … , π‘š. Tasks are translated
by network lines, which are assumed to be identical and have capacity π‘ž.
     In this work it is assumed that:
      1. All processors start to work at the same time;
      2. Scheduler makes assignments instantly;
      3. Scheduling is deterministic.
We will proceed by building simple fluid model for matrices multiplication ignoring
transfer delays. Secondly, we provide generalization by including data transfer into
model. Finally, we consider discrete model, which is the closest to practice.




                                                                                     2
2.1    Simplified Fluid Model
    First, let us consider parallel multiplication of two square matrices 𝑁 Γ— 𝑁. Using
Block matrix multiplication algorithm user specifies block size 𝑛. Let the size of
                                              𝑁2
block 𝑛 be a natural number such that π‘˜ = 2 is a natural number too. The algorithm
                                            𝑛
will produce π‘˜ tasks, each with the complexity of 𝑂(𝑛2 ). Let 𝑇(𝑁, 𝑛) be the time
when all user’s tasks are finished. The problem of time optimal matrix multiplication
is the minimization function problem:
                                     𝑇(𝑁, 𝑛) β†’ π‘šπ‘–π‘›
      Function 𝑇(𝑁, 𝑛) has in general many local extremes, so searching for global
minimum could be resource demanding problem.
      Promising direction of research is the fluid model analysis [2]. Let the user
choose vector π‘₯(π‘˜) ∈ π‘…π‘š with components π‘₯𝑖 (π‘˜), where π‘₯𝑖 (π‘˜) β‰₯ 0, π‘₯𝑖 (π‘˜) ≀ π‘˜, 𝑖 =
1, … , π‘š, βˆ‘π‘š 𝑖=1 π‘₯𝑖 (π‘˜) = π‘˜. Denote 𝑋(𝑛) as the set of all vectors π‘₯(𝑛). Every compo-
nent π‘₯𝑖 (π‘˜) is the amount of computation designed for execution on i-th processor.
Firstly, we take into account only multiplication operation. This is a simplification but
it allows us to understand basic properties of the computation process.
    Finish time was found in [9] and is defined by the following formulae
                                                           π‘₯ 𝑁𝑛2
                                  𝑇(π‘₯, 𝑋(𝑛)) = max { 𝑖             }.
                                                𝑖=1,..,π‘š    𝑝𝑖
   The idea of the proposed approach is a fluid approximation to the problem. For the
approximation, we assume that work is composed of homogeneous fluid rather than
discrete jobs.
     Proposition 1. [9] Minimal task finish time (excluding transmit time) for a fluid
model with one user is equal 𝑇 = 𝑁 3 (βˆ‘π‘š           𝑖=1 𝑝𝑖 )
                                                            βˆ’1
                                                               and π‘Žπ‘Ÿπ‘”π‘šπ‘–π‘›(𝑇(π‘₯)) =
𝑁(𝑝1 , … , π‘π‘š ).
     In this work we employ general approach using convex analysis functions, which
we expect to be a promising direction for future investigation of more complex sys-
tems.
     Define Minkowski functional for set 𝑋 and vector 𝑝 ∈ π‘…π‘š as:
                               πœ‡π‘‹ (𝑝) = 𝑖𝑛𝑓{πœ† > 0: 𝑝 ∈ πœ†π‘‹}.
     It is known that Minkowski functional is convex for convex 𝑋. Let us define the
set of capabilities of the computation system 𝑅 = {π‘Ÿ ∈ π‘…π‘š : π‘Ÿπ‘– ∈ [0, 𝑝𝑖 ]} and rescale it
                         𝑅
as following: 𝑅(𝑛) = 2
                        𝑁𝑛
   Proposition 2. The following equality is true 𝑇(π‘₯, 𝑋(𝑛)) = πœ‡π‘…(𝑛) (𝑋).
   Proof. Consider right-hand side. It is clear thatπœ‡π‘…(𝑛) (π‘₯) = 𝑖𝑛𝑓{πœ† > 0: π‘₯ ∈
                                                                        π‘₯
πœ†π‘…(π‘₯)}. A Vector π‘₯ belongs to the set 𝑅 if and only if max { 𝑖 } = 1, so πœ‡π‘…(𝑛) (π‘₯) =
                                                             𝑖=1,..,π‘š 𝑝𝑖
                      π‘₯     πœ†                                                          π‘₯ 𝑁𝑛2
𝑖𝑛𝑓 {πœ† > 0: max { 𝑖 } =          }. This is equivalent to equality πœ† = max { 𝑖                 }.
             𝑖=1,..,π‘š 𝑝𝑖   𝑁𝑛2                                              𝑖=1,..,π‘š    𝑝𝑖
      Note. There is exists minimum π‘‡π‘šπ‘–π‘› = min πœ‡π‘…(𝑛) (π‘₯) and this minimum is
                                                   π‘₯βˆˆπ‘‹(𝑛)
unique.




                                                                                                    3
2.2    General Fluid Model
    To take into account transfer time we note, that block algorithm sends 2π‘₯𝑖 𝑁𝑛 el-
ements on each node and receives π‘₯𝑖 𝑛2 elements. So, summary time is equal to
                         π‘₯ 𝑁𝑛2     π‘₯ (𝑛2 +2π‘π‘š)
𝑇𝑠 (π‘₯, 𝑋(𝑛)) = max { 𝑖           + 𝑖          }.
               𝑖=1,…,π‘š    𝑝𝑖              π‘ž
   Proposition 3. There is minimum of 𝑇𝑠 (π‘₯, 𝑋(𝑛)) with respect to π‘₯ ∈ 𝑋(𝑛)
   Proof. X(n) is convex compact. Function Ts (x, X(n)) is continuous and convex,
so there is the minimum point.


2.3    Discrete Model and Schedulers
      Time minimization should be performed on finite net:
                    π‘Œ(𝑛) = {𝑦 ∈ π‘…π‘š : 𝑦𝑖 ∈ {0,1, … , π‘˜}, βˆ‘π‘– 𝑦𝑖 = π‘˜, 𝑖 = 1, . . , π‘š}.
      It is clear that π‘Œ(𝑛) βŠ‚ 𝑋(𝑛).
      Now we consider the notion of a scheduler.
      The user chooses the size of the block 𝑛 and π‘Œ(𝑛). The scheduler is an algorithm
responsible for specifying concrete point 𝑦 βˆ— ∈ π‘Œ(𝑛). In this work, we will consider
only simple scheduler of extreme – extreme type and perform simulations and inves-
tigation for min-min scheduler only. The min-min algorithm is quite popular and
simple. The idea of min-min is following.
      1. The scheduler receives π‘˜ tasks, every task has complexity 𝑁𝑛2 ;
      2. The scheduler chooses task with minimal computation complexity (in the
            case of equal tasks the choice is random);
      3. The scheduler sends chosen task on the free processor with maximal capaci-
            ty or waits in the case of no free resources.
      4. If the queue is not empty then return to 2.
   The result of algorithm is the pair of vector 𝑦 and finish time (finish time of the last
task)
   Fix the size of block 𝑛 and consider finish time.
      Proposition 4. For arbitrary 𝑛 following inequalities are true:
                       𝑇𝑑 (𝑛) = min 𝑇(𝑦, 𝑋(𝑛)) β‰₯ min 𝑇(π‘₯, 𝑋(𝑛))
                                 π‘¦βˆˆπ‘Œ(𝑛)             π‘₯βˆˆπ‘‹(𝑛)
                             π‘‡π‘šπ‘–π‘›π‘šπ‘–π‘› (𝑛) β‰₯ 𝑇𝑑 (𝑛)
    Proof. Here we give a sketch of proof. The first inequality is true because
π‘Œ(𝑛) βŠ‚ 𝑋(𝑛). The second inequality holds since 𝑇𝑑 (𝑛) is minimum by definition.


3     Non-Cooperative Scheduling Game Formulation

      We will deal with non-cooperative games in strategic or normal form. A non-
cooperativeness here does not imply that the players do not cooperate, but it means
that any cooperation must be self-enforcing without any coordination among the play-
ers. The strict definition is as follows.
      A non-cooperative game in strategic (or normal) form is a triplet 𝐺 =
{𝑁, {𝑆𝑖 }π‘–βˆˆπ‘ , {𝑒𝑖 }π‘–βˆˆπ‘ } , where:
      β€’ 𝑁 is a finite set of players;




                                                                                         4
      β€’ 𝑆𝑖 is the set of admissible strategies for player i.
      β€’ 𝑒𝑖 : 𝑆 β†’ 𝑅 is the utility (payoff) function for player i.
      A game is said to be static if the players take their actions only once, inde-
pendently of each other. In some sense, a static game is a game without any notion of
time, where no player has any knowledge of the decisions taken by the other players.
      Based on the assumption that all players are rational, the players try to maximize
their payoffs when responding to other players’ strategies. Generally speaking, the
final result is determined by non-cooperative maximization of integrated utility. In
this regard, the most accepted solution concept for a non-cooperative game is Nash
equilibrium [3], introduced by John F. Nash. Loosely speaking, Nash equilibrium is a
state of a non-cooperative game where no player can improve its utility by changing
its strategy if the other players maintain their current strategies. Formally, pure-
strategy Nash equilibrium (NE) of a non-cooperative game 𝐺 is a strategy profile 𝑠 βˆ— ∈
𝑆 such that for all 𝑖 ∈ 𝑁 we have the following:
                             𝑒𝑖 (π‘ π‘–βˆ— , π‘ βˆ’π‘–
                                        βˆ—                βˆ—
                                           ) β‰₯ 𝑒𝑖 (𝑠𝑖 , π‘ βˆ’π‘– ) for all 𝑠𝑖 ∈ 𝑆𝑖 .
      Here π‘ βˆ’π‘– denotes the vector of strategies of all players except i. In other words, a
strategy profile is a pure-strategy Nash equilibrium if no player has an incentive to
unilaterally deviate to another strategy, given that other players’ strategies remain fixed.
      Let us formulate scheduling game for matrix multiplication problem. Players are
users of distributed system. Define the set of players as {𝑒𝑖 }π‘–βˆˆπΏ , where 𝐿 is set of
indexes. Users have available multi-processors system with π‘š computational elements.
Each element has capacity 𝑝𝑖 , 𝑖 = 1, . . , π‘š. We assume every user has two square
matrices with dimension 𝑛𝑙 , 𝑙 ∈ 𝐿. The set of admissible strategies for player l is a
conjunction of all possible cuts π‘˜π‘™ ∈ 𝐾𝑙 , , 𝑙 ∈ 𝐿. After the player chooses his strategy
blocks are translated to a scheduler, which sends them to processors.
      Define finish time for l-th player as the time of finishing of last task 𝑇𝑙 , 𝑙 ∈ 𝐿.
Every player wants to minimize his finish time.
     In current work we consider problem when:
      1. The min-min scheduler is used.
      2. The set of admissible sizes {𝑛𝑗 }𝑗=1,..,𝑠 is sorted in ascending order.
     3. If players choose the same sizes, their finish times are the same. Finish time
             in this case is equal to double individual time for this size.
     4. There is unique minimum 𝑇𝑑 (𝑛𝑗 ), 𝑗 = 1, … , 𝑠. Denote argminimum index as
             𝑗 βˆ—.
     5. There are two players in the system.
     In order to use game theory methods, we build the game matrix, using following
rules. Let players choose strategies 𝑛1 , 𝑛2 . Denote their payoffs as 𝑇1 (𝑛1 , 𝑛2 ) and
𝑇2 (𝑛1 , 𝑛2 ) respectively.
     1. If 𝑛1 < 𝑛2 , then 𝑇1 (𝑛1 , 𝑛2 ) = 𝑇𝑑 (𝑛1 ), 𝑇2 (𝑛1 , 𝑛2 ) = 𝑇𝑑 (𝑛1 ) + 𝑇𝑑 (𝑛2 ).
     2. If 𝑛1 = 𝑛2 , then 𝑇1 (𝑛1 , 𝑛1 ) = 𝑇2 (𝑛1 , 𝑛1 ) = 2𝑇𝑑 (𝑛1 ).
     Proposition 5. If there is exists 𝑗 βˆ— such that inequality 2𝑇𝑑 (𝑛𝑗 βˆ— ) ≀
𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ) holds, then (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) – Nash equilibrium.
     Proof. By definition (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) is Nash equilibrium if:
                     𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) ≀ 𝑇1 (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ— ), 𝑇2 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) ≀ 𝑇2 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— βˆ’1 ).
     Using rules, defined above we obtain:




                                                                                                     5
                             𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) = 2𝑇𝑑 (𝑛𝑗 βˆ— ), 𝑇1 (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ— ) = 𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ).
      The same is valid for the second player. If inequality 2𝑇𝑑 (𝑛𝑗 βˆ— ) ≀
𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ) holds, (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) – Nash equilibrium.
      Proposition 6. If there is exists 𝑗 βˆ— such that inequality 2𝑇𝑑 (𝑛𝑗 βˆ— ) β‰₯
𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ) holds, then (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ— βˆ’1 ) – Nash equilibrium.
      Proof. By definition (𝑛𝑗 βˆ— βˆ’1 , 𝑛𝑗 βˆ— βˆ’1 ) is Nash equilibrium if:
                        𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) β‰₯ 𝑇1 (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ— ), 𝑇2 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) β‰₯ 𝑇2 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— βˆ’1 ).
      Using rules, defined above we obtain:
                𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— βˆ’1 ) = 𝑇𝑑 (𝑛𝑗 βˆ—βˆ’1 ) + 𝑇𝑑 (𝑛𝑗 βˆ— ), 𝑇1 (𝑛𝑗 βˆ— βˆ’1 , 𝑛𝑗 βˆ—βˆ’1 ) = 2𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ).
      The same is valid for the second player. If inequality 2𝑇𝑑 (𝑛𝑗 βˆ— ) β‰₯
𝑇𝑑 (𝑛𝑗 βˆ— βˆ’1 ) holds, then 𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— βˆ’1 ) β‰₯ 𝑇1 (𝑛𝑗 βˆ— βˆ’1 , 𝑛𝑗 βˆ— ) and (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ—βˆ’1 ) – Nash equi-
librium.
      Note. Nash equilibrium is always Pareto-inefficient, in other words
𝑇1 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) ≀ 𝑇1 (𝑛𝑗 βˆ— βˆ’1 , 𝑛𝑗 βˆ— ), 𝑇2 (𝑛𝑗 βˆ— , 𝑛𝑗 βˆ— ) ≀ 𝑇2 (𝑛𝑗 βˆ—βˆ’1 , 𝑛𝑗 βˆ— ). This is common situation
in games of considered type.


4       Simulations

   We have implemented simulations using CloudSim package and real multi-
processing system of Institute of Software Systems NAS Ukraine. The experiments
were designed to optimize finish time for one user. Matrices of 1200 on 1200 dimen-
sion were used. The experiment was performed on the node with two processors Quad
Core Intel Xeon E5405 2GHz and 16 GB DDR2 @667 Mhz RAM (making 7 slave
servers and 1 scheduler node).
   The graph of Time-Size dependency is shown in the Fig. 1.




                               Fig. 1. Finish time – size of task graph




                                                                                                         6
    Using estimation of the main parameters from experiments we have built the simu-
lation model for scheduling game with two players (1200x1200 matrix, strategies –
size of tasks) and min-min scheduler. Results are shown in the Fig 2.




     Fig. 2. Finish time surface for scheduling game of two players. Real experiments
          approximation (left) and simulation using theoretic construction (right)


5        Conclusions

   In this paper, we have presented the approach to deal with problems of scheduling
and load balancing using a game-theoretic framework. The general objective was to
identify and address the efficiency problems, where game theory can be applied to the
model and evaluate user conflicts problems and consequently to design efficient solu-
tion. We consider the fluid model of computations to calculate the "ideal" finish time,
which gives the lower bound of possible real time. We propose the game model of
user's interaction on the example of matrix multiplication problem. We use simulation
environment GridSim to obtain experimental data and validate theoretical results.
   We investigate the interaction model's users performing parallel computing in a
heterogeneous multiprocessor system. The proposed hike is applied to the problem of
matrix multiplication using the scheduler min-min. Resolving this case is the size of
the blocks into which the matrix is cut. The experimental system characteristics have
been used to adjust the simulation model, allowing to measure the time estimate for
completion of all possible combinations of partitioning tasks to processors and end
time to build finish time surface for each user. The findings were substantiated and
summarized based on the game approach, in particular, found the conditions of Nash
equilibrium point existence in the game interaction between two users.


References
1.    Srinivasa Prasanna G.N., Musicus B. Generalized Multiprocessor Scheduling Using Opti-
      mal Control // Proc. SPAA. – 1991, P. 216 – 228.
2.    Nazarathy Y., Weiss G. A Fluid Approach to Large Volume Job Shop Scheduling // Jour-
      nal of Scheduling, 13(5), 509-529, (2010).
3.    Han, Zhu, et al. Game theory in wireless and communication networks. Cambridge Uni-
      versity Press, 2012.




                                                                                         7
4.  S. Penmatsa, A. T. Chronopoulos. Game-theoretic static load balancing for distributed
    systems. Journal of Parallel and Distributed Computing 71, no. 4 (2011): 537-555
5. Wei, Guiyi, et al. A game-theoretic method of fair resource allocation for cloud computing
    services. The journal of supercomputing 54.2 (2010): 252-269.
6. Siar, Hajar, Kourosh Kiani, and Anthony T. Chronopoulos. An effective game theoretic
    static load balancing applied to distributed computing. Cluster Computing 18.4 (2015):
    1609-1623.
7. Li, Kai, Yong Wang, and Meilin Liu. A non-cooperative game model for reliability-based
    task scheduling in cloud computing. arXiv preprint arXiv:1403.5012 (2014).
8. https://en.wikipedia.org/wiki/CloudSim
9. Anatoly, Doroshenko, Ignatenko Oleksii, and Ivanenko Pavlo. One model of optimal
    resource allocation in homogeneous multiprocessor system // Problems in programming 1
    (2011): 29-39.
10. Andon, F. I., and O. P. Ignatenko. "Modeling conflict processes on the internet." Cyber-
    netics and Systems Analysis 49.4 (2013): 616-623.
11. Ignatenko, O., Synetskyi, O. (2014). Evolutionary Game of N Competing AIMD Connec-
    tions. In Information and Communication Technologies in Education, Research, and In-
    dustrial Applications (pp. 325-342). Springer International Publishing.




                                                                                           8