Message Passing Architecture

Message passing systems provide alternative methods for communication and

movement of data among multiprocessors (compared to shared memory
multiprocessor systems).
A message passing system typically combines local memory and the processor at
each node of the interconnection network. There is no global memory so it is
necessary to move data from one local memory to another by means of message
passing. This is typically done by send/receive pairs of commands, which must be
written into the application software by a programmer.
Two important factors must be considered in designing message passing
interconnection networks: link bandwidth and the network latency. The link
bandwidth is defined as the number of bits that can be transmitted per unit of time
(bits/s). Network latency is defined as the time to complete a message transfer
through the network.
In executing a given application program, the program is divided into concurrent
processes; each is executed on a separate processor. If the number of processes is
larger than the number of processors, then more than one process will have to be
executed on a processor in a time-shared fashion.

Processes running on a given processor use what is called internal channels to

exchange messages among themselves. Processes running on different
processors use the external channels to exchange messages. Data exchanged
among processors cannot be shared; it is rather copied (using send/receive
messages).
An example message passing system consisting of four processes. In this figure, a
horizontal line represents the execution of each process and lines extended among
processes represent messages exchanged among these processes.
A message is defined as a logical unit for internode communication; it is
considered as a collection of related information that travels together as
an entity. A message can be an instruction, data, synchronization, or interrupt
signals. A message passing system interacts with the outside world by receiving
input message(s) and/or outputting message(s).
Process Granularity:
The size of a process in a message passing system can be described by a
parameter called process granularity. This is defined as follows:
Three types of granularity can be distinguished. These are:
1. Coarse granularity: Each process holds a large number of sequential
instructions and takes a substantial amount of time to execute.
2. Medium granularity: Since the process communication overhead increases as
the granularity decreases, medium granularity describes a middle ground
where communication overhead is reduced.
3. Fine granularity: Each process contains a few sequential instructions (as few as
just one instruction).
Message passing multiprocessors uses mostly medium or coarse granularity.
Generic Model of a Message-passing Multicomputer
Generic Node Architecture

External
channel
Node
Fat-Node
Node -powerful processor
-large memory
-many chips
Node-processor -costly/node
-moderate parallelism
Processor +
Local memory + ....

Thin-Node
Internal
channel(s) -small processor
Router
External -small memory
Communication channel -one-few chips
-cheap/node
Processor + -high parallelism
External Switch unit+ ....
channel

External
channel
Generic Organization Model

Switching network
P+M P+M
CP CP

S S P+M P+M P+M

CP CP CP

(b) Centralized
(a) Decentralized
Message Passing Properties

• Complete computer as building block, including I/O

• Programming model: directly access only private address space (local
memory)
• Communication via explicit messages (send/receive)
• Communication integrated at I/O level, not memory system, so no
special hardware
• Resembles a network of workstations (which can actually be used as
multiprocessor systems)
Message-Passing Libraries

• Message-passing libraries directly implement the message-passing parallel

programming model
• The basic paradigm of message passing is the same in different libraries (PARMACS,
Chameleon, CHIMP, PICL, Zipcode, p4, PVM, MPI, etc)
• The libraries just differ in details of implementation

• The most popular libraries are

• MPI (Message-Passing Interface)

• PVM (Parallel Virtual Machine)

• Absolute majority of existing message-passing code is written using one of the libraries
• We outline MPI
• Standardised in 1995 as MPI 1.1
• Widely implemented in compliance with the standard
• all hardware vendors offer MPI
• Free high-quality MPI implementations (LAM MPI, MPICH)
• Supports parallel programming in C and Fortran on all MPP
architectures
• including Unix and Windows NT platforms

16
Message-Passing Libraries

• MPI 2.0 is a set of extension to MPI 1.1

released in 1997
• Fortran 90 and C++ bindings, parallel I/O, one-
sided communications, etc
• A typical MPI library fully implements MPI 1.1
and optionally supports some features of MPI 2.0
• We use the C interface to MPI 1.1 to present
MPI

Parallel Computing 17
MPI
• An MPI program
• A fixed number of processes
• Executing their own code in their own address space
• The codes need not be identical
• Communicating via calls to MPI communication primitives
• Does not specify
• The number of processes
• The allocation of the processes to physical processors
• Such mechanisms are external to the MPI program
• must be provided by particular MPI implementations
• Uses calls to MPI inquiring operations to determine their
total number and identify themselves in the program

