Load Imbalance

Assuming that the total amount of computation in a parallel code fragment (or, for the purposes of this paper, a parallel loop nest) is $W_{tot}$ which is distributed amongst $p$ processors in such a way that each processor $i$, $0 \leq i < p$, is assigned an amount of computation equal to $W_i$ (clearly, $\sum_{i=0}^{p-1} W_i = W_{tot}$), then we say that this distribution exhibits a load imbalance, $L$, equal to

$$L = \max_{i}(W_i - \frac{W_{tot}}{p}) = W_{max} - \frac{W_{tot}}{p},$$ (1)

where $W_{max} = \max(W_0, W_1, \dots, W_{p-1})$. When, $L=0$, that is, for all $i$, $W_i = W_{tot}/p$, we say that there exists a perfect load balance.

To assess the impact of load imbalance on performance, we introduce relative load imbalance, $L_R$, defined as

$$L_R = \frac{L}{W_{max}} = \frac{W_{max}-W_{tot}/p}{W_{max}} = 1 - \frac{W_{tot}}{p W_{max}}.$$ (2)

It can be easily shown that $L_R$ takes values in the interval $[0,1-1/p]$; values close to zero denote a small impact of load imbalance on performance.