MPI Collective Communication I

Cornell Theory Center

Presentation:
MPI Collective Communication I

This is the presentation layer of a two-part module. For an explanation of the layers and how to navigate within and between them, return to the top page of this module.

Table of Contents

Introduction
MPI Collective Communication Routines

2.1 Characteristics
2.2 Barrier Synchronization Routine
2.3 Data Movement Routines

2.3.1 Broadcast
2.3.2 Gather and Scatter
2.3.3 Gatherv and Scatterv
2.3.4 Allgather
2.3.5 Alltoall

2.4 Global Computation Routines

2.4.1 Reduce

Performance Issues

3.1 Example: Broadcast to 8 Processors
3.2 Example: Scatter to 8 Processors

References Lab Exercises Evaluation

1. Introduction

Collective Communication:

An MPI call made identically by all processes in process group
Supports easy manipulation of a "common" piece or set of information
Uses an MPI communicator, defined for the process group

2. MPI Collective Communication Routines

Barrier synchronization
Broadcast from one member to all other members
Gather data from an array spread across processors into one array
Scatter data from one member to all members
All-to-all exchange of data
Global reduction (e.g., sum, min of "common" data elements)
Scan across all members of a communicator

2.1 Characteristics

Performed on a group of processes,

identified by a communicator

Substitute for a sequence of point-to-point calls

Communications are locally blocking

Synchronization is not guaranteed

(implementation dependent)

Some routines use a root process

to originate or receive all data

Data amounts must exactly match

Many variations to basic categories

No message tags are needed

2.2 Barrier Synchronization Routine

Blocks the calling process until all group members have called the routine

Fortran Binding:

MPI_BARRIER	(`comm, ierr`)


C Binding:

MPI_Barrier	(MPI_comm `comm`)

2.3 Data Movement Routines

Broadcast
Gather and Gatherv
Scatter and Scatterv
Allgather and Allgatherv
Alltoall and Alltoallv

2.3.1 Broadcast

Send a message from the root process to all processes in the group, including the root process.

Fortran Binding:

MPI_BCAST	(`buffer, count, datatype, root, comm, ierr`)


C Binding:

int MPI_Bcast	(void* `buffer,` int `count,` MPI_Datatype `datatype,` int `root,` MPI_Comm `comm`)

Broadcast Effect

"hello, world" example used in earlier modules

Could use broadcast instead of multiple sends and receives

character(12) message
integer rank,root
data root/0/
call MPI_COMM_RANK(rank, MPI_COMM_WORLD, ierr)
if (rank .eq. root) then: message = 'Hello, world'
call MPI_BCAST(message, 12, MPI_CHARACTER, root,
& MPI_COMM_WORLD, ierr)
print*, 'node', rank, ':', message

2.3.2 Gather and Scatter

Gather Purpose:

Each process sends the contents of its send buffer to the root process.
The root process receives the messages and stores them in rank order.

Fortran Binding:

MPI_GATHER	(`sbuf, scount, stype, rbuf, rcount, rtype, root, comm, ierr`)


C Binding:

int MPI_Gather	(void* `sbuf,` int `scount,` MPI_Datatype `stype,` void* `rbuf,` int `rcount,` MPI_Datatype `rtype,` int `root,` MPI_Comm `comm`)

Scatter Purpose:

The root process splits a buffer of data into chunks,
then sends each process in the group 1 chunk.
- process 1 gets the first chunk,
- process 2 gets the second chunk, and so on.
Reverse of GATHER operation

Fortran Binding:
MPI_SCATTER	(`sbuf, scount, stype, rbuf, rcount, rtype, root, comm, ierr`)

C Binding:
int MPI_Scatter	(void* `sbuf,` int `scount,` MPI_Datatype `stype,` void* `rbuf,` int `rcount,` MPI_Datatype `rtype,` int `root,` MPI_Comm `comm`)

Gather & Scatter Effect

Matrix-vector multiply of matrix distributed by rows

Output vector needed in entirety by one process

Sample Code

DIMENSION A(25, 100), b(100), cpart(25), ctotal(100)

INTEGER root

DATA root/0/

DO I=1, 25

cpart(I) = cpart(I) + A(I, K)*b(K)

END DO

call MPI_GATHER(cpart, 25, MPI_REAL, ctotal, 25,

MPI_REAL, root, MPI_COMM_WORLD, ierr)

A: matrix distributed by rows

b: vector shared by all processes

c: vector updated by each process independently

2.3.3 Gatherv and Scatterv

Gatherv Purpose:

Same as GATHER, except that varying amounts of data may be gathered from each process.

Fortran Binding:

MPI_GATHERV	(`sbuf, scount, stype, rbuf, rcount, displs, rtype, root, comm, ierr`)

C Binding:

int MPI_Gatherv	(void* `sbuf,` int `scount,` MPI_Datatype `stype,` void* `rbuf,` int* `rcount,` int* `displs,` MPI_Datatype `rtype,` int `root,` MPI_Comm `comm`)

Scatterv Purpose:

varying

Fortran Binding:

MPI_SCATTERV	(`sbuf, scount, displs, stype, rbuf, rcount, rtype, root, comm, ierr`)

C Binding:

int MPI_Scatterv	(void* `sbuf,` int* `scount,` int* `displs,` MPI_Datatype `stype,` void* `rbuf,` int `rcount,` MPI_Datatype `rtype,` int `root,` MPI_Comm `comm`)

