Broadcast (parallel pattern)

Broadcast is a collective communication primitive in parallel programming to distribute programming instructions or data to nodes in a cluster.

[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.

is the time it takes for a message to travel to another node, independent of its length.

This grows exponentially as each time step the amount of sending nodes is doubled.

The time needed to distribute the first message piece is

is the time needed to send a package from one processor to another.

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.

[4] 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.

[2][4] [5][6][7] This algorithm aims to improve on some disadvantages of tree structure models with pipelines.

The algorithm concurrently uses two binary trees to communicate over.

It has also the same technical function in opposite side from B to A tree.

This means, two packets are sent and received by inner nodes and leaves in different steps.

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.

, 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.

In addition, a symmetric process makes this approach simple.

We need to find a schedule in order to make sure that no processor has to send or receive two messages from two trees in a step.

In this case the number of packet k is divided in half for each tree.

Both trees are working together the total number of packets

In this section, another broadcasting algorithm with an underlying telephone communication model will be introduced.

Fundamentally ESBT(Edge-disjoint Spanning Binomial Trees) is based on hypercube graphs, pipelining(

cyclically spreads packets to roots of ESBTs.

The roots of ESBTs broadcast data with binomial tree.

It takes another d steps until the last leaf node receives the packet.