Load Balancer

Theoretical description

This page contains theoretical decription of local load balancing methods used in this simulator. These methods can be divided into three basic approaches:

The diffusion method
The Nearest Neighbour Averaging
Liquid Model

These approaches have one property in common, the strict locality of the communication and the control. Assumptions:

tasks are indivisible and identical,
task numbers are integers.

Due to the assumption that tasks (i.e. load) are indivisible and task numbers are integers, it is recommended to simulate load balancing process for many tasks.

The diffusion method

The diffusion method is an iterative algorithm. In every step, a fixed fraction of the load difference between two neighboring processors is exchanged. When such local operations are used, the load distribution should converge to the globally equal, flat load distribution. The efficiency of the diffusion method depends on a diffusion parameter which determines the size of the transferred load fraction. Notation:

\(\alpha\) - diffusion parameter,
\(N\) - number of processors,
\(i\) - processor number, \(i=1..N\),
R - vector of current load processors, \(R = [L_1,L_2,...,L_N]\)
\(L_i\) - current load of processor i
\(\Delta(i)\) - a set of directly neighbouring processors,
\(\delta_i(j)\) - a load transferred from processor i to j.

In every step, a load \(\delta_i(j)\) is transferred from processor i to every neighbour \(j\in\Delta(i)\) with:

\(1) \delta_i(j) = \alpha(L_i - L_j)\)

For \(\delta_i(j) \lt 0\) , the load is transferred in the inverse direction i.e. from processor j to i.
Every change of state of the processor load \(L_i\) by synchronous load balancing can be described by the following transition equation:

\(2) L_i(t+1) = L_i(t) - \sum_{j\in\Delta(i)}\delta_i(j)\), where t - the current step in time, t +1 - the next time moment

It is possible, that for big value of alfa parameter and big number of directly neighbouring processors, after one step of load balancing, one of processors will have negative load, according to mentioned formula. In this situation we propose two modifications of diffusion approach:

Diffusion Sync

In the Diffusion algorithm, additional parameter \(\beta\) (parameter \(\alpha\) modificator) is usued, where \(\beta = \alpha/max|\Delta(i)|\).
In this connection, equation 1 changes to equation 3:

\(3) \delta_i(j) = \beta\alpha(L_i - L_j)\)

Diffusion Async

The second modification of the diffusion algorithm consists in asynchronous load exchanges. Each load exchange between the two neighbouring processors is performed independently of the other exchanges, and immediately modifies the loads of the two communicating processors.

The Nearest Neighbour Averaging

The nearest-neighbor-averaging (NNA) is a completely local load balancing method. The idea is to change the load of each processor such that it is equal to the mean load of the processor and its neighbors. Notation:

\(N\) - number of processors,
\(i\) - processor number, \(i=1..N\),
\(R\) - vector of current load processors, \(R = [L_1,L_2,...,L_N]\),
\(L_i\) - current load of processor i,
\(\Delta(i)\) - a set of directly neighbouring processors,
\(\delta(i)\) - a load transferred from processor i to j.

After one load balanvcing step, at time t+1, the processor i should have a load of \(L_i(t+1)\):

\(4) L_i(t+1) = {1 \over |\Delta(i)|+1} (L_i(t) + \sum_{j\in\Delta(i)}L_j(t))\)

The NNA can be realized in two different ways:

The Nearest Neighbour Averaging (asyn)

The Nearest Neighbour Averaging (asyn) is an asynchronous variant of NNA. In this variant, when a processor is highly loaded then it transfers a portion of its load to all deficient neighbours. The amount of transfered load is proportional to the difference of the mean load and the load of the neighbour.
Let the deficiency of each neighbouring processor \(j\in\Delta(i)\) for the processor i be given by \(h_j=max(0,L_j(t+1)-L_j(t))\) and the total deficiency by \(H_i = \sum_{j\in\Delta(i)}h_j\). Then, the asynchronous NNA performs a load transfer \(\delta_i(j)\) from processor i to each of its neighbours \(j\in\Delta(i)\) with:

\(5) \delta_i(j) = (L_i(t) - L_i(t+1)) {h_j \over H_j}\)

The Nearest Neighbour Averaging (syn)

