Distributed Memory Programming With: Peter Pacheco

An Introduction to Parallel Programming
Peter Pacheco
Chapter 3
Distributed Memory
Programming with
MPI
Copyright © 2010, Elsevier Inc. All rights Reserved 1

# Chapter Subtitle
Roadmap
 Writing your first MPI program.

 Using the common MPI functions.
 The Trapezoidal Rule in MPI.
 Collective communication.
 MPI derived datatypes.
 Performance evaluation of MPI programs.
 Parallel sorting.
 Safety in MPI programs.

A distributed memory system

A shared memory system

Hello World!
(a classic)
5
Identifying MPI processes
 Common practice to identify processes by
nonnegative integer ranks.
 p processes are numbered 0, 1, 2, .. p-1
6
Our first MPI program
7
Compilation
wrapper script to compile

source file
mpicc -g -Wall -o mpi_hello mpi_hello.c
produce create this executable file name

debugging (as opposed to default a.out)
information
turns on all warnings
8
Execution
mpiexec -n <number of processes> <executable>
mpiexec -n 1 ./mpi_hello
run with 1 process
run with 4 processes
9
Execution
Greetings from process 0 of 1 !

10
MPI Programs
 Written in C.
 Has main.
 Uses stdio.h, string.h, etc.
 Need to add mpi.h header file.
 Identifiers defined by MPI start with
“MPI_”.
 First letter following underscore is
uppercase.
 For function names and MPI-defined types.
 Helps to avoid confusion.
11
MPI Components
 MPI_Init
 Tells MPI to do all the necessary setup.
 MPI_Finalize
 Tells MPI we’re done, so clean up anything
allocated for this program.
13
Basic Outline
14
Communicators
 A collection of processes that can send

messages to each other.
 MPI_Init defines a communicator that consists of
all the processes created when the program is
started.
 Called MPI_COMM_WORLD.
15
Communicators
number of processes in the communicator
my rank
(the process making this call)
16
SPMD
 Single-Program Multiple-Data
 We compile one program.
 Process 0 does something different.
 Receives messages and prints them while the
other processes do the work.
 The if-else construct makes our program

SPMD.
17
Communication

Data types

Communication

Message matching
r
MPI_Send
src = q
MPI_Recv
dest = r

Receiving messages
 A receiver can get a message without
knowing:
 the amount of data in the message,
 the sender of the message,
 or the tag of the message.

status_p argument
MPI_Status*
MPI_Status* status; MPI_SOURCE

MPI_TAG
MPI_ERROR
status.MPI_SOURCE
status.MPI_TAG

How much data am I receiving?

Issues with send and receive
 Exact behavior is determined by the MPI
implementation.
 MPI_Send may behave differently with regard to
buffer size, cutoffs and blocking.
 MPI_Recv always blocks until a matching
message is received.
 Know your implementation;
don’t make assumptions!

TRAPEZOIDAL RULE IN MPI

The Trapezoidal Rule

The Trapezoidal Rule

One trapezoid

Pseudo-code for a serial program

Parallelizing the Trapezoidal Rule
1. Partition problem solution into tasks.

2. Identify communication channels between
tasks.
3. Aggregate tasks into composite tasks.
4. Map composite tasks to cores.

Parallel pseudo-code

Tasks and communications for
Trapezoidal Rule

First version (1)

First version (2)

First version (3)

Dealing with I/O
Each process just

prints a message.

Running with 6 processes
unpredictable output

Input
 Most MPI implementations only allow process 0
in MPI_COMM_WORLD access to stdin.
 Process 0 must read the data (scanf) and send
to the other processes.

Function for reading user input

COLLECTIVE
COMMUNICATION

A tree-structured global sum

Tree-structured communication
1. In the first phase:

(a) Process 1 sends to 0, 3 sends to 2, 5 sends to 4, and
7 sends to 6.
(b) Processes 0, 2, 4, and 6 add in the received values.
(c) Processes 2 and 6 send their new values to
processes 0 and 4, respectively.
(d) Processes 0 and 4 add the received values into their
new values.
2. (a) Process 4 sends its newest value to process 0.

