Image

Message Passing Interface (MPI)

Parallel Programming Methods (Algorithms, MPI) and Linux Clustering
User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Message Passing Interface (MPI)

Postby Shahram » Sun Feb 05, 2017 4:39 pm

First steps in MPI programming
By: Shahram Talei


Contents:
Part one: Basics
1-1. Introduction
1.2 - Definitions
1.3 First code
Part two : Simple parallel algorithms
2.1 - Point to point communication
2.2- Collective communication

Part Three: Appendixes

- Codes are in c

--------------------------------------------------------------
1.1- Introduction

According to Wikipedia:
Message Passing Interface (MPI) is a standardized and portable message-passing system designed by a group of researchers from academia and industry to function on a wide variety of parallel computing architectures. The standard defines the syntax and semantics of a core of library routines useful to a wide range of users writing portable message-passing programs in C, C++, and Fortran. There are several well-tested and efficient implementations of MPI, many of which are open-source or in the public domain. These fostered the development of a parallel software industry, and encouraged development of portable and scalable large-scale parallel applications.


MPI (Message Passing Interface) is a portable library (not a language) to manage parallel algorithms running on clusters in higher level from direct hardware programming.
Both point-to-point and collective communication are supported in MPI.
MPI programs are regularly run on shared memory computers, and both MPICH and Open MPI can use shared memory for message transfer if it is available. MPI belongs in layers 5 and higher of the OSI Reference Model, implementations may cover most layers, with sockets and Transmission Control Protocol (TCP) used in the transport layer.
MPI-3.0 is a major update to the MPI standard. The updates include the extension of collective operations to include nonblocking versions, extensions to the one-sided operations, and a new Fortran 2008 binding. In addition, the deprecated C++ bindings have been removed, as well as many of the deprecated routines and MPI objects (such as the MPI_UB datatype).


1.2 Definitions

Host cluster is called "world". every world contains processors which are accessible by a unique number called "rank". If we have n processors in our world then they will be distinguished by integer number between 0 -> n-1.
We are able to distribute different tasks (usually called process) between processors in two ways: 1- point to point by using send and receive and 2- collective communication using reduce, bcast, ... .

To start using MPI 6 functions are enough:

MPI_INIT - Initialize MPI
MPI_COMM_SIZE - finds size of our world ( number of processors)
MPI_COMM_RANK - finds rank of processor (which processor are we in)
MPI_SEND - send a message to other processor
MPI_RECV - receive a message to other processor
MPI_FINALIZE - terminate MPI

I should note that this is for point to point communication. For collective communication other functions are required.
MPI has a lot of functions and it is really big library but we can write our code with minimum number of routines. To see complete list of functions with examples visit this link: https://www.mpich.org/static/docs/v3.2/www3/

1.3 First code - Display number of processors and current processor

Lets go to code without hesitate. This is very simple example.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

int main()
{
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   
   printf("Number of processors are %d and processor %d is at your service now\n", world_size,world_rank);
   MPI_Finalize();
   
}


Lets save this file as "Start.c"
To compile it with mpi you should have mpicc and use Makefile as below to compile it:

Code: Select all

EXECS=Start
MPICC?=mpicc
all:${EXECS}

Start:Start.c
   ${MPICC} -o Start Start.c
   
Clean:
   rm -f ${EXECS}


And save it with name "Makefile" in the same folder.

If you don't have mpicc, you can install it with this command in Debian for example:

Code: Select all

#apt-get mpich


Now browse to that folder in terminal and run:

Code: Select all

make


And if you don't have error, new executive file named "Start" will be added to that folder.
Now if you have MPI on your system you can run your program by using:

Code: Select all

mpirun -np 2 ./Start

2 is number of processors.
It is instructive to look at output. You may decide to have more control on distribution of your problem between processors.


Part two : Samples

2.1 Point to point sample - walk in processors
Lets go directly to first point to point code. This is just a simple code to show you how to walk in processors:

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

int main()
{
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   
   if(world_size>1)
      {
         int i;
         for(i=0;i<world_size;i++)
            {
               if(world_rank==i)
               {
                  printf("I am processor %d\n", world_rank);
               }
            }
         MPI_Finalize();
   }
   else
   {
      printf("Not enough Ps");
      MPI_Abort(MPI_COMM_WORLD,1);
   }
   
}


Compile and run as before.

2.2 Collective communication sample
Now let me show an example of collective communication. MPI runs your program in all processors by default. In this example we want to find an approximate value for mathematical pi by integrating 4/(1+x^2) between 0 and 1. because our program is distributed in all processors we need to collect them. One way is reduce function. reduce acts on all values by operation you want. This is a beautiful example which shows you how MPI works, Infact all processors watch code and you ask them to do their job !

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

int main()
{
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   int n,i,rc;
   double mypi,h,sum,x,a,pi;
   do
   {
      if(world_rank==0)
      {
         printf("Enter number of intervals:");
         scanf("%d",&n);
      }
      MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
      h=1/(double)n;
      sum=0;
      for(i=world_rank+1;i<=n;i+=world_size)
      {
         x=h*((double)i-0.5);
         sum+=(4/(1+x*x));
      }
      mypi=sum*h;
      MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);
      if(world_rank==0)
      {
         printf("pi is=%.16f\n",pi);
      }
   }while(n!=0);
   MPI_Finalize();
   
}