In the synchronous variant of NNA, the load of every processor is divided into \(|\Delta(i)| + 1\) portions of the same size. The processor itself and all of its neighbors receive one load portion. The execution of each load balancing step satisfies the transition equation in 4. Let the processor i have a load \(L_i\) and a set of neighbors \(\Delta(i)\). Then, by the synchronous NNA, a load transfer \(\delta_i\) from processor i to each of its neighbors \(j \in \Delta(i)\) is performed with:

\(6) \delta_i = {L_i \over |\Delta(i)| + 1}\)

Liquid Model

Liquid model can be compared to box filled with a homogeneous liquid. In the balanced state, the liquid has the same height at any place in the box. If one pours additional liquid into the box at an arbitrary location, the liquid equalizes itself such that the height is again the same everywhere. We assume a general cyclic mesh structure (torus) as the communication network of the processing units.
Notation:

\(D\) - dimensions
Cordinates given as D-dimensional vector \(i = (i_1,...,i_D)\)
\(L_i\) - current load of processor i,
\(P_{i_{D}}\) - Processor i in dimension D.

The change of load states is accomplished by shifting elementary load units between neighboring processors. The Boolean function \(C_{i,d}(t)\) controls the shift of load elements. If for one processing unit i the condition \(C_{i,d}(t)\) holds true, then it shifts one load element to its neighbour in dimension d. The function \(C_{i,d}(t)\) represents one of the six conditions C0 to C5:

\(C0)L_i\gt0\), so \(P_i\) has load elements to be transferred

\(C1)L_i\gt1\), so \(P_i\) is not idle after giving away one load element

\(C2)C1 \lor [L_1 = 1 \land (L_{i-1_{d} } \gt 1)]\), so \(P_i\) is not idle after giving away one load element or receives one load element from \(P_{i-1_{d}}\)

\(C3) C1 \lor L_i \ge L_{i+1_{d}}\), so \(P_i\) is not idle after giving away one load element and \(P_{i+1_{d}}\) has not more load

\(C4) C2 \lor L_i \ge L_{i+1_{d}}\), so \(P_i\) is not idle after giving away one load element or receives one load element from \(P_{i-1_{d}}\) and \(P_{i+1_{d}}\) has not more load

\(C5) C0 \lor L_i \ge L_{i+1_{d}}\), so \(P_i\) has load elements to be transferred and \(P_{i+1_{d}}\) has not more load

A change of state \(L_i(t) \Rightarrow L_i(t+1) \), with \(i \in I\), is called Liquid model load balancing, if and only if in every dimension \(d =1,...,D\) the following equation is applied successively:

\( L_i(t) := \begin{cases} L_i(t) + 1, if\: C_{i-1_{d},d}(t) \land \lnot C_{i,d}(t) \\[.5em] L_i(t) - 1, if\: \lnot C_{i-1_{d},d}(t) \land C_{i,d}(t) \\[.5em] L_i(t), otherwise \end{cases} \)

Help

In the top right corner there is a menu allowing to control simulation:

Start/Stop - start/stop simulation while clicking on toggle button
Speed - controls simulation's speed
Toggle labels - on/off labels identifying node
Topology - defines topology used during simulation
Dimentions - set size of dimensions for given topology
Reset Load - set load of each node to 0
Algorithms - select load balancing algorithm used during simulation
Algorithm specs - if any, controls variables of given algorithm

On the left side there is taskbar allowing to open modals with additional functionalities. Modals can be closed by pressing ESC or by mouse click. (Warning: Simulation is stopped while opening any modal)

Current Load - shows current load of all nodes
Load History - shows load history of all nodes during last 30 load updates
Edit Load - allows setting certain load for all the nodes or to modify the range of changes (during each step load is changed by value from +/- range with uniform distribution)
Theory - description of algorithms
Help

When it comes to navitation we can:

Rotate with left mouse button
Zoom with mouse wheel
Translate with right mouse button or with left mouse button + Ctrl

In the right bottom corner, we can see 'Load Legend', that presents a legend for color representation of load, where the lowest value (blue) is the smallest load currently present in the system and the highest value (red) is the highest load currently present in the system.