Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Blocking Message
Passing Operations
5.1
Lecture 5
Programming Using the
Message- Passing Paradigm I
Principles of Message-Passing Programming
IKC-MH.57 Introduction to High Performance and Parallel
Computing at November 10, 2023
Dr. Cem Özdo
˘
gan
Engineering Sciences D epartment
˙
Izmir Kâtip Çelebi University
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.2
Contents
1 Prog ramming Using th e Message-Passing Paradigm
Principles of Message-Passing Programming
Structure of Message-Passing Programs
The Building Blocks: Send and Receive Operations
Blocking Message Passing Operations
Non-Blocking Message Passing Operations
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.3
Principles of Message-Passing Programming I
Set of Primitives: Allows processes to communicate with each
other.
•
A message passing arc hitecture uses a set of primitives
that allows process es to communicate with each other.
•
i.e., send, receive, broadcast, and barrier.
There are two key attributes that characterize the message
-passing programming paradig m.
1 the first is that it assumes a partitioned address space,
2 the second is that it s upports only explicit parallelization.
•
Each data element must b elong to one of the partitions
of the space;
•
hence, data must be explicitly partit ioned and placed.
•
Adds complexity, encourages data locality.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.4
Principles of Message-Passing Programming II
•
All interactions (read-only or read/write) require
cooperation of two processes:
1 the process that has the data,
2 the process that wants to access the data.
•
Primary advantage of explicit two-way interactions is that
the programmer is fully aware of all the costs of non-local
interactions
•
The programmer is responsible for analyzing the
underlying serial algorithm/application.
•
As a result, programming using the message-passing
paradigm tends to be hard and intellectually demanding.
•
However, on the other hand, properly written
message-passing programs can often achieve very high
performance and scale to a very large number of
processes.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.5
Structure of Message-Passing Programs I
•
Message-passing programs are often written using the
asynchronous or loosely synchronous paradigms.
•
In the asynchronous paradigm, all concurrent tasks
execute asynchronously.
•
However, such programs can be harder and can have
non-deterministi c b ehavior
due to race conditions.
•
Loosely synchronous pr ograms are a good compromise
between two extremes.
•
In such programs, tasks or subsets of tasks synchronize to
perform interactions
.
•
However, between these interactions, t asks execute
completely a synchronously.
•
Most message-passing programs ar e wr itten using the
single program multiple data (SPMD).
•
SPMD programs can be loosely synchronous or
completely asynchronous.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.6
The Building Blocks: Send and Receive Operation s I
•
Since interactions are accomplished by sending and
receiving messages, the basic operations in the
message-passing programming paradigm are send and
receive.
•
In their simplest form, the prototypes of these operations
are defined as follows:
send(void
*
sendbuf, int nelems, int dest)
receive(void
*
recvbuf, int nelems, int source)
• sendbuf points to a buffer that stores the data to be sent
,
• recvbuf points to a buffer that stores t he data to be
received,
• nelems is the number of data units to be sent and
received,.
• dest is the identifier of the process that receives th e data,.
• source i s the identifier of the process that sends the data.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.7
The Building Blocks: Send and Receive Operation s II
1 P0 P1
2
3 a = 100; receive(&a, 1, 0)
4 send(&a, 1, 1); printf("%d\n", a);
5 a=0;
• Process P
0
sends a message to process P
1
which
receives and prints the message.
• The important thing to note is that process P
0
changes
the value of a to 0 immediately following the send.
• The semantics of the send operation require that the
value received by process P
1
must be 100 (not 0).
• That is, the value of a at the time of the send operation
must be the value that is received by pr ocess P
1
.
• It may seem that it is quite straightforward to ensure the
semantics of the send and receive operations.
• However, based on how the send and receive operations
are implemented this may not be the case.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.8
Blocking Message Passin g Operations I
•
As a result, if the send operation programs the
communication hardware and returns before the
communication operation has been accomplished,
process P
1
might receive
the value 0 in a instead of 100!
•
A simple s olution to the problem presented in the code
fragment above is for the send operation to return only
when it is semantically safe to do so.
•
Note that this is not the same as saying that the send
operation returns only after the receiver has received the
data.
•
It simply means that the sending operation blocks until it
can guarantee that the semantics will not be violated on
return irrespective of what happens in the program
subsequently.
•
There are two mechanisms by which this can be achieved.
1 Blocking Non-Buffered Send/ R eceive
2 Blocking Buffered Send/Receive
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.9
Blocking Message Passin g Operations II
1 Blocking Non-Buffered Send/Receive
•
The send operation does not return until the matching
receive has been encountered at the rec eiving process.
•
When this happens, the message is sent and the send
operation returns upon completion of the communication
operation.
•
Typically, this process involves a handshake between the
sending and receiving processes (see Figure).
Figure: Handshake for a blocking non-buffered send/receive
operation.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.10
Blocking Message Passin g Operations III
• The sending process sends a request to c ommunicate to
the receiving process.
• When the receiving process encounters the target
receive, it responds to the request.
• The sending process upon receiving this response
initiates a transfer operation.
• Since there are no buffers used at either sending or
receiving ends, this is also referred to as a non-buffered
blocking operation.
•
Idling Overheads in Blocking Non-Buffered Operations: It
is clear from the figure that a blocking non-buffered
protocol is s uitable when the send and receive are posted
at roughly the same time (see Figure(b)).
•
However, in an asynchronous environment, this may be
impossible to predict.
•
This idling overhead is one of the major drawbacks of this
protocol.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.11
Blocking Message Passin g Operations IV
•
Deadlocks in Blocking Non-Buffered Operations: Consider
the following simple exchange of messages that can lead
to a deadlock:
1 P0 P1
2
3 send(&a, 1, 1); send(&a, 1, 0);
4 receive(&b, 1, 1); receive(&b, 1, 0);
•
The code fragment makes the values of a available to both
processes P
0
and P
1
.
•
However, if the send and r eceive operations are
implemented using a blocking non-buffered protocol
,
• the send at P
0
waits
for the matching receive at P
1
• whereas the send at process P
1
waits
for the
corresponding receive at P
0
,
• resulting in an infinite wait.
•
Deadlocks are ver y easy in blocking protoc ols and care
must be taken to break cyclic waits.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.12
Blocking Message Passin g Operations V
2 Blocking Buffered Send/Receive
•
A simple s olution to the idling and deadlocking problems
outlined above is to rely on buffers at the sending and
receiving ends.
Figure: Blocking buffered transfer protocols: Left: in the
presence of communication hardware with buffers at send and
receive ends; and Right: in the absence of communication
hardware, sender interrupts receiver a nd deposits data in buffer
at receiver end.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.13
Blocking Message Passin g Operations VI
•
On a send operation, the sender simply copies the data
into the designated buffer and returns after the copy
operation has been completed.
•
The sender process can now continue with the program
knowing that any changes to the data will not impact
program semantics.
•
Note that at the receiving end, the data cannot be stored
directly at the target location since this would violate
program semantics.
•
Instead, the data is copied into a buffer at the receiver as
well.
•
When the receiving process encounters a receive
operation, it checks to see if the message is available in its
receive buffer. If so, the data is copied into the tar get
location.
•
In general, if the parallel program is highly synchronous,
non-buffered sends may perform better than buffer ed
sends.
•
However, generally, this is not the case and buffer ed sends
are desirable unless buffer capacity becomes an issue.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.14
Blocking Message Passin g Operations VII
•
Deadlocks in Buffered Send and Receive Operations:
•
While buffering relieves many of the deadlock situations, it
is still possible to write code that deadlocks.
•
This is due to the fact that as in the non-buffered case,
receive calls are always blocking (to ensure semantic
consistency).
•
Thus, a simple code fragment such as the following
deadlocks since both processes wait to receive data but
nobody sends it.
1 P0 P1
2
3 receive(&a, 1, 1); receive(&a, 1, 0);
4 send(&b, 1, 1); send(&b, 1, 0);
•
Once again, suc h circular waits have to be broken.
•
However, deadlocks are caused only by waits on receive
operations in this case.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.15
Non-Blocking Message Passing Operations I
•
In blocking protocols, the overhead of guaranteeing
semantic correctness was paid in the form of idling
(non-buffered) or buffer management (buffered).
•
It is possible to require the programmer
•
to ensure semantic correctness,
•
to provide a fast send/receive operation that incu rs little
overhead.
•
This class of non-blocking protocols returns from the
send or receive operation before it is semantically safe to
do so.
•
Consequently, the user must be careful not to alter data
that may be potentially participating in communication.
•
Non-blocking operations are generally accompanied by a
check-status operation,
•
which indicates whether the semantics of a pr eviously
initiated transfer may be violated or not.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.16
Non-Blocking Message Passing Operations II
•
Upon return from a non-blocking operation, the process is
free to perform any computation that does not depend
upon the completion of the operation.
•
Later in the program, the process can check whether or
not the non-blocking operation has completed,
•
and, if necessary, wait for its completion.
•
Non-blocking operations can be buffered or non-buffered.
•
In the non-buffered case, a process wishing to send data
to another simply posts a pending message and returns to
the user program.
•
The program can then do other useful work.
•
At some point in the future, when the corresponding
receive is posted, the c ommunication operation is initiated.
•
When this operation is completed, the check-status
operation indicates that it is safe to touch this data.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.17
Non-Blocking Message Passing Operations III
Figure: Non-blocking non-buffered send and receive operations Left:
in absence of communication hardware; Right: in presence of
communication hardware.
•
This transfer is indicated in Figure(Left)
•
Comparing Figures (Left) and (a), it is easy to see that the
idling time when the process is waiting for the
corresponding receive in a blocking operation can now be
utilized for computation.
•
This removes the major bottleneck associated with the
former at the expense of some program res tructuring.
Programming Using the
Message-Passing
Paradigm I
Dr. Cem Özdo
˘
gan
LOGIK
Programming Using
the Message-Passing
Paradigm
Principles of
Message-Passing
Programming
Structure of
Message-Passing
Programs
The Building Blocks: Send
and Receive Operations
Blocking Message Passing
Operations
Non-Block ing Message
Passing Operations
5.18
Non-Blocking Message Passing Operations IV
•
Blocking operations facilitate safe and easier
programming.
•
Non-blocking operations are useful for performance
optimization by masking communication overhead.
•
One must, however, be careful using non-blocking
protocols since errors can result from unsafe access to
data that is in the proc ess of being communic ated.
