[SOLVED] CS FIT3143 LECTURE WEEK 9a

Information Technology
FIT3143 LECTURE WEEK 9a
PARALLEL ALGORITHM DESIGN ADVANCED MPI TOPICS

Copyright By Assignmentchef assignmentchef

Topic Overview
Revisiting Collective Communications with MPI Scatter & Gather Introduction to MPI Virtual Topologies
A portion of the content in the following slides were adopted from:
a) Introduction to the
Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)
(www.ichec.ie)
Learning outcome(s) related to this topic
Design and develop parallel algorithms for various parallel computing architectures (LO3)

Revisiting Collective Communications with MPI Scatter & Gather

Collective Communication
Communications involving a group of processes.
Must be called by all processes in a communicator.
Examples:
Barrier synchronization.
Broadcast, scatter, gather.
Global sum, global maximum, etc.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Characteristics of Collective Communication
Optimised Communication routines involving a group of processes
Collective action over a communicator, i.e. all processes must call the collective routine.
Synchronization may or may not occur.
All collective operations are blocking.
No tags.
Receive buffers must have exactly the same size as send buffers.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Barrier Synchronization
C: int MPI_Barrier(MPI_Comm comm)
MPI_Barrier is normally never needed:
all synchronization is done automatically by the data communication:
a process cannot continue before it has the data that it needs.
if used for debugging:
please guarantee, that it is removed in production.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

C: int MPI_Bcast(void *buf, int count, MPI_Datatype datatype, int root, MPI_Comm comm)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)
red red red red red
e.g., root=1
rank of the sending process (i.e., root process) must be given identically by all processes

