Simple look at MPI

Hi all, it's been a while since I blogged last time. I am following a course on High performance computing in the university and one module of the course was about MPI (Message Passing Interface). MPI is being used to develop parallel programs. This post will not cover depths of MPI but will just give a brief introduction. However I'll post a link at the end so that you can learn more about MPI if you are interested.

Currently MPI runs on virtually any hardware platform. While developing application on MPI, programmer is responsible for correctly identifying parallelism.

There are various implementations of MPI exists. ex: mpich, LAM/MPI. Installation of different implementations have different steps.

Installation guide for mpich.

Installation guide for LAM/MPI

After the installation, to run MPI program you need a machines file. This is just a text file with the IP addresses of the each machine you will be using.

Ex: (file name: machines)

192.168.10.10
192.168.10.11
192.168.10.12

You can use the default cc compiler to compile standard C source files. However you will have to use mpicc compiler to compile MPI source files and you will need mpirun to execute MPI executable file.

Compile:
mpicc -o program program.c

Execute:
mpirun -np x -machinefile machines program

np: number of processes.
x: is an integer number. ex: 4
machinefile: path for the machines file.

All the MPI related functions have the following format.

MPI_X
Ex:
MPI_Init
MPI_Comm_rank
MPI_Comm_size
MPI_Finalize
MPI_Send
MPI_Recv

you can find more information about above function calls in the detailed guide I have linked in the bottom.

Lets look at a simple MPI program.

	#include <stdio.h>
	#include <mpi.h>
	int main(int argc, char *argv[])
	{
	int rank, size;
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);
	printf("Hello world! I am %d of %d\n", rank, size);
	MPI_Finalize();
	return 0;
	}

view raw hello.c hosted with ❤ by GitHub

This will give following output.

 After modifying it to display the host name.

	#include <stdio.h>
	#include "mpi.h"
	int main(int argc, char **argv)
	{
	int me, nprocs, namelen;
	char processor_name[MPI_MAX_PROCESSOR_NAME];
	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &nprocs);
	MPI_Comm_rank(MPI_COMM_WORLD, &me);
	MPI_Get_processor_name(processor_name, &namelen);
	printf("Hello World! I'm process %d of %d on %s\n", me, nprocs,
	processor_name);
	MPI_Finalize();
	}

view raw helloHost.c hosted with ❤ by GitHub

Now lets look at the a Matrix Multiplication with sequential approach and with MPI approach.

Code for sequential approach. (mm.c)

	#include <stdio.h>
	#include <stdlib.h>
	#include <math.h>
	#include <sys/time.h>
	#include <assert.h>
	#define RANDLIMIT 5 /* Magnitude limit of generated randno.*/
	#define N 4 /* Matrix Size */
	#define NUMLIMIT 70.0
	float a[N][N];
	float b[N][N];
	float c[N][N];
	int main(int argc, char *argv[])
	{
	struct timeval start, stop;
	int i, j, k;
	/* generate mxs */
	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
	a[i][j] = 1 + (int)(NUMLIMIT*rand() / (RAND_MAX + 1.0));
	b[i][j] = (double)(rand() % RANDLIMIT);
	}
	#ifdef PRINT
	/* print matrices */
	printf("Matrix A:\n");
	for (i = 0; i < N; i++){
	for (j = 0; j < N; j++)
	printf("%.3f\t", a[i][j]);
	printf("\n");
	}
	printf("Matrix B:\n");
	for (i = 0; i < N; i++){
	for (j = 0; j < N; j++)
	printf("%.3f\t", b[i][j]);
	printf("\n");
	}
	printf("Matrix C:\n");
	for (i = 0; i < N; i++){
	for (j = 0; j < N; j++)
	printf("%.3f\t", c[i][j]);
	printf("\n");
	}
	#endif
	gettimeofday(&start, 0);
	for (i = 0; i < N; i++) {
	for (j = 0; j < N; j++) {
	c[i][j] = 0.0;
	for (k = 0; k < N; k++)
	c[i][j] = c[i][j] + a[i][k] * b[k][j];
	} /* end j loop */
	}
	gettimeofday(&stop, 0);
	#ifdef PRINT
	/* print results*/
	printf("Answer c:\n");
	for (i = 0; i < N; i++){
	for (j = 0; j < N; j++)
	printf("%.3f\t", c[i][j]);
	printf("\n");
	}
	#endif
	fprintf(stdout, "Time = %.6f\n\n",
	(stop.tv_sec + stop.tv_usec*1e-6) - (start.tv_sec + start.tv_usec*1e-6));
	return(0);
	}

view raw mm.c hosted with ❤ by GitHub

