Microsoft PowerPoint – Chapter 4 – Basic Communication Operations
Introduction to
Parallel Computing
George Karypis
Basic Communication Operations
Outline
Importance of Collective Communication
Operations
One-to-All Broadcast
All-to-One Reduction
All-to-All Broadcast & Reduction
All-Reduce & Prefix-Sum
Scatter and Gather
All-to-All Personalized
Collective Communication
Operations
They represent regular communication patterns that are
performed by parallel algorithms.
Collective: Involve groups of processors
Used extensively in most data-parallel algorithms.
The parallel efficiency of these algorithms depends on
efficient implementation of these operations.
They are equally applicable to distributed and shared
address space architectures
Most parallel libraries provide functions to perform them
They are extremely useful for “getting started” in parallel
processing!
MPI Names
One-to-All Broadcast &
All-to-One Reduction
Broadcast on a Ring Algorithm
Reduction on a Ring Algorithm
Broadcast on a Mesh
Broadcast on a Hypercube
Code for the Broadcast
Source: Root
Code for Broadcast
Arbitrary Source
All-to-All Broadcast & Reduction
All-to-All Broadcast for Ring
All-to-All Broadcast on a Mesh
All-to-All Broadcast on a HCube
All-Reduce & Prefix-Sum
Scatter & Gather
Scatter Operation on HCube
All-to-All Personalized (Transpose)
All-to-all Personalized on a Ring
All-to-all Personalized on a Mesh
All-to-all Personalized on a HCube
All-to-all Personalized on a HCube
Improved Algorithm
Perform log(p) point-to-point
communication steps
Processor i communicates
with processor iXORj during
the jth communication step.
Complexities