PDP Chapter 5: Basic communication operations

One-to-All Broadcast and All-to-One Reduction

• Processors are connected and can communicate
• Data can be combined using operations like addition, minimum, maximum, AND, OR, or XOR
• One-to-all broadcast: Single processor sends data to all other processors
• All-to-one reduction: Data from all processors is combined and sent to a single processor
• Example: One processor has a vector, and another processor has a matrix. The vector can be broadcast to rows of processors, and the rows can calculate the product of the vector and matrix. This can be done concurrently for all rows. Then, the results can be summed using all-to-one reduction along the columns of processors.

Recursive Doubling for One-to-All and All-to-One

• Efficient way to perform one-to-all broadcast and all-to-one reduction on a ring of processors
• How it works:
  • Source processor initially broadcasts the data to another processor
  • Now, two independent problems are created, each with half the number of processors
  • The same procedure of broadcasting and reduction can be performed on the two halves
  • This process is repeated until all processors have the data (for broadcast) or the result is available at the desired processor (for reduction)
• Example: On an 8-node ring:
  • Source processor (Node 0) sends data to Node 1 in the first step
  • Node 0 and Node 1 both send data to Node 2 and Node 3 in the second step
  • This continues until all nodes have the data

All-Reduce

• Combines one-to-all broadcast and all-to-one reduction
• How it works:
  • All-to-one reduction is first performed to combine data from every processor to a single processor
  • Then, the combined data is broadcast to all processors using one-to-all broadcast
• Example: Given data A0 to F0 on different processors, the all-reduce operation would combine the data into H0 (A0 * B0 * C0 * D0 * E0 * F0) and then broadcast H0 to all of the processors.

Scatter and Gather

• Scatter operation: A single node sends a unique message to every other node
• Gather operation: A single node collects a unique message from each node

Broadcast and Reduction on a Mesh

• A grid of p processors with √p processors in each row and column can be viewed as a 2D array.
• How it works:
  • Broadcast or reduction is first performed along each row, followed by concurrent operations along each column
  • This can be generalized to higher dimensions
• Example: Broadcasting a message on a 16-node (4x4) mesh:
  • In the first step, the message is broadcast along the first row
  • In the second step, the message is broadcast along each of the four columns

Broadcast and Reduction on a Hypercube

• A hypercube with 2d nodes can be viewed as a d-dimensional mesh with two nodes in each dimension.
• How it works :
  • The mesh algorithm can be generalized to a hypercube, with operations carried out in d (= log p) steps
• Example: Broadcasting on a 3-dimensional hypercube:
  • In the first step, a node broadcasts the data to the other node in its dimension
  • This is repeated in the other two dimensions

Matrix-Vector Multiplication Example

• How broadcast and reduction can be used to efficiently multiply a matrix with a vector on a distributed system
• Each row of a processor grid is assigned a row of the matrix
• The first row is assigned the vector
• Broadcast the vector to all processors in a column
• Concurrently perform the local product of the vector and the matrix row
• Finally, use all-to-one reduction to sum the local products within each column, resulting in the final vector output
• This computation can be done concurrently for all columns of the matrix.

This quiz explores the concepts of one-to-all broadcast and all-to-one reduction in parallel processing. It delves into the operations used for data combination, such as addition and logical operations, and discusses efficient methods like recursive doubling for communication among processors. Test your understanding of these important parallel processing techniques.