scatter e.g., root=1
ABCDE ABCDE
C: int MPI_Scatter(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
C: int MPI_Scatterv(const void *sendbuf, const int *sendcounts, const int *displs, MPI_Datatype sendtype, void *recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

gather e.g., root=1
ABCDE ABCDE
C: int MPI_Gather(void *sendbuf, int sendcount, MPI_Datatype sendtype,
void *recvbuf, int recvcount, MPI_Datatype recvtype,
C: int MPI_Gatherv(const void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, const int *recvcounts, const int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm)
int root, MPI_Comm comm)
Click here for sample C code implementation of MPI Scatter & Gather Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Introduction to MPI Virtual Topologies
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Topologies Motivations
Need to create sets of processes For programming convenience
Make use of collectives routines
Need to map the abstract topology onto the natural topology of the problem domain
For programming convenience For performance
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Groups & communicators
A group is an ordered set of process identifiers
Each process in a group is associated with an rank
Usually one associates to groups communicators
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Working with groups
Select processes ranks to create groups
Associate to these groups new communicators
Use these new communicators as usual
MPI_Comm_group(comm, group) returns in group the group associated to the communicator comm
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)
Even_group

For the previous example
Odd_ranks={1, 3, 5}, Even_ranks={0, 2, 4}
1. MPI_comm_group(MPI_COMM_WORLD, Old_group)
2. MPI_Group_incl(Old_group, 3, Odd_ranks, &Odd_group)
3. MPI_Group_incl(Old_group, 3, Even_ranks, &Even_group)
int MPI_Comm_create(MPI_COMM_WORLD, Odd_group, Odd_Comm )
int MPI_Comm_create(MPI_COMM_WORLD, Even_group, Even_Comm)
Alternatively
color = modulo(myrank, 2)
MPI_Comm_split(MPI_COMM_WORLD, color, key, &newcomm)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Group Management
Group Accessors
MPI_Group_size()
MPI_Group_rank()
Group Constructors
MPI_COMM_GROUP() MPI_GROUP_INCL() MPI_GROUP_EXCL()
Group Destructors
MPI_GROUP_FREE(group)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Communicator Management
Communicator Accessors MPI_COMM_SIZE()
MPI_COMM_RANK()
Communicator Constructors MPI_COMM_CREATE()
MPI_COMM_SPLIT()
Communicator Destructors MPI_COMM_FREE(comm)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Virtual topology
For more complex mapping, MPI routines are available
Global array A(1:3000, 1:4000, 1:500) =
6109 words
3 x 4 x 5 = 60
0..2, 0..3, 0..4
processors
processcoordinates
example:
on process
decomposition, e.g., A(2001:3000, 1:1000, 301:400) =
virtual Cartesian topologies
ic0=2, ic1=0, ic2=3 (rank=43)
0.1109 words
processcoordinates: handledwith
Array decomposition: handled by the application program directly
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Graphical representation
Distribution of processes over the grid
Distribution of the Global Array
Coordinate (2, 0, 3) represents process number 43
It is being assigned the cube A(2001:3000, 1:1000, 301:400)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Virtual Topologies
Convenient process naming.
Simplifies writing of code.
Can allow MPI to optimize communications.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

How to use a Virtual Topology
Creating a topology produces a new communicator.
MPI provides mapping functions:
to compute process ranks, based on the topology naming scheme,
and vice versa.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Topology Types
Cartesian Topologies
each process is connected to its neighbor in a virtual grid,
boundaries can be cyclic, or not,
processes are identified by Cartesian coordinates,
of course,
communication between any two processes is still allowed.
Graph Topologies general graphs,
not covered here.
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Creating a Cartesian Virtual Topology
int MPI_Cart_create(MPI_Comm comm_old, int ndims,
int *dims, int *periods, int reorder,
MPI_Comm *comm_cart)
0369 (0,0) (1,0) (2,0) (3,0)
1 4 7 10 (0,1) (1,1) (2,1) (3,1)
2 5 8 11 (0,2) (1,2) (2,2) (3,2)
comm_old ndims dims periods
= MPI_COMM_WORLD = 2
= ( 1/.true., 0/.false. )
reorder = see next slide
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Example A 2-dimensional Cylinder
RanksandCartesianprocesscoordinatesincomm_cart
Ranks in comm and comm_cart may differ, if reorder = 1 or .TRUE.
This reordering can allow MPI to optimize communications
1 11 (0,1)
4 10 (1,1)
10 8 (3,1)
23 52 81 110 (0,2) (1,2) (2,2) (3,2)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Cartesian Mapping Functions
Mapping ranks to
process grid coordinates
int MPI_Cart_coords( MPI_Comm comm_cart,
int rank, int maxdims, int *coords)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Cartesian Mapping Functions
Mapping process grid coordinates to ranks int MPI_Cart_rank(MPI_Comm comm_cart,
int *coords, int *rank) 7
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Own coordinates
0369 (0,0) (1,0) (2,0) (3,0)
MPI_Cart_rank
1 4 7 10 (0,1) (1,1) (2,1) (3,1)
MPI_Cart_coords
2 5 8 11 (0,2) (1,2) (2,2) (3,2)
Each process gets its own coordinates with MPI_Comm_rank(comm_cart, my_rank, ierror) MPI_Cart_coords(comm_cart, my_rank, maxdims, my_coords, ierror)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Cartesian Mapping Functions?
Computing ranks of neighboring processes
int MPI_Cart_shift(MPI_Comm comm_cart, int direction, int disp,
int *rank_prev, int *rank_next) Returns MPI_PROC_NULL if there is no neighbor.
MPI_PROC_NULL can be used as source or destination rank in each communication
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

MPI_Cart_shift Example
0369 (0,0) (1,0) (2,0) (3,0)
1 4 7 10 (0,1) (1,1) (2,1) (3,1)
2 5 8 11 (0,2) (1,2) (2,2) (3,2)
invisible input argument: my_rank in cart
MPI_Cart_shift( cart, direction, displace, rank_prev, rank_next, ierror) example on 0 or +1 4 10
process rank=7 1 +1 6 8 Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

Cartesian Partitioning
Cut a grid up into slices.
A new communicator is produced for each slice.
Each slice can then perform its own collective communications.
int MPI_Cart_sub(MPI_Comm comm_cart, int *remain_dims, MPI_Comm *comm_slice)
0369 (0,0) (1,0) (2,0) (3,0)
1 4 7 10 (0,1) (1,1) (2,1) (3,1)
2 5 8 11 (0,2) (1,2) (2,2) (3,2)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

MPI_Cart_sub Example
RanksandCartesianprocesscoordinatesincomm_sub
00316293 (0,0) (0) (1,0) (1) (2,0) (2) (3,0) (3)
1 0 4 1 7 2 10 3 (0,1) (0) (1,1) (1) (2,1) (2) (3,1) (3)
2 0 5 1 8 2 11 3 (0,2) (0) (1,2) (1) (2,2) (2) (3,2) (3)
MPI_Cart_sub(comm_cart,remain_dims,comm_sub,ierror) (true, false)
Introduction to the Message Passing Interface (MPI), Irish Centre for High-End Computing (ICHEC)

CS: assignmentchef QQ: 1823890830 Email: [email protected]