Broadcast is a collective communication primitive in parallel programming to distribute programming instructions or data to nodes in a cluster. It is the reverse operation of reduction.^[1] The broadcast operation is widely used in parallel algorithms, such as matrix-vector multiplication,^[1] Gaussian elimination and shortest paths.^[2]

The Message Passing Interface implements broadcast in MPI_Bcast.^[3]

Definition

A message ${\displaystyle M[1..m]}$of length ${\displaystyle m}$ should be distributed from one node to all other ${\displaystyle p-1}$ nodes.

${\displaystyle T_{\text{byte}}}$is the time it takes to send one byte.

${\displaystyle T_{\text{start}}}$is the time it takes for a message to travel to another node, independent of its length.

Therefore, the time to send a package from one node to another is ${\displaystyle t=\mathrm {size} \times T_{\text{byte}}+T_{\text{start}}}$.^[1]

${\displaystyle p}$ is the number of nodes and the number of processors.

Binomial Tree Broadcast

Binomial Tree Broadcast

With Binomial Tree Broadcast the whole message is sent at once. Each node that has already received the message sends it on further. This grows exponentially as each time step the amount of sending nodes is doubled. The algorithm is ideal for short messages but falls short with longer ones as during the time when the first transfer happens only one node is busy.

Sending a message to all nodes takes ${\displaystyle \log _{2}(p)t}$ time which results in a runtime of ${\displaystyle \log _{2}(p)(mT_{\text{byte}}+T_{\text{start}})}$

Message M

id := node number
p := number of nodes

if id > 0  
    blocking_receive M
for (i := ceil(log_2(p)) - 1; i >= 0; i--)
    if (id % 2^(i+1) == 0 && id + 2^i <= p)
        send M to node id + 2^i

^[4]

Linear Pipeline Broadcast

Pipeline Broadcast

The message is split up into ${\displaystyle k}$ packages and send piecewise from node ${\displaystyle n}$ to node ${\displaystyle n+1}$. The time needed to distribute the first message piece is ${\textstyle pt={\frac {m}{k}}T_{\text{byte}}+T_{\text{start}}}$ whereby ${\displaystyle t}$ is the time needed to send a package from one processor to another.

Sending a whole message takes ${\displaystyle (p+k)\left({\frac {mT_{\text{byte}}}{k}}+T_{\text{start}}\right)=(p+k)t=pt+kt}$.

Optimal is to choose ${\displaystyle k={\sqrt {\frac {m(p-2)T_{\text{byte}}}{T_{\text{start}}}}}}$ resulting in a runtime of approximately

$${\displaystyle mT_{\text{byte}}+pT_{\text{start}}+{\sqrt {mpT_{\text{start}}T_{\text{byte}}}}}$$

The run time is dependent on not only message length but also the number of processors that play roles. This approach shines when the length of the message is much larger than the amount of processors.

Message M := [m_1, m_2, ..., m_n]
id = node number

for (i := 1; i <= n; i++) in parallel
    if (id != 0)
        blocking_receive m_i
        
    if (id != n)
        send m_i to node id + 1

^[4]

Pipelined Binary Tree Broadcast

Pipelined Binary Tree Broadcast

This algorithm combines Binomial Tree Broadcast and Linear Pipeline Broadcast, which makes the algorithm work well for both short and long messages. The aim is to have as many nodes work as possible while maintaining the ability to send short messages quickly. A good approach is to use Fibonacci trees for splitting up the tree, which are a good choice as a message cannot be sent to both children at the same time. This results in a binary tree structure.

We will assume in the following that communication is full-duplex. The Fibonacci tree structure has a depth of about ${\displaystyle d\approx \log _{\Phi }(p)}$whereby ${\displaystyle \Phi ={\frac {1+{\sqrt {5}}}{2}}}$the golden ratio.