Code for MPI approach.

	/**********************************************************************
	* MPI-based matrix multiplication AxB=C
	*********************************************************************/
	#include <stdio.h>
	#include "mpi.h"
	#define N 4 /* number of rows and columns in matrix */
	MPI_Status status;
	double a[N][N],b[N][N],c[N][N];
	main(int argc, char **argv)
	{
	int numtasks,taskid,numworkers,source,dest,rows,offset,i,j,k;
	struct timeval start, stop;
	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &taskid);
	MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
	numworkers = numtasks-1;
	/*---------------------------- master ----------------------------*/
	if (taskid == 0) {
	for (i=0; i<N; i++) {
	for (j=0; j<N; j++) {
	a[i][j]= 1.0;
	b[i][j]= 2.0;
	}
	}
	gettimeofday(&start, 0);
	/* send matrix data to the worker tasks */
	rows = N/numworkers;
	offset = 0;
	for (dest=1; dest<=numworkers; dest++)
	{
	MPI_Send(&offset, 1, MPI_INT, dest, 1, MPI_COMM_WORLD);
	MPI_Send(&rows, 1, MPI_INT, dest, 1, MPI_COMM_WORLD);
	MPI_Send(&a[offset][0], rows*N, MPI_DOUBLE,dest,1, MPI_COMM_WORLD);
	MPI_Send(&b, N*N, MPI_DOUBLE, dest, 1, MPI_COMM_WORLD);
	offset = offset + rows;
	}
	/* wait for results from all worker tasks */
	for (i=1; i<=numworkers; i++)
	{
	source = i;
	MPI_Recv(&offset, 1, MPI_INT, source, 2, MPI_COMM_WORLD, &status);
	MPI_Recv(&rows, 1, MPI_INT, source, 2, MPI_COMM_WORLD, &status);
	MPI_Recv(&c[offset][0], rows*N, MPI_DOUBLE, source, 2, MPI_COMM_WORLD, &status);
	}
	gettimeofday(&stop, 0);
	printf("Here is the result matrix:\n");
	for (i=0; i<N; i++) {
	for (j=0; j<N; j++)
	printf("%6.2f ", c[i][j]);
	printf ("\n");
	}
	fprintf(stdout,"Time = %.6f\n\n",
	(stop.tv_sec+stop.tv_usec*1e-6)-(start.tv_sec+start.tv_usec*1e-6));
	}
	/*---------------------------- worker----------------------------*/
	if (taskid > 0) {
	source = 0;
	MPI_Recv(&offset, 1, MPI_INT, source, 1, MPI_COMM_WORLD, &status);
	MPI_Recv(&rows, 1, MPI_INT, source, 1, MPI_COMM_WORLD, &status);
	MPI_Recv(&a, rows*N, MPI_DOUBLE, source, 1, MPI_COMM_WORLD, &status);
	MPI_Recv(&b, N*N, MPI_DOUBLE, source, 1, MPI_COMM_WORLD, &status);
	/* Matrix multiplication */
	for (k=0; k<N; k++)
	for (i=0; i<rows; i++) {
	c[i][k] = 0.0;
	for (j=0; j<N; j++)
	c[i][k] = c[i][k] + a[i][j] * b[j][k];
	}
	MPI_Send(&offset, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
	MPI_Send(&rows, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
	MPI_Send(&c, rows*N, MPI_DOUBLE, 0, 2, MPI_COMM_WORLD);
	}
	MPI_Finalize();
	}

view raw mpiMult.c hosted with ❤ by GitHub

Little explanation for the MPI approach:

Plan is to split the multiplication in to several parts and distribute it among different worker nodes so they can separately compute and finally merge the results.

To distribute multiplication we can divide number of rows in the first matrix to the required amount of pieces. For example we will divide the first 4x4 matrix to two parts as follows.

With these two sets we can use entire second matrix to calculate the top and bottom parts of the final output. (Little bit of thinking will make you understand the concept)

Above code will read the number of tasks and identify number of workers. (Master will not do any work other than distributing and merging the arrays).

C uses row-major ordering to store arrays in the memory. So to send 2 rows to one of the worker machine you can use the following code.

MPI_Send(&a[offset][0], rows*N, MPI_DOUBLE,dest,1, MPI_COMM_WORLD);

Here, rows*N number of elements from array "a" starting from [offset][0] position will be transferred to the worker machine.

MPI_Send(&b, N*N, MPI_DOUBLE, dest, 1, MPI_COMM_WORLD);

Above line says that N*N elements from array "b" will be send to the worker machine.

I think above explanation is enough to understand the entire code. If you have any questions please do comment.

Above sources are given for 4x4 matrix. I tested two sources with 1000x1000 matrix and the execution times are as follows.

Note: Above MPI approach will use only worker machines to the computation. I have modified the code little bit so the Master node will also participate for  the computation. Also I have removed the code lines which are related to printing the matrices so that only the run time will be printed in the screen.

By using 4 machines for the multiplication it was able to reduce run time by approximately 20 seconds. Impressive. :)

By using compiler optimizations you might be able to reduce the run time even more. Give it a try.

Most of the codes were taken from the sample materials which were provided with the course. So the credits should go for the original authors of those sources.

Detailed guide on MPI.

Update: I compiled the sequential code with different compiler optimization levels and were able to reduce the run time to nearly 10 seconds.