qulrb

Load rebalancing problem and quantum approximate optimization approach

Load Rebalancing Problem

• Formulation by Aggarwal et al. [SPAA-03]

  • Given $n$ jobs with the following sizes ${s_{1}, s_{2}, ..., s_{n}}$
  • Assigned on $m$ processors ${P_{1}, P_{2}, ..., P_{m}}$
  • Problem: relocating jobs among the processors to minimize the makespan, where
    • $makespan$: the completion time
    • relocating cost: $c_{ij}$ when moving a job from processor $i$ to processor $j$

  [SPAA-03] Gagan Aggarwal, Rajeev Motwani, and An Zhu. 2003. The load rebalancing problem. In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures (SPAA '03). Association for Computing Machinery, New York, NY, USA, 258–265, https://doi.org/10.1145/777412.777460.

Figure 1. Problem formulation.

• Re-formulating and mapping the load rebalancing problem in a context of task-based parallel applications in HPC
  • A given distribution of $n$ tasks on $m$ compute nodes/machines.
  • If the execution happens expectedly, total load per node is similar like the left figure shows.
  • If the execution happens unexpectedly (e.g., wrong performance model for unexpected task distribution before the execution), load per tasks per process might be different. The total load among nodes is unbalanced like the right figure shows.

Objective

• Migrate tasks to balance the load
• How many tasks should be migrated? From which process/node to which process/node?

Approaches

Figure 2. Task stealing and task offloading approach.

• Dynamic:
  • Task stealing (work stealing) without prior knowledge about load values/the length of tasks. During execution, when the queue of a process is empty, it starts asking to steal the tasks from the other processes, as shown in Figure 2 (A).
  • Reactive task offloading without prior knowledge about load values/the length of tasks. During execution, each process dedicates a thread for checking queue status continuously and offloading tasks reactively if it detects load imbalance based on the queue status at a time, as shown in Figure 2 (B).

Figure 3. A hybrid approach with prior knowledge based on load predicted values at runtime.

• Hybrid: works in the case, the load imbalance or the performance model of tasks can be predicted before a new execution phase starts.
  • First, assume we have predicted load values before a new execution starts. For example, as Figure 3 shows, $P_{0}$ has 5 tasks, each takes $15ms$; $P_{1}$ has 5 tasks, each takes $38ms$ and so on.
  • Second, apply a solver/algorithm to find the solution: how many tasks should be migrated? from which process to which process?
  • Third, the delay of task migration might be taken into account, even task migration can start early.

Motivation

• Load rebalancing problem can be considered as an optimization problem [SPAA-03].

• Compared to the classical algorithms, how this problem can be formulated and solved in quantum computing?