Diffusion algorithm

One of the most popular approaches to the flow calculation problem is to use diffusion based algorithms [6,14]. In a heat diffusion process, the initial uneven temperature distribution in space causes the movement of heat, and the system eventually reaches a steady-state temperature.

The diffusion algorithm, as described in [6], is given as follows. At each iteration $k+1$ of the algorithm, processor $i$ will send an amount proportional to the difference between its load and its neighbor's load, $c_{ij}(l^{(k)}_i-l^{(k)}_j)$, to its neighbor $j$. Assume $c_{ij} = c_{ji}$, the new load $l_i^{(k+1)}$ of the processor $i$ is given by the combination of its own load $l^{(k)}_i$ and contributions from/to its neighboring vertices, namely

$$l_i^{(k+1)}\ = \ l_i^{(k)}\ -\ \sum_{i \leftrightarrow j} c_{ij} (l^{(k)}_i-l^{(k)}_j),\quad i,\ j\in V,\ k=1,2,\ldots$$ (10)

Initially the load for vertex $i\in V$ is $l_i^{(1)}=l_i$. In matrix form, the above equation can be rewritten as

$$l^{(k+1)}\ =\ (I\ -\ A\ W\ A^T)\ l^{(k)},$$ (11)

where $W$ is a diagonal matrix of the size $\vert E\vert\times\vert E\vert$, that consists of the coefficients $c_{ij}$, and $A$ is a matrix of size $\vert E\vert\times \vert V\vert$, to be defined in Section 4.3.4. For the choice of the coefficients, Boillat [6] suggested

$$c_{ij}={1\over \max\left\{deg(i),deg(j)\right\}+1},\quad i\leftrightarrow j,\quad i,\ j\in V.$$

The diffusion algorithm, being a stationary iterative method of the form (11), can converge quite slowly on graphs with small connectivity. Boillat [6] proved that the worst case happens when the graph is, say, a line, and in such a case the number of iterations needed to reach a given tolerance is $O(p^2),$ with $p$ the number of vertices. There are other variations of the diffusion algorithm (see [33,28]). For example instead of (11), a special case of the following equation,

$$(I\ +\ A\ W\ A^T)\ l^{(k+1)}\ =\ l^{(k)},$$

is solved in [33]. The convergence of the diffusion algorithm can also be improved using the Chebyshev polynomial [44,17,64].

Many investigations of dynamic load balancing algorithms have used a diffusive approach, although the details vary. For example, in both the tiling algorithm and the iterative tree balancing algorithm [13,25,26], a processor selects amongst its neighbors the one with the highest load and posts a request. In the tiling algorithm the amount of load to be sent is decided by looking at the average of the loads in the neighborhood. In the iterative tree balancing algorithm the requests are viewed as a forest of trees. The flow along the branches of the tree is then calculated using a logarithmic time parallel scan operation.