The resulting runtime is ${\textstyle ({\frac {m}{k}}T_{\text{byte}}+T_{\text{start}})(d+2k-2)}$. Optimal is ${\displaystyle k={\sqrt {\frac {n(d-2)T_{\text{byte}}}{3T_{\text{start}}}}}}$.

This results in a runtime of ${\displaystyle 2mT_{\text{byte}}+T_{\text{start}}\log _{\Phi }(p)+{\sqrt {2m\log _{\Phi }(p)T_{\text{start}}T_{\text{byte}}}}}$.

Message M := [m_1, m_2, ..., m_k]

for i = 1 to k 
    if (hasParent())
        blocking_receive m_i
        
    if (hasChild(left_child))
        send m_i to left_child
        
    if (hasChild(right_child))
        send m_i to right_child

^[2][4]

Two Tree Broadcast (23-Broadcast)

^[5][6][7]

Visualization of Two Tree Broadcast

Tree construction

Examples of tree structures depending on the number of processors

The number of steps needed to construct two parallel-working binary trees is dependent on the amount of processors. Like with other structures one processor can is the root node who sends messages to two trees. It is not necessary to set a root node, because it is not hard to recognize that the direction of sending messages in binary tree is normally top to bottom. There is no limitation on the number of processors to build two binary trees. Let the height of the combined tree be h = ⌈log(p + 2)⌉. Tree A and B can have a height of ${\displaystyle h-1}$. Especially, if the number of processors correspond to ${\displaystyle p=2^{h}-1}$, we can make both sides trees and a root node.

To construct this model efficiently and easily with a fully built tree, we can use two methods called "Shifting" and "Mirroring" to get second tree. Let assume tree A is already modeled and tree B is supposed to be constructed based on tree A. We assume that we have ${\displaystyle p}$ processors ordered from 0 to ${\displaystyle p-1}$.

Shifting

Tree construction using "Shifting"

The "Shifting" method, first copies tree A and moves every node one position to the left to get tree B. The node, which will be located on -1, becomes a child of processor ${\displaystyle p-2}$.

Mirroring

Tree construction using mirroring

"Mirroring" is ideal for an even number of processors. With this method tree B can be more easily constructed by tree A, because there are no structural transformations in order to create the new tree. In addition, a symmetric process makes this approach simple. This method can also handle an odd number of processors, in this case, we can set processor ${\displaystyle p-1}$ as root node for both trees. For the remaining processors "Mirroring" can be used.

ESBT-Broadcasting (Edge-disjoint Spanning Binomial Trees)

In this section, another broadcasting algorithm with an underlying telephone communication model will be introduced. A Hypercube creates network system with ${\displaystyle p=2^{d}(d=0,1,2,3,...)}$. Every node is represented by binary ${\displaystyle {0,1}}$ depending on the number of dimensions. Fundamentally ESBT(Edge-disjoint Spanning Binomial Trees) is based on hypercube graphs, pipelining(${\displaystyle m}$ messages are divided by ${\displaystyle k}$ packets) and binomial trees. The Processor ${\displaystyle 0^{d}}$ cyclically spreads packets to roots of ESBTs. The roots of ESBTs broadcast data with binomial tree. To leave all of ${\displaystyle k}$ from ${\displaystyle p_{0}}$, ${\displaystyle k}$ steps are required, because all packets are distributed by ${\displaystyle p_{0}}$. It takes another d steps until the last leaf node receives the packet. In total ${\displaystyle d+k}$ steps are necessary to broadcast ${\displaystyle m}$ message through ESBT.

The resulting run time is ${\textstyle T(m,p,k)=({\frac {m}{k}}T_{\text{byte}}+T_{\text{start}})(k+d)}$. ${\textstyle (k={\sqrt {{mdT_{\text{byte}}}/{T_{\text{start}}}}})}$.

This results in a run time of ${\displaystyle T(m,p):=mT_{\text{byte}}+dT_{\text{start}}+{\sqrt {mdT_{\text{start}}T_{\text{byte}}}}}$.

^[8][9]

See also

• Reduction operator

References