(b) Process 0 adds the received value to its newest
value.

An alternative tree-structured global sum
44
MPI_Reduce
45
18 and 28 lines are replaced with MPI_reduce 46
Predefined reduction operators in MPI
47
Collective vs. Point-to-Point Communications
 All the processes in the communicator must call

the same collective function.
 For example, a program that attempts to match a

call to MPI_Reduce on one process with a call to
MPI_Recv on another process is erroneous, and,
in all likelihood, the program will hang or crash.
48
 The arguments passed by each process to an

MPI collective communication must be
“compatible.”
 For example, if one process passes in 0 as the

dest_process and another passes in 1, then the
outcome of a call to MPI_Reduce is erroneous,
and, once again, the program is likely to hang or
crash.

 The output_data_p argument is only used

on dest_process.
 However, all of the processes still need to

pass in an actual argument corresponding
to output_data_p, even if it’s just NULL.

 Point-to-point communications are matched on

the basis of tags and communicators.
 Collective communications don’t use tags.

 They’re matched solely on the basis of the
communicator and the order in which
they’re called.

Example (1)
Multiple calls to MPI_Reduce

the order of the calls determine the result.
b seems to be 3 but it is 4.
d seems to be 4 but it is 5
52
MPI_Allreduce
 Useful in a situation in which all of the processes

need the result of a global sum in order to
complete some larger computation.

A global sum followed
by distribution of the
result.

A butterfly-structured global sum.

Broadcast
Data belonging to a single process is sent to

all of the processes in the communicator.

A tree-structured broadcast.

A version of Get_input that uses MPI_Bcast

Data distributions
Compute a vector sum.
Serial implementation of vector addition

Different partitions of a 12-component
vector among 3 processes

Partitioning options
 Block partitioning
 Assign blocks of consecutive components to
each process.
 Cyclic partitioning
 Assign components in a round robin fashion.
 Block-cyclic partitioning
 Use a cyclic distribution of blocks of
components.

Parallel implementation of
vector addition

Scatter
 MPI_Scatter can be used in a function that reads in an
entire vector on process 0 but only sends the needed
components to each of the other processes.

Reading and distributing a vector
64
Gather
 Collect all of the components of the vector onto
process 0, and then process 0 can process all of
the components.
65
Print a distributed vector

Allgather
 Concatenates the contents of each process’
send_buf_p and stores this in each process’
recv_buf_p.
 As usual, recv_count is the amount of data being
received from each process.

Matrix-vector multiplication

69
i-th component of y
Dot product of the ith
row of A with x.

Multiply a matrix by a vector
Serial pseudo-code

C style arrays
stored as

Serial matrix-vector multiplication

An MPI matrix-vector multiplication function

MPI DERIVED DATATYPES
75
Derived datatypes
 Used to represent any collection of data items in
memory by storing both the types of the items
and their relative locations in memory.
 The idea is that if a function that sends data
knows this information about a collection of data
items, it can collect the items from memory
before they are sent.
 Similarly, a function that receives data can
distribute the items into their correct destinations
in memory when they’re received.

Derived datatypes
 Formally, consists of a sequence of basic
MPI data types together with a
displacement for each of the data types.
 Trapezoidal Rule example:

MPI_Type create_struct
 Builds a derived datatype that consists of

individual elements that have different
basic types.

MPI_Get_address
 Returns the address of the memory

location referenced by location_p.
 The special type MPI_Aint is an integer
type that is big enough to store an address
on the system.

MPI_Type_commit
Allows the MPI implementation to optimize

its internal representation of the datatype
for use in communication functions.

MPI_Type_free
 When we’re finished with our new type,

this frees any additional storage used.

Get input function with a derived datatype



HERE

PERFORMANCE EVALUATION
86
Elapsed parallel time
Returns the number of seconds that have

