recursivedoubling

Recursive doubling, often written as recursivedoubling in some sources, is a communication pattern used in parallel computing and distributed systems to disseminate information and perform reductions across a set of processes or nodes. The technique organizes communication in log2(p) rounds, where p is the number of participating processes. In each round, every process exchanges data with a partner chosen so that the total set of known data doubles. After r rounds, a process has information from up to 2^r processes; after log2(p) rounds, each process can have information from all processes (assuming p is a power of two). The partner in round i is typically found by toggling the i-th bit in the process rank, e.g., exchanging with rank XOR 2^i.

Applications of recursive doubling include broadcast, allreduce, and allgather. In broadcast, a root process disseminates a value to all others by repeatedly doubling the number of informed processes. In allreduce, partial reductions are exchanged and combined at each step to produce a final result at all processes. In allgather, each process ends up with the complete set of data from all participants.

Complexity and performance characteristics depend on the underlying network. The number of rounds is O(log p), and the total data moved scales as O(n log p) for data of size n. The pattern presumes reliable point-to-point communication and is particularly effective on networks with fast, symmetric links or hypercube-like topologies. Variants exist to handle non-power-of-two process counts and to adapt to different topologies or latency profiles; in practice, recursive doubling is a common building block in MPI and other parallel libraries.