PRAM-algorithm

This algorithm represents a widely spread method to handle inputs where ${\displaystyle p}$ is a power of two. The reverse procedure is often used for broadcasting elements.^[5][6][7]

Visualization of the algorithm with p = 8, m = 1, and addition as the reduction operator

for ${\displaystyle k\gets 0}$ to ${\displaystyle \lceil \log _{2}p\rceil -1}$ do

for ${\displaystyle i\gets 0}$ to ${\displaystyle p-1}$ do in parallel

if ${\displaystyle p_{i}}$ is active then

if bit ${\displaystyle k}$ of ${\displaystyle i}$ is set then

set ${\displaystyle p_{i}}$ to inactive

else if ${\displaystyle i+2^{k}<p}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

The binary operator for vectors is defined element-wise such that ${\displaystyle {\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}}$. The algorithm further assumes that in the beginning ${\displaystyle x_{i}=v_{i}}$ for all ${\displaystyle i}$ and ${\displaystyle p}$ is a power of two and uses the processing units ${\displaystyle p_{0},p_{1},\dots p_{n-1}}$. In every iteration, half of the processing units become inactive and do not contribute to further computations. The figure shows a visualization of the algorithm using addition as the operator. Vertical lines represent the processing units where the computation of the elements on that line take place. The eight input elements are located on the bottom and every animation step corresponds to one parallel step in the execution of the algorithm. An active processor ${\displaystyle p_{i}}$ evaluates the given operator on the element ${\displaystyle x_{i}}$ it is currently holding and ${\displaystyle x_{j}}$ where ${\displaystyle j}$ is the minimal index fulfilling ${\displaystyle j>i}$, so that ${\displaystyle p_{j}}$ is becoming an inactive processor in the current step. ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ are not necessarily elements of the input set ${\displaystyle X}$ as the fields are overwritten and reused for previously evaluated expressions. To coordinate the roles of the processing units in each step without causing additional communication between them, the fact that the processing units are indexed with numbers from ${\displaystyle 0}$ to ${\displaystyle p-1}$ is used. Each processor looks at its ${\displaystyle k}$-th least significant bit and decides whether to get inactive or compute the operator on its own element and the element with the index where the ${\displaystyle k}$-th bit is not set. The underlying communication pattern of the algorithm is a binomial tree, hence the name of the algorithm.

Only ${\displaystyle p_{0}}$ holds the result in the end, therefore it is the root processor. For an Allreduce-operation the result has to be distributed, which can be done by appending a broadcast from ${\displaystyle p_{0}}$. Furthermore, the number ${\displaystyle p}$ of processors is restricted to be a power of two. This can be lifted by padding the number of processors to the next power of two. There are also algorithms that are more tailored for this use-case.^[8]

Distributed memory algorithm

In contrast to the PRAM-algorithm, in the distributed memory model, memory is not shared between processing units and data has to be exchanged explicitly between processing units. Therefore, data has to be exchanged explicitly between units, as can be seen in the following algorithm.

for ${\displaystyle k\gets 0}$ to ${\displaystyle \lceil \log _{2}p\rceil -1}$ do

for ${\displaystyle i\gets 0}$ to ${\displaystyle p-1}$ do in parallel

if ${\displaystyle p_{i}}$ is active then

if bit ${\displaystyle k}$ of ${\displaystyle i}$ is set then

send ${\displaystyle x_{i}}$ to ${\displaystyle p_{i-2^{k}}}$

set ${\displaystyle p_{k}}$ to inactive

else if ${\displaystyle i+2^{k}<p}$

receive ${\displaystyle x_{i+2^{k}}}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

The only difference between the distributed algorithm and the PRAM version is the inclusion of explicit communication primitives, the operating principle stays the same.

Runtime analysis

The number of steps in the parallel execution are ${\displaystyle p+m-2}$, it takes ${\displaystyle p-1}$ steps until the last processing unit receives its first element and additional ${\displaystyle m-1}$ until all elements are received. Therefore, the runtime in the BSP-model is ${\displaystyle T(n,p,m)=\left(T_{\text{start}}+{\frac {n}{m}}\cdot T_{\text{byte}}\right)(p+m-2)}$, assuming that ${\displaystyle n}$ is the total byte-size of a vector.

Although ${\displaystyle m}$ has a fixed value, it is possible to logically group elements of a vector together and reduce ${\displaystyle m}$. For example, a problem instance with vectors of size four can be handled by splitting the vectors into the first two and last two elements, which are always transmitted and computed together. In this case, double the volume is sent each step, but the number of steps has roughly halved. It means that the parameter ${\displaystyle m}$ is halved, while the total byte-size ${\displaystyle n}$ stays the same. The runtime ${\displaystyle T(p)}$ for this approach depends on the value of ${\displaystyle m}$, which can be optimized if ${\displaystyle T_{\text{start}}}$ and ${\displaystyle T_{\text{byte}}}$ are known. It is optimal for ${\displaystyle m={\sqrt {\frac {n\cdot (p-2)\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$, assuming that this results in a smaller ${\displaystyle m}$ that divides the original one.