Compile and run as before.


Part Three: Appendixes
A-Complete list of MPI Routines (functions):
https://www.mpich.org/static/docs/v3.2/www3/


B- References and Further readings:
MPI 3 Manual : http://mpi-forum.org/docs/mpi-3.1/mpi31-report.pdf
William Gropp, Ewing Lusk, Anthony Skjellum,Using MPI: Portable Parallel Programming with the Message-Passing Interface,
MPI Forum: https://mpi-forum.org/
--------------
http://people.sc.fsu.edu/~jburkardt/c_src/mpi/mpi.html
http://www.mcs.anl.gov/research/projects/mpi/tutorial/gropp/talk.html
https://en.wikipedia.org/wiki/Message_Passing_Interface



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Fri Feb 10, 2017 2:29 pm

Lectures on MPI.

High-Performance Computing - Episode 1 - Introducing MPI

https://www.youtube.com/watch?v=kHV6wmG35po


Introduction to MPI Programming, by Hristo Iliev:

part 1

https://www.youtube.com/watch?v=LBgx_S5ougk
part 2

https://www.youtube.com/watch?v=CliFXC3kG90



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Fri Feb 10, 2017 3:20 pm

For fast and clear introduction to MPI I found this site very useful.
http://mpitutorial.com/
Generally we should know that MPI helps us to communicate with different processors and provides primitive tools to check the status and we should use these tool in an appropriate way (well defined parallelized algorithm) to distribute job between different processors. The second part is our parallelization algorithm which is independent of MPI or other tools.

First section of tutorial is about sending and receiving information between processors:
http://mpitutorial.com/tutorials/mpi-send-and-receive/

Second part is about making dynamic send and receive (put control by checking status):
http://mpitutorial.com/tutorials/dynamic-receiving-with-mpi-probe-and-mpi-status/

And third part is about a sample problem which shows us how we can put all together to have an efficient parallel solution for a problem(in this case our problem is random walk, my favorite problem !):
http://mpitutorial.com/tutorials/point-to-point-communication-application-random-walk/



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Sun Feb 26, 2017 8:38 pm

Another example on point to point comunication in MPI:

This is a code which sends data from one processor to another processor. It Is first example described in this address but I made it simpler and shorter. It works only with send and receive command in mpi:
http://mpitutorial.com/tutorials/mpi-send-and-receive/

C program for MPI send and receive ( I saved as SR.c)

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

