Message-Passing Programming with MPI
Message-Passing Concepts
Reusing this material
This work is licensed under a Creative Commons Attribution- NonCommercial-ShareAlike 4.0 International License.
http://creativecommons.org/licenses/by-nc-sa/4.0/
This means you are free to copy and redistribute the material and adapt and build on the
material under the following terms: You must give appropriate credit, provide a link to the license and indicate if changes were made. If you adapt or build on the material you must distribute your work under the same license as the original.
Acknowledge EPCC as follows: EPCC, The University of Edinburgh, www.epcc.ed.ac.uk
Note that this presentation contains images owned by others. Please seek their permission before reusing these images.
3
Overview
• This lecture will cover – message passing model – SPMD
– communication modes
– collective communications
4
Programming Models
Serial Programming
Message-Passing Parallel Programming Concepts
Concepts
Arrays
Control flow Variables
Subroutines Human-readable OO
Processes
SPMD Groups
Send/Receive
Collectives
Python
Java
struct
C/C++
Fortran
if/then/else
Languages
Libraries
MPI
MPI_Init()
Implementations
Intel MPI OpenMPI
MPICH2
Cray MPI
IBM MPI
gcc -O3
crayftn
pgcc -fast
icc
javac
Implementations
craycc
5
Message Passing Model
• The message passing model is based on the notion of
过程的概念,
– can think of a process as an instance of a running program,
together with the programs data
• In the message passing model, parallelism is achieved by having many processes co-operate on the same task
• Each process has access only to its own data – ie all variables are private
• Processes communicate with each other by sending and receiving messages
– typically library calls from a conventional sequential language 6
processes
Sequential Paradigm
Memory
M
连续的范式
Process
Processor
7
P
Parallel Paradigm
Processes 0123
Message Passing Interface
isdated.jdohotnedtoknowtpngsicds.de
Communication Network
8
Distributed-Memory Architectures
Interconnect
P
M
P
M
P
M
P
M
P
M
P
M
P
M
P
M
9
Process Communication
Program
Process 2
Recv(1,b)
a=b+1
Process 1
a=23
Send(2,a)
a.
ababare.pro
23
24
Data
23 23
。在
10
SPMD
• Most message passing programs use the Single- Program-Multiple-Data (SPMD) model
• All processes run (their own copy of) the same program
• Each process has a separate copy of the data
• To make this useful, each process has a unique identifier
• Processes can follow different control paths through the program, depending on their process ID
• Usually run one process per processor / core
11
Emulating General Message Passing (C)
main (int argc, char **argv) {
if (controller_process)
{
} }
asmlopnoces.mg
Controller( /* Arguments */ ); }
else
{
Worker
( /* Arguments */ );
12
Emulating General Message Passing (F)
PROGRAM SPMD
IF (controller_process) THEN
ELSE
CALL WORKER
END PROGRAM SPMD
( ! Arguments ! )
ENDIF
CALL CONTROLLER ( ! Arguments ! )
13
Messages
• A message transfers a number of data items of a certain type from the memory of one process to the memory of another process
• A message typically contains – the ID of the sending processor – the ID of the receiving processor – the type of the data items
– the number of data items – the data itself
– a message type identifier
14
Communication modes
• Sending a message can either be synchronous or asynchronous
• A synchronous send is not completed until the message has started to be received
• An asynchronous send completes as soon as the makephoneausendemail.tn
message has gone
• Receives are usually synchronous – the receiving process must wait until the message arrives
15
Synchronous send
类似
• Analogy with faxing a letter.
• Know when letter has started to be received.
16
Asynchronous send
• Analogy with posting a letter.
• Only know when letter has been posted, not when it has been received.
17
Point-to-Point Communications
• We have considered two processes – one sender
– one receiver
• This is called point-to-point communication – simplest form of message passing
– relies on matching send and receive
• Close analogy to sending personal emails
18
Collective Communications
• A simple message communicates between two processes • There are many instances where communication between
groups of processes is required
• Can be built from simple messages, but often implemented separately, for efficiency
19
Barrier
• Global synchronisation 全球眇
Barrier
Barrier
Barrier
20
Broadcast
• One to all communication
21
Broadcast
• From one process to all others 8
88 8
8
8
22
Scatter 䩢
• Information scattered to many processes
1
2 012345
3
0
4
5
23
Gather
• Information gathered onto one process 1
2 012345
3
0
4
5
24
Reduction Operations
• Combine data from several processes to form a single result
Strike?
kgpare
25
Reduction
• Form a global sum, product, max, min, etc. 1
20 15
3
5
4
26
Launching a Message-Passing Program
• Write a single piece of source code
• with calls to message-passing functions such as send / receive
• Compile with a standard compiler and link to a message- passing library provided for you
• both open-source and vendor-supplied libraries exist
• Run multiple copies of same executable on parallel machine • each copy is a separate process
• each has its own private data completely distinct from others
• each copy can be at a completely different line in the program
• Running is usually done via a launcher program
• please run N copies of my executable called program.exe
启动程序
27
Issues
• Sends and receives must match – danger of deadlock
– program will stall (forever!)
• Possible to write very complicated programs, but – most scientific codes have a simple structure
– often results in simple communications patterns
• Use collective communications where possible – may be implemented in efficient ways
28
Summary (i)
• Messages are the only form of communication – all communication is therefore explicit 明星的 .
• Most systems use the SPMD model
– all processes run exactly the same code
– each has a unique ID
– processes can take different branches in the same codes
• Basic communications form is point-to-point
– collective communications implement more complicated patterns
that often occur in many codes
29
Summary (ii)
• Message-Passing is a programming model
– that is implemented by MPI
– the Message-Passing Interface is a library of function/subroutine calls
• Essential to understand the basic concepts – private variables
– explicit communications
– SPMD
• Major difficulty is understanding the Message-Passing model – a very different model to sequential programming
if (x < 0)
pin(Eo);
exit;
30