Scribd
Upload
22 views23 pages

Collective Communication Operations in Parallel Computing

The document provides an introduction to parallel computing, focusing on collective communication operations essential for parallel algorithms. It covers various operations such as one-to-all broadcast, all-to-one reduction, and all-to-all communication patterns, emphasizing their importance for efficient parallel processing. Additionally, it discusses the implementation of these operations across different architectures and includes algorithms for various communication scenarios.

Uploaded by

ewnetdbu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views23 pages

Collective Communication Operations in Parallel Computing

The document provides an introduction to parallel computing, focusing on collective communication operations essential for parallel algorithms. It covers various operations such as one-to-all broadcast, all-to-one reduction, and all-to-all communication patterns, emphasizing their importance for efficient parallel processing. Additionally, it discusses the implementation of these operations across different architectures and includes algorithms for various communication scenarios.

Uploaded by

ewnetdbu
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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!
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

You might also like