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. We developed simulation model to verify the results.
Modern scientific problems require significant computing resources, so the problem of resource optimization in multiprocessor environments is very important. Nowadays, 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.
cient algorithm for load distribution – scheduler, providing services to users.
scheduling and allocation of computing resources in a dynamic heterogeneous environment with many competitive users.
In this work we consider heterogeneous multi-processor computing system and
associated 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
schedule 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
complexity 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
systems [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 [
2
We consider an analytic computational model of parallel matrices multiplication
developed in papers [
2.1
Block matrix multiplication algorithm user specifies block size . Let the size of block be a natural number such that = 22 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:
( , ) →
minimum could be resource demanding problem.
choose vector ( ) ∈ with components ( ), where ( ) ≥ 0, ( ) ≤ , = 1, … , , ∑
=1 ( ) = . Denote ( ) as the set of all vectors ( ). Every component ( ) is the amount of computation designed for execution on i-th processor.
it allows us to understand basic properties of the computation process.
( , ( )) = max { 2}. =1,..,
model with one user is equal = 3(∑ =1 )−1 and ( ( )) = ( 1, … , ).
Define Minkowski functional for set and vector ∈ as: ( ) = { > 0: ∈ }.
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,.., { > 0: max { } = 2}. This is equivalent to equality = =1,.., Note. There is exists minimum max { 2}.
=1,.., = min ( )( ) and this minimum is ∈ ( ) unique. 2.2
General Fluid Model ( , ( )) = max =1,…,
{ 2 + ( 2+2 ) }.
To take into account transfer time we note, that block algorithm sends 2 ements on each node and receives 2 elements. So, summary time is equal to elProposition 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
( ) = { ∈ : ∈ {0,1, … , }, ∑ = , = 1, . . , }. It is clear that ( ) ⊂ ( ).
responsible for specifying concrete point ∗ ∈ ( ). In this work, we will consider only simple scheduler of extreme – extreme type and perform simulations and investigation 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;
case of equal tasks the choice is random);
ty or waits in the case of no free resources.
task)
Proposition 4. For arbitrary following inequalities are true: ( ) = min ( , ( )) ≥
min ( , ( )) ∈ ( )
∈ ( ) ( ) ≥ ( )
( ) ⊂ ( ). The second inequality holds since ( ) is minimum by definition. 3
We will deal with non-cooperative games in strategic or normal form. A noncooperativeness 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 players. The strict definition is as follows. { , { } ∈ , { } ∈ } , where: •
is a finite set of players; A non-cooperative game in strategic (or normal) form is a triplet = • is the set of admissible strategies for player i. • : → is the utility (payoff) function for player i.
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, purestrategy 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.
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 , ∈ .
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.
in this case is equal to double individual time for this size. 4. There is unique minimum ( ), = 1, … , . Denote argminimum index as ∗.
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).
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).
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 equilibrium.
1( ∗, ∗) ≤ 1( ∗−1, ∗), 2( ∗, ∗) ≤ 2( ∗−1, ∗). This is common situation in games of considered type. 4
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 dimension were used. The experiment was performed on the node with two processors Quad
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.
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 solution. 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.