The two-tree broadcast (abbreviated 2tree-broadcast or 23-broadcast) is an algorithm that implements a broadcast communication pattern on a distributed system using message passing. A broadcast is a commonly used collective operation that sends data from one processor to all other processors. The two-tree broadcast communicates concurrently over two binary trees that span all processors. This achieves full usage of the bandwidth in the full-duplex communication model while having a startup latency logarithmic in the number of partaking processors. The algorithm can also be adapted to perform a reduction or prefix sum.
Algorithm A broadcast sends a message from a specified root processor to all other processors. Binary tree broadcasting uses a binary tree to model the communication between the processors. Each processor corresponds to one node in the tree, and the root processor is the root of the tree. To broadcast a message M, the root sends M to its two children (child nodes). Each processor waits until it receives M and then sends M to its children. Because leaves have no children, they don't have to send any messages. The broadcasting process can be pipelined by splitting the message into k blocks, which are then broadcast consecutively. In such a binary tree, the leaves of the tree only receive data, but never send any data themselves. If the communication is bidirectional (full-duplex), meaning each processor can send a message and receive a message at the same time, the leaves only use one half of the available bandwidth.
The idea of the two-tree broadcast is to use two binary trees T1 and T2 and communicate on both concurrently. The trees are constructed so that the interior nodes of one tree correspond to leaf nodes of the other tree. The data that has to be broadcast is split into blocks of equal size. In each step of the algorithm, each processor receives one block and sends the previous block to one of its children in the tree in which it is an interior node. A schedule is needed so that no processor has to send or receive two messages in the same step. To create such a schedule, the edges of both trees are colored with 0 and 1 such that
no processor is connected to its parent nodes in T1 and T2 using edges of the same color no processor is connected to its children nodes in T1 or T2 using edges of the same color. Edges with color 0 are used in even steps, edges with color 1 are used in odd steps. This schedule allows each processor to send one message and receive one message in each step, fully utilizing the available bandwidth. Assume that processor i wants to broadcast a message. The two trees are constructed for the remaining processors. Processor i sends blocks alternating to the roots of the two trees, so each tree broadcasts one half of the message.
Analysis Let p be the number of processing elements (PE), numbered from 0 to p - 1.
Construction of the trees
Let h = ⌈log(p + 2)⌉. T1 and T2 can be constructed as trees of height h - 1, such that both trees form an in-order numbering of the processors, with the following method: T1: If p = 2h − 2, T1 is a complete binary tree of height h − 1 except that the rightmost leaf is missing. Otherwise, T1 consists of a complete binary tree of height h − 2 covering PEs [0, 2h−1 − 2], a recursively constructed tree covering PEs [2h−1, p − 1], and a root at PE 2h−1 − 1 whose children are the roots of the left and the right subtree. T2: There are two ways to construct T2. With shifting, T2 is first constructed like T1, except that it contains an additional processor. Then T2 is shifted by one position to the left and the leftmost leaf is removed. With mirroring, T2 is the mirror image of T1 (with the mirror axis between processors p/2−1 and p/2). Mirroring only works for even p. It can be proven that a coloring with the desired properties exists for all p. When mirroring is used to construct T2, each processor can independently compute the color of its incident edges in O(log p) time.
Communication Time For this analysis, the following communication model is used: A message of size n has a communication time of α + βn, independent on which processors communicate. α represents the startup overhead to send the message, β represents the transmission time per data element. Suppose the message of size m is split into 2k blocks. Each communication step takes time α + βm/2k. Let h=log p be the height of the communication structure with the root at processor i and the two trees below it. After 2h steps, the first data block has reached every node in both trees. Afterwards, each processor receives one block in every step until it received all blocks. The total number of steps is 2h + 2k resulting in a total communication time of (2h + 2k)(α + βm/2k). Using an optimal k = k* = (βmh/2α)1⁄2, the total communication time is βm + 2αlog p + √8αβmlog p.
Comparison to similar algorithms In a linear pipeline broadcast, the message is split into k blocks. In each step, each processor i receives one block from the processor i-1 (mod p) and sends one block to the processor i+1 (mod p). Linear pipeline has optimal throughput, but has a startup time in O(p). For large p, the O(log p) startup latency of the two-tree broadcast is faster. Because both algorithms have optimal throughput, the two-tree algorithm is faster for a large numbers of processors. A binomial tree broadcast communicates along a binomial tree. Each process receives the message that is broadcast (the root already has the message) and then sends the message to its children. A binomial tree broadcast has only half the startup time of the two-tree broadcast, but a factor of log(p) more communication. The binomial tree broadcast is faster than the two-tree broadcast for small messages, but slower for large messages.
A pipelined binary tree broadcast splits the message into k blocks and broadcasts the blocks consecutively over a binary tree. By using a Fibonacci tree instead of a simple balanced binary tree, the startup latency can be reduced to αlog(p).
A Fibonacci tree of height h consists of a root that has a Fibonacci tree of height h-1 as its left child and a Fibonacci tree of h-2 as its right child. The pipelined Fibonacci tree broadcast has half the startup latency of the two-tree broadcast, but also only half of the throughput. It is faster for small messages, while the two-tree broadcast is faster for large messages.
Usage for other communication primitives
Reduction
… excerpt ends here. Continue reading the full article.
