Game Theoretic Analysis of Multi-Processor Schedulers: Matrix Multiplication Example

Oleksii IgnatenkoICTERI 2017

TL;DR

This paper applies game theory to model resource allocation in heterogeneous multiprocessor systems, specifically for matrix multiplication. By treating users as rational agents competing for resources, they analyze how individual optimization can lead to system-wide inefficiencies and identify conditions for stable outcomes (Nash equilibria) that are often suboptimal.

What Problem Does This Paper Address?

Modern scientific computing relies heavily on multiprocessor systems, but efficiently allocating resources among competing users is a significant challenge. These systems are often heterogeneous, meaning processors have different capabilities, and users have diverse computational needs. This can lead to unfair resource access and increased processing times, especially when users act selfishly to maximize their own performance. The paper aims to understand and model this user conflict using game theory, specifically focusing on how individual users' choices about how to partition their tasks (in this case, matrices for multiplication) can lead to suboptimal overall system performance.

Methods

The authors employ a game-theoretic approach to model the interactions between users competing for resources on a heterogeneous multiprocessor system. They first develop a fluid model to approximate the "ideal" finish time for matrix multiplication, establishing a theoretical lower bound. Then, they formulate a static, non-cooperative game where users' strategies involve choosing the size of blocks to partition their matrices. The paper focuses on the "min-min" scheduler, a common algorithm that assigns tasks to processors. They analyze the conditions under which a Nash equilibrium (a state where no player can improve their outcome by unilaterally changing their strategy) exists and investigate its Pareto efficiency. Simulation experiments using CloudSim and a real system are used to validate their theoretical models.

Datasets

Not discussed in the paper. The paper uses a simulated heterogeneous multiprocessor system and a real system for experiments, with matrices of 1200x1200 dimensions.

Key Insights and Ideas

  • Selfishness leads to inefficiency: When individual users try to optimize their own matrix multiplication finish times by choosing block sizes, it can lead to a system-wide equilibrium that is worse for everyone than if they had cooperated.
  • Nash Equilibrium is often Pareto-inefficient: The stable states (Nash equilibria) found in this game model are not necessarily the best possible outcomes for the system as a whole. This highlights a fundamental tension between individual rationality and collective efficiency.
  • Scheduler type matters: The characteristics of the scheduler (like the min-min algorithm used here) significantly influence the nature and existence of Nash equilibria.
  • Block size is a strategic choice: Users' decisions on how to partition their matrices (i.e., the block size) are treated as strategic moves in the game, directly impacting their own and potentially others' finish times.

Key Results

The paper presents conditions for the existence of Nash equilibria in the described game for two players. They demonstrate that these Nash equilibria are always Pareto-inefficient. Simulation results, visualized in a "finish time surface" graph, show the relationship between players' chosen block sizes and their resulting finish times, illustrating the game's dynamics and the location of the Nash equilibrium.

Limitations and Future Work

The paper acknowledges that the presented model is a simplification, particularly the fluid model and the focus on a specific scheduler (min-min). Future work could involve extending the analysis to more complex schedulers, considering dynamic environments where user demands change over time, and exploring cooperative game theory approaches to find more globally optimal solutions. The authors also suggest investigating more complex systems with a larger number of users and more intricate task dependencies.

Summary updated

BibTeX
@inproceedings{ignatenko2017game,
  author = {Oleksii Ignatenko},
  title = {{Game Theoretic Analysis of Multi-Processor Schedulers: Matrix Multiplication Example}},
  booktitle = {ICTERI},
  year = {2017},
}
Figure