Module -3
Distributed Memory Programming with MPI
Course Outcome:
At the end of the course, the student will be able to Apply MPI
library to parallelize the code to solve the given problem
Topic
●
Introduction
●
MPI Functions
●
Trapezoidal Rule in MPI
●
Dealing with I/O
●
Collective Communication
●
MPI-derived datatypes
●
Performance Evaluation
●
Parallel Sorting Algorithm
Introduction
●
MPI (Message-Passing Interface) is used for writing parallel
programs for distributed-memory systems
●
It is a library of functions using which processes can send and
receive messages
●
Messages are sent through ‘send’ functions
●
Messages are received through ‘receive’ functions
●
Global communications can be achieved through ‘collective’
communications
Introduction
●
Sample program
●
MPI_Init:
– it tells the MPI system to do all necessary setup
– like allocating storage for message buffers, assigning ranks
to processes, etc
– No other MPI functions must be called prior to this
Introduction
●
MPI_Finalize:
– tells the MPI system that we’re done using MPI and any
resources allocated can be freed
– No MPI functions should be called after this
Introduction
●
MPI_Comm_size:
– Gets info about number of processes in a communicator
– This info is returned in the second arg of the function
●
MPI_Comm_rank:
– Gets the rank assigned to the calling process
– This info is returned in the second arg of the function
Introduction
Introduction
●
MPI_Send:
– Used to send message from ‘source’ to ‘destination’ process
– Syntax: (in next slide)
– First arg: pointer to message to be sent
– Second arg: size of message
– Third arg: type of message
– Fourth arg: specifies the destination process rank
– Fifth arg: a non-negative int, to distinguish messages sent by a process
– Sixth arg: communicator, specifying group of processes in it
Introduction
Introduction
●
MPI_Recv:
– Used to receive message from other processes
– Syntax: (in next slide)
– First arg: pointer to memory where message will be stored
– Second arg: size of message that can be stored
– Third arg: type of message
– Fourth arg: sending process rank
– Fifth arg: must match ‘tag’ of sending process
– Sixth arg: must match ‘communicator’ of sending process
– Seventh arg: used to get more info about sending process
Introduction
Introduction
Predefined MPI Datatypes
Trapezoidal rule
●
Classic example of ‘how to create parallel programs for problems’
●
Problem: find the area under the curve between the 2 extremes ‘a’
and ‘b’, where a < b
●
Solution:
– divide the area under the curve between ‘a’ and ‘b’ into ‘n’
subintervals of equal length
– Calculate the areas of each subinterval and sum it up to get the
total area under the curve
Trapezoidal rule
Trapezoidal rule
Program link1 Program link2
Dealing with I/O
●
In MPI, any process can access ‘stdout’
●
But only Process 0 can access ‘stdin’
●
Hence, Process 0 has to collect input from user and pass it to
other processes using MPI_Send
Dealing with I/O
Function where Process 0
reads data from user and
sends them to all other
process
Collective Communication
●
It is a communication that involve all processes in a communicator
●
Communication between a single source and destination is called
“point-to-point” communication
●
MPI_Send and MPI_Recv are used for point-to-point communication
●
For a collective communication, MPI provides 3 functions:
MPI_Reduce, MPI_Allreduce and MPI_Bcast
●
MPI_Reduce and MPI_Allreduce are used to send input & output
●
MPI_Bcast is used to send input
Collective Communication
the final result is available only
to dest_process
the final result is available to all
processes
Collective Communication
●
Where:
– input_data_p : input buffer from where processes will read data
– output_data_p : output buffer where all processes store their result
– Count : size of data, 1=> scalar, n => n-dim vector
– Datatype: MPI datatype
– Operator : MPI operator used to reduce data (next slide)
– dest_process : process to which final result should be sent to
– Comm : communicator, to which all processes belongs
Collective Communication
Reduction Operator in MPI
Collective Communication
Where
data_p : data to be communicated to all processes
Count : dimension of data
Datatype : data type of data
source_proc : process that sends data to all processes
Comm : communicator
Collective Communication
Function where Process 0
reads data from user and
sends them to all other process
through MPI_Bcast function
Data Distribution
●
Data Distribution among processes can be done in 3 ways:
– Block partition: blocks of data is assigned to each process
– Cyclic partition: each data is assigned to each process in
round-robin fashion
– Block-cyclic: blocks of data is assigned in a cyclic fashion
to each process
Data Distribution
Different partitions of a 12-component vector among 3 processes
Data Distribution
●
To distribute data among processes, MPI provides a function “MPI_Scatter”
Data Distribution
●
Where
– send_buf_p: buffer that stores the complete data
– send_count : amount of data going to each process
– send_type: type of data being sent
– recv_buf_p: buffer where received data will be stored
– recv_count: amount of data getting received
– recv_type: type of data being received
– src_proc : sending process rank, should be zero
– Comm: communicator to which processes belongs
Data Distribution
A function for reading and
distributing a vector
Data Distribution
●
To collect results from different processes, MPI provides a function “MPI_Gather”
Data Distribution
●
Where data referred by send_buf_p by process 0 is stored in
first block of recv_buf_p
●
Data referred by send_buf_p by process 1 is stored in next
block of recv_buf_p and so on
Data Distribution
A function for collecting and
printing a distributed vector
MPI-derived datatypes
●
Used to represent any collection of data items in memory
●
It consists of a sequence of basic MPI datatypes together with a ‘displacement’
for each of the datatypes
●
The ‘MPI_Type_create_struct()’ function can be used to create a derived
datatype
●
Once created, it must be commited with a call to function:
MPI_Type_commit()
●
After using, it must be destroyed by calling function: MPI_Type_free()
●
The address of the data can be found by calling function: MPI_Get_address()
MPI-derived datatypes
MPI-derived datatypes
Performance Evaluation
●
Used to re
Parallel Sorting Algorithm
●
Bubble sort cannot be parallelized as comparision of keys at consecutive
positions need to be done
●
A variant of bubble sort called “odd-even transposition” sort can be parallelized
●
The idea is to decouple compare-swaps
●
The algorithm runs in 2-phases: odd phase and even-pahse
●
During even-phase compare-swap is executed on pairs (a[0], a[1]),
(a[2],a[3]),...
●
During odd-phase compare-swaps is executed on pairs (a[1],a[2]),
(a[3],a[4]),...
Parallel Sorting Algorithm
Parallel Sorting Algorithm
Serial odd-even transposition sort
Parallel Sorting Algorithm
Parallel odd-even transposition sort algorithm
Parallel Sorting Algorithm
Safety in MPI programs
●
If an MPI program depends on MPI-provided buffering for sending and receiving
message, then it is said to be “unsafe”
●
For example, if all processes send message at the same time and then try to
receive message, it creates “deadlock”
●
How to tell if a program is safe?
– Use an alternative to MPI_Send called “MPI_Ssend”, if the program doesn’t
hang or crash, it’s safe
●
How to modify communication to make program safe?
– Instead of manual scheduling by us, use “MPI_Sendrecv”
Safety in MPI programs
Safety in MPI programs