Policy as it pertains to high-performance systems

I was recently asked to think about how high performance systems deal with policies?

Two clarifications are required here:

  1. What are high-performance systems in the context of Grid, HPC and scheduling?
  2. What are the policies that a typical high-performance system deals with or in other words, sets?

In the context of high-performance schedulers, a high-performance system is the scenario where we are dealing with a large number of tasks (potentially millions of tasks) that are fairy short in duration, and the total job is only complete once all the tasks have been completed.

What is “short” in our context?  I can easily say that short is in the order of milliseconds or even seconds, but more quantitatively, I will assume that a task is short in duration iff:

  1. Scheduling overhead directly impacts the speedup factor (i.e. the time that it takes to schedule that task cannot be neglected)
  2. The runtime of a give task is significantly shorter (two-orders of magnitude) than the overall runtime of given job.

The bigger question becomes what these policies actually are and why would they be of importance?

The following is a subset of policies that we could be referring to:

  1. Sharing policy
  2. Fair-share policy pertaining to scheduling
  3. (others – TBD)

In a sharing policy, a client can allow some or all if its resources to be shared (given out) to other client[s] that may need them.  This obviously has a risk that the resources are not immediately available when the original owner needs them back.  At the same time, if one waits before lending out resources, there could a high degree of unutilized resources.

 

The fair-share policy is scheduling is probably the most implicitly set policy in shared environments.  The users get their “fair-share” of the available resources based on some preset fair-share policy.  A user may assist or hint the policy with priorities, for example, but generally speaking, the policy is set and agreed to by all the users.

My research focuses on Fair-share policy and how it affects users – and to an extend resources.  Users agree to the fair-share policy with the assumption that what the scheduler does is “fair”.

Furthermore, users interact with the system unbeknownst to how the fair-share scheduling policy is affecting their runtime.  The side effect of a fair-share scheduler is that timing is severely affects the outcome.  Since there is no historical perspective kept to aid the scheduler to better aid the enforcement of such policy, and some users end up keep temporarily starved.

 

Art Sedighi

Hot-Potato pricing and utility algorithm

This is a place holder for my paper

Approach

Game theory can be used to explain behaviour in shared environments such as Grid or Cloud.

One could argue that a Cloud environment is much like non-cooperative game setting where one player is unaware of the other players.  An internal Grid, on the other hand, *may* still be non-cooperative but the other players are known.

Nash Equilibrium requires coordination between and amongst the parties in order to achieve an optimal solution.  The ratio of the solution achieved in NE vs. what really happens in the real-world is the Price of Anarchy.  The goal is reduce PoA for a shared environment.

 

Game Theory Building Blocks

Just a recap today…

A game is composed of players or the interacting parties, rules or “who can do what”, and results or outcomes.  Game theory is build atop of other theories, with each representing the three components of a game:

- decision theory

- representation theory

- solution theory

 

Decision Theory – is an extension of the von Neumann-Morgenstern decision theory that relate to making a decision under uncertainty.  Decision theory relates to game theory in that it provides a way to represent preferences.  Games are all about preferences and as such utility of the chosen preference.

Representation Theory – allows a formal way of representing rules of a give game.  Two representation theories pertain to our discussion: normal form and extensive form.

Normal form: complete plan that considers all contingencies are presented at the start of the game.  It has a static view of the game in how it is played.

Extensive form: it is like a decision tree or a flow chart in that each level of the tree is build only when the node has been reached.  Players have choices and those choices are made in real-time

Solution Theory – it deals with how to assign solutions to games.  It works based on the premise that each player is looking out for itself.  One of the main solution concepts that we will talk about is Nash’s Equilibrium which basically states that no one player can change its strategy and improve its utility.

Game theory puts these three theories together to try and explain a social interaction.  A solution prescribes how rational players should behave and not how they would actually behave in the real-world. 

 

Congestion Games

The concept of Congestion Games is a very interesting one as it pertains to Scheduling.  Rosenthal (1973) coined the term and defined a congestion game to be a scenario where the payoff of a given player depends on the resource it ends up on, and the how busy that resource may be based on how many other players are also on that resource.  Rosenthal, however, focused on having identical machines, and same-size jobs.

A scheduler may schedule a number of tasks on a given machine, if the number of pending tasks is greater than the total number of resources.  As the number of tasks scheduled on a given machine increases – they are all competing for the same resource (CPU, memory, etc) and therefore the utility perceived by a given client could change based on how “congested” a node gets.

The fact of the matter is that most schedulers schedule one task per CPU, so avoid congestion.  I do agree that there could be other processes running on that machine as part of the Operating System (for example, time sync daemon runs on a box every few minutes), but these processes in a dedicated node scenario consume very minimal resources and can be ignored.

In unrelated machines where the infrastructure is heterogeneous, Nir Andelman argues in Strong Price of Anarchy (2006),  that congestion does not take place since the load of a given task is different on different machines.  I strongly disagree with this sentiment.  Based on one of my previous postings called Utility of Master-worker Systems, we must start thinking about the utility of the node itself.  A node (CPU) desires a high utility as well, and that utility is to be idle.  Based on this, unrelated machines cannot be treated any different than related machines.   A system of nodes breaks down to its components of individual nodes with each node desiring a level of utility that matches the utility of all the other nodes.

In short, there is an intrinsic commonality between related and unrelated machines.  This commonaility is the fact that each CPU can achieve the same level of utility by doing the same thing (taking on the same strategy in GT lingo), and that is to finish the task that it was given as soon as possible.

