PARALLEL PROGRAMMING PARADIGMS

In this blog we shall provide a soft introduction into parallel programming using MPI framework. Beginning with concepts of a parallel machine and models of parallel computation, we will introduce MPI basics in section 2. Section 3 will contain a small hands on tutorial and a summary shall be provided in section 5 along with what to expect in next post.

Introduction

Von Nuemann Model: Single Machine Model consisting of a CPU connected to memory. The CPU executes the program specifying sequqence of read write operations of memmory.
Multicomputer Model : Several Von Neumann machines linked via interconnection network. The individual machines execute their own program and uses local memmory, but also exchange messages through network.
Role of message passing:

1. Communicate with other processes.
2. Read/Write remote memmory.

Examples of Parallel Computing Architecture:

1. Distributed-memmory MIMD: The computer memmory is not placed at a central location but rather distributed amongst several processors. Each of these can execute a separate stream of instructions using local data.
   Difference wrt multicomputer model: message sending cost b/w two nodes may depend on location and traffic.
2. Shared-memmory MIMD: Several processors share a centrally placed memmory through a bus or a hierarchy of them. Usually each processor is provided with a cache to temporarily store copies of frequenty used items, in order to reduce the calls to main memmory.
   This architecture is more close to multicomputers since shared memmory allows an easier paradigm for message passing.
3. SIMP: Several processors execute single instruction stream on different peice of data. This is a simple approach but limited to a very narrow range of problems having a high degree of regularity.
4. MPMD: This is an acronym for Multiple Program Multiple Data and differs from SIMP in respect that each processor executes different program.

The MPI Programming Model

The Message Passing Interface (MPI) is based on MPMD model and views a computation as comprising of one or more proesses that communicate via library routines. These processes are usually created at the initialization and may communicage one or more of following modes:

1. Point-to-Point Communication.
2. Collective Communication.

In both these modes we use a mechanism called communicator that for defining modules encapsulating internal communication standards.

The Basic Functions: Getting Started

Here we introduce six beginner's routines and few points to explain the basic functionality. Following function is called before any other MPI command in order to intialize the environment.

MPI_INIT Role: Start an MPI computation. Prototype: int MPI_Init( int *argc, char ***argv ) Prameters: Two parameters argc: Pointer to the number of arguments argv: Pointer to the argument vector

During MPI_Init, all of MPI’s global and internal variables are constructed. Like construction of a communicator enveloping all of the processes spawned, assignment of unique rank to each.

After we are done with all the MPI stuff, MPI_Finalize is used to clean up the MPI environment. No more MPI calls can be made after this one.

MPI_FINALIZE Role: Finish/Terminate an MPI computation. Prototype: int MPI_Finalize( void ) Parameters: None

Note: Both these functions must be called by a single and same thread namely the main thread. Although MPI standard is silent about what can be done before MPI_INIT and after MPI_FINALIZE but its better to do as little as possible and avoid any opeation that change external state of program like opening files, reading stdin or writing stdout.

Following function is used to find number of processes in a communicator:

MPI_COMM_SIZE Role: Give size of group asstd. to a communicator. Prototype: int MPI_Comm_Size( MPI_Comm comm, int *size) Prameters: Two parameters comm: Input communicator to be probed. size: Carrier to contain the output.

Following would return the rank of calling process in that communicator

MPI_COMM_RANK Role: Give rank of calling process in communicator. Prototype: int MPI_Comm_rank( MPI_Comm comm, int *size) Prameters: Two parameters comm: Input communicator to be probed. size: Carrier to contain the output.

Note: Both the above can be safely used by multiple threads and from within a signal handler.

Now we introduce two functions that form the backbone of message passing facility. Below is the MPI_Send function used to send a message to another process.

MPI_SEND Role: Perform a blocking send Prototype: int MPI_Send( void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm ); Prameters: Six parameters buf : add of send buffer count: num of elems in send buffer dest : rank of destination tag : message tag comm : communicator

Similarly, a message from a specific source can be received with following function:

MPI_RECV Role: Perform a blocking recieve Prototype: int MPI_Recv( void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status ); Prameters: Seven parameters, two new ones. source: rank of source. status: status of recv buffer.

Note: The parameter datatype indicates the type of data which is being sent. For example, if you wish to send an int, the datatype MPI_Int must be used. A complete list of MPI datatypes can be found here.

Note: The count argument does not indicate the length of message but rather the MAXIMUM length of it.

Note: Both these routines may be used by multiple threads but they however are not interrupt safe.

Summary

We provided a very brief introduction into the subject of parallel computing in MPI paradigm. In addition to Von-Neumann's concept of a single machine we know about various paradigms for parallel processing. We also know how to initialize MPI computing environment and how to cleanup after use. We know how to find the total number of processes in a communicator as well as how to find the rank of current process. Finally we had a look into the MPI_Send and MPI_Recv functions which are used for point-to-point communication between two processes.

We know that much better clarity about these functions can be obtained by working out the actual examples. So we will present a basic hello world program and a simple message exchange program in next post along with the explanations.