elapsed since some time in the past.
87
Elapsed serial time
 In this case, you don’t need to link in the MPI
libraries.
 Returns time in microseconds elapsed from
some point in the past.
88
Elapsed serial time
89
MPI_Barrier
Ensures that no process will return from calling it
until every process in the communicator has
started calling it.
90
MPI_Barrier
91
Run-times of serial and parallel
matrix-vector multiplication
(Seconds)
92
Speedup

Efficiency

Speedups of Parallel Matrix-Vector Multiplication

Efficiencies of Parallel Matrix-Vector Multiplication

Scalability
A program is scalable if the problem size can be
increased at a rate so that the efficiency doesn’t
decrease as the number of processes increase.

Scalability
Programs that can maintain a constant efficiency
without increasing the problem size are
sometimes said to be strongly scalable.
Programs that can maintain a constant efficiency if

the problem size increases at the same rate as
the number of processes are sometimes said to
be weakly scalable.

A PARALLEL SORTING ALGORITHM

Sorting
 n keys and p = comm sz processes.
 n/p keys assigned to each process.
 No restrictions on which keys are assigned to
which processes.
 When the algorithm terminates:
 The keys assigned to each process should be sorted
in (say) increasing order.
 If 0 ≤ q < r < p, then each key assigned to process q
should be less than or equal to every key assigned to
process r.
100
Serial bubble sort
101
Odd-even transposition sort
 A sequence of phases.
 Even phases, compare swaps:
 Odd phases, compare swaps:
102
Example
Start: 5, 9, 4, 3
Even phase: compare-swap (5,9) and (4,3)
getting the list 5, 9, 3, 4
Odd phase: compare-swap (9,3)
Even phase: compare-swap (5,3) and (9,4)
Odd phase: compare-swap (5,4)
103
Serial odd-even transposition sort
104
Communications among tasks in odd-even sort
Tasks determining a[i] are labeled with a[i].
105
Parallel odd-even transposition sort
106
Pseudo-code
107
Compute_partner
108
Safety in MPI programs
 The MPI standard allows MPI_Send to behave in

two different ways:
 it can simply copy the message into an MPI managed
buffer and return,
 or it can block until the matching call to MPI_Recv
starts.
109
 HERE……….

 Many implementations of MPI set a threshold at
which the system switches from buffering to
blocking.
 Relatively small messages will be buffered by
MPI_Send.
 Larger messages, will cause it to block.
111
 If the MPI_Send executed by each process

blocks, no process will be able to start executing
a call to MPI_Recv, and the program will hang or
deadlock.
 Each process is blocked waiting for an event that

will never happen.
(see pseudo-code)
112
 A program that relies on MPI provided
buffering is said to be unsafe.
 Such a program may run without problems

for various sets of input, but it may hang or
crash with other sets.
113
MPI_Ssend
 An alternative to MPI_Send defined by the MPI
standard.
 The extra “s” stands for synchronous and
MPI_Ssend is guaranteed to block until the
matching receive starts.
114
Restructuring communication
115
MPI_Sendrecv
 An alternative to scheduling the communications
ourselves.
 Carries out a blocking send and a receive in a
single call.
 The dest and the source can be the same or
different.
 Especially useful because MPI schedules the
communications so that the program won’t hang
or crash.

MPI_Sendrecv

Parallel odd-even transposition sort

Run-times of parallel odd-even sort
(times are in milliseconds)

Concluding Remarks (1)
 MPI or the Message-Passing Interface is a
library of functions that can be called from C,
C++, or Fortran programs.
 A communicator is a collection of processes
that can send messages to each other.
 Many parallel programs use the single-program
multiple data or SPMD approach.

 Most serial programs are deterministic: if we run
the same program with the same input we’ll get
the same output.
 Parallel programs often don’t possess this
property.
 Collective communications involve all the
processes in a communicator.

 When we time parallel programs, we’re usually