2.3.4 Allgather

Same as GATHER, except that all processes, not just root, receive the result
Data stored in rank order
Varying version (like GATHERV) called ALLGATHERV

Fortran Binding:

MPI_ALLGATHER	(`sbuf, scount, stype, rbuf, rcount, rtype, comm, ierr`)

C Binding:

int MPI_Allgather	(void* `sbuf,` int `scount,` MPI_Datatype `stype,` void* `rbuf,` int `rcount,` MPI_Datatype `rtype,` MPI_Comm `comm`)

Allgather Effect

Matrix-vector multiply of matrix distributed by rows

Output vector needed in entirety by all processes

Sample Code

DIMENSION A(25, 100), b(100), cpart(25), ctotal(100)

DO I=1, 25

cpart(I) = cpart(I) + A(I, K) * b(K)

END DO

call MPI_ALLGATHER(cpart, 25, MPI_REAL, ctotal, 25,

MPI_REAL, MPI_COMM_WORLD, ierr)

2.3.5 Alltoall

Extension to ALLGATHER

Each process sends distinct data to each receiver

Process i sends its jth block of data to process j

Process j stores data from process i in ith block

Varying data version (like GATHERV) called ALLTOALLV


Fortran Binding:

MPI_ALLTOALL	(`sbuf, scount, stype, rbuf, rcount, rtype, comm, ierr`)

C Binding:

int MPI_Alltoall	(void* `sbuf,` int `scount,` MPI_Datatype `stype,` void* `rbuf,` int `rcount,` MPI_Datatype `rtype,` MPI_Comm `comm`)

Alltoall Effect

2.4 Global Computation Routines

Communication routines that include a computation
Computation function included in routine call may be either
- An MPI predefined routine or
- A user-supplied function
Two types of global computation routines:
- Reduce
- Scan

2.4.1 Reduce

Combine the elements of the input buffer of each process using a specified operation
Return result to root process

Fortran Binding:
MPI_REDUCE	(`sbuf, rbuf, count, stype, op, root, comm, ierr`)

C Binding:
int MPI_Reduce	( void* `sbuf,` void* `rbuf,` int `count,` MPI_Datatype `stype,` MPI_Op `op,` int `root,` MPI_Comm `comm`)

**MPI Predefined Reduce Operations**
Name	Meaning	Datatypes
MPI_MAX	maximum value	Each of these operations makes sense for only certain datatypes. The MPI Standard lists the types accepted for each operation.
MPI_MIN	minimum value
MPI_SUM	sum
MPI_PROD	product
MPI_LAND	logical and
MPI_BAND	bit-wise and
MPI_LOR	logical or
MPI_BOR	bit-wise or
MPI_LXOR	logical xor
MPI_BXOR	bit-wise xor
MPI_MAXLOC	max value and location
MPI_MINLOC	min value and location

Reduce effect

Example:

Each process in a forest dynamics simulation calculates the maximum tree height for its region.
Process 0, which is writing output, must know the global maximum height.

Sample Code

INTEGER maxht, globmx: .
. (calculations which determine maximum height)
.
call MPI_REDUCE (maxht, globmx, 1, MPI_INTEGER,: MPI_MAX, 0, MPI_COMM_WORLD, ierr)
IF (taskid.eq.0) then: .
. (Write output)
.
END IF

User-defined Operations

User can define his/her own reduce operation
Makes use of the MPI_OP_CREATE function

Reduce Variations

MPI_ALLREDUCE allows the result to appear in the receive buffers of all processes in the group.
MPI_REDUCE_SCATTER scatters a vector, which results from a reduce operation, across all processes.
MPI_SCAN performs a partial reduction in which process i receives data from processes 0 through i, inclusive.

3. Performance Issues

A great deal of hidden communication takes place with collective communication
Performance depends greatly on the particular implementation of MPI
Because there may be forced synchronization, not always best to use collective communication

3.1 Example: Broadcast to 8 Processors

Simple Approach

Amount of data transferred: (N-1)*p

Number of steps: N-1

Better approach

Amount of data transferred: (N-1)*p

₂

3.2 Example: Scatter to 8 Processors

Simple Approach

Amount of data transferred: (N-1)*p

Number of steps: (N-1)*p

Better Approach

Amount of data transferred: log₂(N)*N*p/2

₂

References

Book

Using MPI: Portable Parallel Programming with the Message-Passing Interface, by William Gropp, Ewing Lusk, and Anthony Skjellum. Published 10/21/94 by MIT Press, 328 pages.

World Wide Web

MPI: A Message-Passing Interface Standard June 1995
Argonne National Lab. MPI page: Message Passing Interface (MPI) Standard
Mississippi State Engineering Research Center: Message-Passing Interface
Netlib: MPI
Notre Dame: LAM/MPI Parallel Computing
Introduction to MPI, Message-Passing Interface Standard
MPI Point-to-Point Communication I
CTC's MPI Documentation

Lab exercises for MPI Collective Communication I

Please complete this short evaluation form. Thank you!

[CTC Home Page]

[Education]

[Copyright Statement]

[Feedback]

[Resources]

URL http://www.tc.cornell.edu/Edu/Talks/MPI/Collective.I/less.html