Furthermore, we need to look at scheduling a job on a CPU as being two seperate and sometimes conflciting games:

- Macro-level: a game played by the job submitters trying to minimize their runtime (makespan)

-Micro-level: a game played by the job and the CPU where the CPU wishes to be idle and the job wishes to be compeleted.

 

Reference:

Strong Price of Anarchy N. Andelman, M. Feldman, Y. Mansour, 2006

 

The Matching Pennies Problem

So what is the Matching Pennies Problem anyway (MPP)?

Matching Pennies is a simple game but has very interesting properties that can be applied to many other types of complex games.

There are two players, and each select either Head or Tail.  Here are the rules of the game:

- if the choices differ (one player chooses Head while the other Tail), Player 1 pays Player 2 $1

- if the choices are the same (both players select Head or both select Tail), Player 2 pays Player 1 $1

 

Head Tail
Head 1,-1 -1,1
Tail -1,1 1,-1

This is a Zero-sum game in that one player’s win would mean a loss for the second player.  In another words, the choices are diametrically opposed to one another.  This game is a strictly competitive game and no amount of collaboration will help the situation.

Recap: To be in Nash’s Equilibrium, no player has an action yielding an outcome that he prefers to that of the current action, given that every other player chooses his equilibrium action.  In other words, no player can profitably deviate, given the actions of the other players.  In the MPP, if Player 2 and Player 1 have chosen Head, Player 2 end up paying Player 1.  If now Player 2 chooses to change his choice to Tail, so can Player 1 and the results are the still the same.  You can see what happens from Player 1′s perspective if the users’ selections were not the same to start.

But there is not a single solution that “stands” out in that there is no solution (or strategy) that has a better outcome for one player over the current action.

 

Art Sedighi

 

The Grid Problem

Determining if a problem/game has a Nash Equilibrium is not an easy problem.  In fact, it is harder than the classical NP problems and it is considered to be PPAD.  In this posting, I will look and classify the Grid Problem to be the following:

Grid is a shared infrastructure with a limited number of resources.  The limit could be high, but it must be less than what two players (users of the Grid) are able to consume.  We want to look at the Grid Problem and see if there exists a configuration where all the users/players are satisfied.  In short, we want to see if there exists a Nash’s Equilibrium point for the Grid Problem. 

Lets take a step back, and look at the classes of games that exist.  I want to do this to level-set and clarify my position about where various infrastructure types will fit into the different classes of games.

We have the following:

  1. Strategic Games (a.k.a Games in Normal Form)
  2. Extensive Games with perfect information
  3. Extensive Games without perfect information
  4. Coalitional Games

Strategic games are rather interesting in that both players (or N-players) make the decision in advance, and stick to that decision for the duration of the games.  Extensive games, however, players can modify their strategy between moves.

Lets look at a Grid infrastructure:

A. Resource are limited
B. Jobs are submitted to the Queue to be processed
C. Queues are most likely FIFO
D. A Player wants to get results asap without regards to the other players

Based on the above properties, we can deduce the following:

  • Property A makes this game a Zero-sum game.
  • Property B makes this game an imperfect information game
  • Properties C + D makes this game a non cooperative strictly competitive game

In a Strategic game, the player chooses his plan of action once and for all and independently of the other players.  Each plan is made based on a set of preferences, but those preferences *must* be selfish as we are dealing with a Zero-sum game.

If this problem can be reduced to the Matching Pennies problem, we can deduce that the Grid Problem does not have a Nash Equilibrium.

 

Art Sedighi

 

Protected: Draft – Paper

This content is password protected. To view it please enter your password below:

Not Fair

We can assume, as mentioned before, that the users of a Grid are playing a zero-sum game against each other.  In that one’s gain is another one’s loss.  Or more explicitly, if one user gets more CPU’s, the other[s] get less as a result.

This is fairly easy to prove as we have a set of CPU’s that does not change.  In a zero-sum game, there always exists a Nash’s Equilibrium.  Finding Nash’s Equilibrium is not easy; in-fact it falls under a calls of problems call PPAD, but we know that one does exist.

Two comments can therefore be made:

1. If we assume that Nash’s Equilibrium is in-fact the standard fairness point, then if the scheduler deviates from NE, it is not a fairshare scheduler.  Proving that fairshare is in-fact, not fair.

2. If a user by changing its strategy is able to increase its utility (i.e. get a higher portion of the available resources), then the system is not in Nash’s Equilibrium and the scheduler is not dividing up resources in a fair manner.

and 2.1. The user is inclined to change its strategy so it can get a larger portion of the system.  This is where we see “Price of Anarchy” developing.

Assumption:

One assumption we have made throughout is that Nash’s Equilibrium point presents the only fair point at which point all participants are treated fairly.

 

Art Sedighi

 

 

Zero-sum game

It is conceivable to think of a Grid Scheduler as the mediator to a zero-sum game.  The number of resources do not change — not taking into account the hype that is cloud these days with elastic computing.  If the number of resources available to a scheduler and in turn the clients/players of the system is constant, the number of CPU’s that one client gets assigned directly affects the number of CPU’s that has been “taken” away from the pool of resources available to the second client.

As the total number of resources does not change, and one players action based on fairshare scheduling affects the number of resources that it gets assigned, one can conclude:

Based on client’s task submission strategy, a client realizes a utility that is directly a result of the number of resources it received – or got assigned to by the scheduler.