interested in elapsed time or “wall clock time”.
 Speedup is the ratio of the serial run-time to the
parallel run-time.
 Efficiency is the speedup divided by the number of
parallel processes.

 If it’s possible to increase the problem size (n) so
that the efficiency doesn’t decrease as p is
increased, a parallel program is said to be
scalable.
 An MPI program is unsafe if its correct behavior
depends on the fact that MPI_Send is buffering its
input.

124
 Parallel Bubblesort
 Parallel Quicksort
 Parallel Mergesort
 Parallel Paritioning
125

Distributed Memory Programming With: Peter Pacheco

Uploaded by

Copyright:

Available Formats

Distributed Memory Programming With: Peter Pacheco

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Distributed Memory Programming With: Peter Pacheco

Uploaded by

Copyright:

Available Formats

An Introduction to Parallel Programming

Copyright © 2010, Elsevier Inc. All rights Reserved 1

 Writing your first MPI program.

Copyright © 2010, Elsevier Inc. All rights Reserved 2

Copyright © 2010, Elsevier Inc. All rights Reserved 3

Copyright © 2010, Elsevier Inc. All rights Reserved 4

 p processes are numbered 0, 1, 2, .. p-1

wrapper script to compile

mpicc -g -Wall -o mpi_hello mpi_hello.c

produce create this executable file name

turns on all warnings

mpiexec -n <number of processes> <executable>

run with 1 process

run with 4 processes

Greetings from process 0 of 1 !

Greetings from process 0 of 4 !

 A collection of processes that can send

number of processes in the communicator

 The if-else construct makes our program

Copyright © 2010, Elsevier Inc. All rights Reserved 18

Copyright © 2010, Elsevier Inc. All rights Reserved 19

Copyright © 2010, Elsevier Inc. All rights Reserved 20

Copyright © 2010, Elsevier Inc. All rights Reserved 21

Copyright © 2010, Elsevier Inc. All rights Reserved 22

MPI_Status* status; MPI_SOURCE

Copyright © 2010, Elsevier Inc. All rights Reserved 23

Copyright © 2010, Elsevier Inc. All rights Reserved 24

Copyright © 2010, Elsevier Inc. All rights Reserved 25

Copyright © 2010, Elsevier Inc. All rights Reserved 26

Copyright © 2010, Elsevier Inc. All rights Reserved 27

Copyright © 2010, Elsevier Inc. All rights Reserved 28

Copyright © 2010, Elsevier Inc. All rights Reserved 29

Copyright © 2010, Elsevier Inc. All rights Reserved 30

1. Partition problem solution into tasks.

Copyright © 2010, Elsevier Inc. All rights Reserved 31

Copyright © 2010, Elsevier Inc. All rights Reserved 32

Copyright © 2010, Elsevier Inc. All rights Reserved 33

Copyright © 2010, Elsevier Inc. All rights Reserved 34

Copyright © 2010, Elsevier Inc. All rights Reserved 35

Copyright © 2010, Elsevier Inc. All rights Reserved 36

Each process just

Copyright © 2010, Elsevier Inc. All rights Reserved 37

Copyright © 2010, Elsevier Inc. All rights Reserved 38

Copyright © 2010, Elsevier Inc. All rights Reserved 39

Copyright © 2010, Elsevier Inc. All rights Reserved 40

Copyright © 2010, Elsevier Inc. All rights Reserved 41

Copyright © 2010, Elsevier Inc. All rights Reserved 42

1. In the first phase:

2. (a) Process 4 sends its newest value to process 0.

Copyright © 2010, Elsevier Inc. All rights Reserved 43

 All the processes in the communicator must call

 For example, a program that attempts to match a

 The arguments passed by each process to an

 For example, if one process passes in 0 as the

Copyright © 2010, Elsevier Inc. All rights Reserved 49

 The output_data_p argument is only used

 However, all of the processes still need to

Copyright © 2010, Elsevier Inc. All rights Reserved 50

 Point-to-point communications are matched on