A visualization for an all-to-all communication with four processors and m=1.

In parallel computing, all-to-all (also known as index operation or total exchange) is a collective operation, where each processor sends an individual message to every other processor.

Initially, each processor holds p messages of size m each, and the goal is to exchange the i-th message of processor j with the j-th message of processor i.

The number of communication rounds and the overall communication volume are measures to evaluate the quality of an all-to-all algorithm. We consider a single-ported full-duplex machine throughout this article. On such a machine, an all-to-all algorithm requires at least ${\displaystyle \lceil \log _{2}n\rceil }$ communication rounds. Further a minimum of ${\displaystyle \left\lceil m(n-1)\right\rceil }$ units of data is transferred. Optimum for both these measures can not be achieved simultaneously.^[1]

Depending on the network topology (fully connected, hypercube, ring), different all-to-all algorithms are required.

All-to-all algorithms based on topology

Visualization of an all-to-all algorithm in a ring topology.

Visualization of an all-to-all algorithm in a mesh topology.

We consider a single-ported machine. The way the data is routed through the network depends on its underlying topology. We take a look at all-to-all algorithms for common network topologies.

1-factor algorithm

A visualization of the 1-factor algorithm.

Again, we consider a single-ported machine. A trivial algorithm, is to send (p-1) asynchronous messages into the network for each processor. The performance of this algorithm is poor, which is due to congestion arising because of the bisection width of the network.^[3] More sophisticated algorithms combine messages to reduce the number of send operations and try to control congestion.

For large messages, the cost of a startup is small compared to the cost of transmitting the payload. It is faster to send messages directly to their destination. In the following algorithm an all-to-all algorithm is performed using (p-1) one-to-one routings.

// p odd:
// pe index ${\displaystyle j\in \{0,\dots ,p-1\}}$
for i := 0 to p-1 do
    Exchange data with PE ${\displaystyle (i-j)\,\mod \,p}$

// p even:
// pe index ${\displaystyle j\in \{0,\dots ,p-1\}}$
for i := 0 to p-2 do
    idle := ${\displaystyle {\frac {p}{2}}i\,\mod \,(p-1)}$
    if j = p-1 then
        exchange data with PE idle
    else
        if j = idle then
            exchange data with pe p-1
        else
            exchange data with PE ${\displaystyle (i-j)mod(p-1)}$

The algorithm has a different behavior, whether p is odd or even. In case p is odd, one processor is idle in each iteration. For an even p, this idle processor communicates with the processor with index p-1. The total time taken is ${\displaystyle (p-1)(t_{s}+t_{w}m)}$ for an even p, and ${\displaystyle p(t_{s}+t_{w}m)}$ for an odd p respectively.

Instead of pairing processor j with processor ${\displaystyle (i-j){\bmod {p}}}$ in iteration i, we can also use the exclusive-or of j and i to determine a mapping. This approach requires p to be a power of two. Depending on the underlying topology of the network, one approach might be superior to the other. The exclusive or approach is superior, when performing pairwise one-to-one routings in a hypercube or fat-tree.^[4]

References