int main()
{
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   
   if(world_size>=2)
   {
   int number;
   if(world_rank==0)
   {
      number=-1;
      MPI_Send(&number,1, MPI_INT, 1, 0,MPI_COMM_WORLD);
   }
   else if (world_rank==1)
   {
      MPI_Recv(&number,1,MPI_INT,0,0,MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      printf("Process 1 recieved number %d from process 0\n", number );
   }
   MPI_Finalize();
   }
   else
   {
      printf("You only have one processor");
      MPI_Abort(MPI_COMM_WORLD,1);
   }
   
}


To compile it create a file called Makefile and put these codes inside it:

Code: Select all

EXECS=SR
MPICC?=mpicc
all:${EXECS}

SR:SR.c
   ${MPICC} -o SR SR.c
   
Clean:
   rm -f ${EXECS}


Then open that directory in terminal and compile and run it:

Code: Select all

$make
$mpirun -np 2 ./SR



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Sun Feb 26, 2017 8:44 pm

Here is ping pong example in that page which I simplified it. My version is shorter and you can run it directly without extra script. This example is called ping pong between processors and it is described very nicely in this address:
http://mpitutorial.com/tutorials/mpi-send-and-receive/

This is content of file called PP.c :

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

int main()
{
   const int END=10;
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   
   if(world_size==2)
   {
      int count=0;
      int partner_rank=(world_rank+1)%2;
      while(count<END)
      {
         if(world_rank==count%2)
         {
            count++;
            MPI_Send(&count,1, MPI_INT, partner_rank, 0,MPI_COMM_WORLD);
            printf("%d sent count %d to %d\n", world_rank,count,partner_rank);
         }
         else
         {
            MPI_Recv(&count,1,MPI_INT,partner_rank,0,MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            printf("%d received count %d from %d\n", world_rank,count,partner_rank);
         }
         
      }
   }
   else
   {
      printf("You only have one processor");
      MPI_Abort(MPI_COMM_WORLD,1);
   }
   MPI_Finalize();
   
}



and content of make file ( is called Makefile):

Code: Select all

EXECS=PP
MPICC?=mpicc
all:${EXECS}

PP:PP.c
   ${MPICC} -o PP PP.c
   
Clean:
   rm -f ${EXECS}



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Thu Mar 02, 2017 11:47 pm

How to transfer one structure between processors - part one
This is the simplest case of a structure with same type. If we have different types inside structure ( which is often) we should use vectors to communicate. However here is a very simple code to show how to do uniform structure transformation.
This example is written for 2 processors to make it easy to test by home computers it is obvious that its is not applicable example.
Structure is field with uniform distribution of numbers.

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>

struct Point
{
   int x;
   int y;
   int z;
   int m;
}p[100],cm;

int main()
{
   
   MPI_Init(NULL,NULL);
   
   int world_rank;
   MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
   int world_size;
   MPI_Comm_size(MPI_COMM_WORLD, &world_size);
   
   const int count=100;
   int i;
   cm.x=0;
   cm.y=0;
   cm.z=0;
   cm.m=0;
   //struct Point p[count],cm;
   
   if(world_size>=2)
   {
   int number;
   if(world_rank==0)
   {
      //give primary values to points;
      for(i=0;i<count;i++)
      {
         p[i].x=i;
         p[i].y=i;
         p[i].z=i;
         p[i].m=1;
      }
      for( i=0;i<count;i++)
      {
         cm.m+=p[i].m;
         cm.x+=p[i].x;
         cm.y+=p[i].y;
         cm.z+=p[i].z;
      }
      MPI_Send(&cm,4, MPI_INT, 1, 0,MPI_COMM_WORLD);
      /*
       * MPI_Send(
    void* data,
    int count,
    MPI_Datatype datatype,
    int destination,
    int tag,
    MPI_Comm communicator)

       * */
   }
   else if (world_rank==1)
   {
      MPI_Recv(&cm,4,MPI_INT,0,0,MPI_COMM_WORLD, MPI_STATUS_IGNORE);
      /*
       * MPI_Recv(
    void* data,
    int count,
    MPI_Datatype datatype,
    int source,
    int tag,
    MPI_Comm communicator,
    MPI_Status* status)

       * */
      printf("Process 1 recieved cm from process 0\n" );
      printf("Center of Mass: x=%d, y=%d, z=%d\n",cm.x/cm.m,cm.y/cm.m,cm.z/cm.m);
   }
   MPI_Finalize();
   }
   else
   {
      printf("You only have one processor");
      MPI_Abort(MPI_COMM_WORLD,1);
   }
   
}



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Tue Mar 14, 2017 11:31 pm

Nice tutorial by William Gropp Author of using mpi book which is available in this link but I uploaded in this post to make it easier to download.

gropp-mpi-tutorial.pdf
(632.04 KiB) Downloaded 31 times


and this is another nice summary:
http://wgropp.cs.illinois.edu/bib/talks/tdata/2004/mpi-half-day-public.pdf



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Fri Mar 24, 2017 10:56 pm

A User's Guide To MPI
by: Peter S. Pacheco
mpi.guide.pdf
(349.49 KiB) Downloaded 46 times



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Fri Apr 07, 2017 11:56 pm

Communicators and virtual topologies:

In intermediate level of MPI programming in order to solve real problems we need to distribute our code in all processors with more control.
In this case we can use communicators in simple cases. In fact communicators are group of processors. You can take number of processors and build a group with them.
In the next level it is important to pay attention to topology of your cluster and to know how processors are connected together. But to help you design proper solutions, there are designed virtual topologies in MPi. You need to know how to decompose your problem on these topologies.

An important virtual topology is Cartesian topology. This is simply a decomposition in natural coordinate directions. You are familiar with one dimensional decomposition from previous examples. We can have 2 or more dimensional decompositions. It is similar to putting elements in matrix. You can refer to processors by knowing row and column numbers in 2 dimensions.


Image
https://www.physics.drexel.edu/~valliere/PHYS405/Domain_Decomposition/domain.html

You should define connection between elements. In this topology every processor is connected to its neighbors.
you can make it periodic by connecting end cells together.
Sample code will be similar to this:

General form:

Code: Select all

int MPI_Cart_create(
  MPI_Comm comm_old,
  int ndims,
  int *dims,
  int *periods,
  int reorder,
  MPI_Comm *comm_cart
);


An example:

Code: Select all

dim[0]=4; dim[1]=3;
    period[0]=1; period[1]=0;
    reorder=1;
    MPI_Cart_create(MPI_COMM_WORLD, 2, dim, period, reorder, &comm);


This is a good introduction for virtual topology in MPI:
http://perso.ens-lyon.fr/mehdi.diouri/ressources/Distributed_Systems/TD3/mpi_topologies.pdf
Attachments
domain.GIF
(6.3 KiB) Downloaded 529 times



User avatar
Shahram
Posts: 276
Joined: Sun Feb 05, 2017 8:31 am

Re: Message Passing Interface (MPI)

Postby Shahram » Sun Apr 09, 2017 11:16 pm

Sometimes we need to find time interval in MPI to find out efficiency of our method. Simplest way is to use "MPI_Wtime()" function. This function returns time. General form is as below:

Code: Select all

double t1, t2;
ti = MPI_Wtime();
...
//your codes
...
tf = MPI_Wtime();
printf( "Elapsed time is %f\n", tf - ti );




Return to “Parallel Programming and Clusters”

Who is online

Users browsing this forum: No registered users and 1 guest