Parallel Computing 18
MPI (ctd)
• Two types of communication operation
• Point-to-point
• Involves two processes, one of which sends a message and other
receives the message
• Collective
• Involves a group of processes
• barrier synchronisation, broadcast, etc

Parallel Computing 19
MPI (ctd)
• Process group
• An ordered collection of processes, each with a rank
• Defines the scope of collective communication operations
• No unnecessarily synchronizing uninvolved processes
• Defines a scope for process names in point-to-point
communication operations
• Participating processes are specified by their rank in the same process
group
• Cannot be build from scratch
• Only from other, previously defined groups
• By subsetting and supersetting existing groups
• The base group of all processes available after MPI is initialised
MPI (ctd)
• Communicators
• Mechanism to safely separate messages
• Which don’t have to be logically mixed, even when the messages are transferred
between processes of the same group
• A separate communication layer associated with a group of processes
• There may be several communicators associated with the same group, providing
non-intersecting communication layers
• Communication operations explicitly specify the communicator
• Messages transmitted over different communicators cannot be mixed (a message
sent through a communicator is never received by a process not communicating
over the communicator)
MPI (ctd)
• Communicators (ctd)
• Technically, a communicator is implemented as
follows
• A unique tag is generated at runtime
• shared by all processes of the group, with which the
communicator is associated
• attached to all messages sent through the communicator
• used by the processes to filter incoming messages
• Communicators make MPI suitable for writing parallel
libraries
MPI (ctd)
• MPI vs PVM
• PVM can’t be used for implementation of parallel
libraries
• No means to have separate safe communication layers
• All communication attributes, which could be used to
separate messages, such as groups and tags, are user-defined
• The attributes do not have to be unique at runtime
• Especially if different modules of the program are written
by different programmers
MPI (ctd)
• Example 1. The pseudo-code of a PVM application
extern Proc();
if(my process ID is A)
Send message M with tag T to process B
Proc();
if(my process ID is B)
Receive a message with tag T from process A
• Does not guarantee that message M will not be intercepted inside the library
procedure Proc
• In this procedure, process A may send a message to process B
• The programmer, who coded this procedure, could attach tag T to the message

Parallel Computing 24
MPI (ctd)
• Example 2. MPI solves the problem as follows
extern Proc();
Create communicator C for a group including
processes A and B
if(my process ID is A)
Send message M to process B through
communicator C
Proc();
if(my process ID is B)
Receive a message from process A through
communicator C
• A unique tag attached to any message sent over the communicator C
prevents the interception of the message inside the procedure Proc
Groups and Communicators
• A group is an ordered set of processes
• Each process in a group is associated with an integer rank
• Ranks are contiguous and start from zero
• Groups are represented by opaque group objects of the type MPI_Group
• hence cannot be directly transferred from one process to another
• A context is a unique, system-generated tag
• That differentiates messages
• The MPI system manages this differentiation process
Groups and Communicators (ctd)
• Communicator
• Brings together the concepts of group and context
• Used in communication operations to determine the scope and
the “communication universe” in which an operation is to
operate
• Contains
• an instance of a group
• a context for point-to-point communication
• a context for collective communication
• Represented by opaque communicator objects of the type
MPI_Comm
Groups and Communicators (ctd)
• We described intra-communicators
• This type of communicators is used
• for point-to-point communication between processes of the same group
• for collective communication
• MPI also introduces inter-communicators
• Used specifically for point-to-point communication between processes of
different groups
• We do not consider inter-communicators
Groups and Communicators (ctd)
• An initial pre-defined communicator MPI_COMM_WORLD
• A communicator of all processes making up the MPI program
• Has the same value in all processes
• The group associated with MPI_COMM_WORLD
• The base group, upon which all other groups are defined
• Does not appear as a pre-defined constant
• Can be accessed using the function
int MPI_Comm_group(MPI_Comm comm, MPI_Group *group)
Groups and Communicators (ctd)
• Other group constructors
• Explicitly list the processes of an existing group, which make up a new
group, or
• Do set-like binary operations on existing groups to construct a new group
• Union
• Intersection
• Difference