A code snippet that uses MPI (over MPICH 1.4.1p1) to sort a N*N matrix using N*N processes

shearsort-inneroddevensort-mpi.cpp

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

#define NUMBER_OF_PROC_IN_DIM 4
#define NUMBERS_RANGE_MAX 31

/*
  dependencies: mpich 1.4.1p1
*/

typedef enum {
	HORIZONTAL,
	VERTICAL
} Direction;

typedef enum {
	EVEN,
	ODD
} OddEven;

typedef enum {
	COLUMN,
	ROW
} RowColumn;

void randMatrixNumbers(int* matrix, int sizeMatrix);
void printMatrix(int* matrix, int sizeMatrix, int myid);
void printMatrixSnakeSorted(int* matrix, int sizeMatrix, int myid);
void oddEvenSort(int rank, MPI_Comm comm, Direction direction, OddEven oddEven, int* matrix, MPI_Status* status);
void evenSortHorizontal(int rank, int y, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status);
void evenSortVertical(int rank, int x, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status);
void oddSortHorizontal(int rank, int y, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status);
void oddSortVertical(int rank, int x, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status);
double log_2(double n);
int toggleDirection(Direction direction);
int toggleOddEvent(OddEven oddEven);

int main(int argc,char *argv[])
{
	int  namelen, numprocs, myid, numberOfPhases;
	int buf[NUMBER_OF_PROC_IN_DIM * NUMBER_OF_PROC_IN_DIM] = {0};
    char processor_name[MPI_MAX_PROCESSOR_NAME];
	MPI_Comm comm;

    MPI_Init(&argc,&argv);
	MPI_Comm_rank(MPI_COMM_WORLD,&myid);
	MPI_Comm_size(MPI_COMM_WORLD,&numprocs);	
	MPI_Get_processor_name(processor_name,&namelen);
	MPI_Status status;

	// array with dimensions (rows, cols)
	int dim[2] = { NUMBER_OF_PROC_IN_DIM, NUMBER_OF_PROC_IN_DIM };
	int perdiods[2] = { 0, 0 };
	int reorder = 1;
	MPI_Cart_create(MPI_COMM_WORLD, 2, dim, perdiods, reorder, &comm);

	int matrixToSort[NUMBER_OF_PROC_IN_DIM*NUMBER_OF_PROC_IN_DIM] = { 0 };

	if (myid == 0){
		randMatrixNumbers(matrixToSort, NUMBER_OF_PROC_IN_DIM);
		printMatrix(matrixToSort, NUMBER_OF_PROC_IN_DIM, myid);
	}

	MPI_Bcast(matrixToSort, NUMBER_OF_PROC_IN_DIM*NUMBER_OF_PROC_IN_DIM, MPI_INT, 0, MPI_COMM_WORLD);
	
	numberOfPhases = (int)(2 * log2((double)NUMBER_OF_PROC_IN_DIM) + 1);
	Direction direction = HORIZONTAL;
	OddEven oddEven = EVEN;

	for (int i = 0; i < numberOfPhases; i++){
		for (int j = 0; j < NUMBER_OF_PROC_IN_DIM; j++){
			oddEvenSort(myid, comm, direction, oddEven, matrixToSort, &status);
			oddEven = (OddEven) toggleOddEvent(oddEven);
			MPI_Barrier(comm);
		}
		direction = (Direction) toggleDirection(direction);
	}

	// root will gather all numbers and print them sorted!
	MPI_Gather(&matrixToSort[myid], 1, MPI_INT, buf, 1, MPI_INT, 0, MPI_COMM_WORLD);
	if (myid == 0){
		printf("-------------- sorted like a snake! --------------\n\n"); fflush(stdout);
		printMatrix(buf, NUMBER_OF_PROC_IN_DIM, myid);

		// print decending
		printf("\n\n"); fflush(stdout);
		printMatrixSnakeSorted(buf, NUMBER_OF_PROC_IN_DIM, myid);
	}

    MPI_Finalize();

	return 0;
}

void oddEvenSort(int rank, MPI_Comm comm, Direction direction, OddEven oddEven, int* matrix, MPI_Status* status){
	int coords[2] = { 0 };
	int rankNeighborPrev, rankNeighborNext;

	MPI_Cart_coords(comm, rank, 2, coords);
	if (direction == HORIZONTAL){
		// ########## HORIZONTAL #############
		MPI_Cart_shift(comm, ROW, 1, &rankNeighborPrev, &rankNeighborNext);
		if (oddEven == EVEN){
			// ######### EVEN SORT - HORIZONTAL #######
			evenSortHorizontal(rank, coords[0], matrix, rankNeighborNext, rankNeighborPrev, comm, status);
		}
		else {
			// ######### ODD SORT - HORIZONTAL #######
			oddSortHorizontal(rank, coords[0], matrix, rankNeighborNext, rankNeighborPrev, comm, status);
		}
	}
	else {
		// ########## VERTICAL #############
		MPI_Cart_shift(comm, COLUMN, 1, &rankNeighborPrev, &rankNeighborNext);
		if (oddEven == EVEN){
			// ######### EVEN SORT - VERTICAL #######
			evenSortVertical(rank, coords[0], matrix, rankNeighborNext, rankNeighborPrev, comm, status);
		}
		else {
			// ######### ODD SORT - VERTICAL #######
			oddSortVertical(rank, coords[0], matrix, rankNeighborNext, rankNeighborPrev, comm, status);
		}
	}
}

void evenSortHorizontal(int rank, int y, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status){
	if (rank % 2 == 1 || (rank % 2 == 0 && rankNeighborNext != MPI_PROC_NULL)){ // check if the next procces is not null (for N*N matrix with odd N)
		int received, sendBack;
		if (rank % 2 == 0){
			// give number to odd receive what to store
			MPI_Send(&matrix[rank], 1, MPI_INT, rankNeighborNext, 0, comm);
			MPI_Recv(&received, 1, MPI_INT, rankNeighborNext, 0, comm, status);
			matrix[rank] = received;
		}
		else {
			// receive number give what to store on even
			MPI_Recv(&received, 1, MPI_INT, rankNeighborPrev, 0, comm, status);
			if (y % 2 == 0){
				// left to right
				if (received > matrix[rank]){
					sendBack = matrix[rank];
					matrix[rank] = received;
				}
				else {
					sendBack = received;
				}
			}
			else {
				// right to left
				if (received < matrix[rank]){
					sendBack = matrix[rank];
					matrix[rank] = received;
				}
				else {
					sendBack = received;
				}
			}
			MPI_Send(&sendBack, 1, MPI_INT, rankNeighborPrev, 0, comm);
		}
	}
}

void evenSortVertical(int rank, int x, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status){
	if (x % 2 == 1 || (x % 2 == 0 && rankNeighborNext != MPI_PROC_NULL)){ // check if the next procces is not null (for N*N matrix with odd N)
		int received, sendBack;
		if (x % 2 == 0){
			// give number to odd receive what to store
			MPI_Send(&matrix[rank], 1, MPI_INT, rankNeighborNext, 0, comm);
			MPI_Recv(&received, 1, MPI_INT, rankNeighborNext, 0, comm, status);
			matrix[rank] = received;
		}
		else {
			// receive number give what to store on even
			MPI_Recv(&received, 1, MPI_INT, rankNeighborPrev, 0, comm, status);
			if (received > matrix[rank]){
				sendBack = matrix[rank];
				matrix[rank] = received;
			}
			else {
				sendBack = received;
			}
			MPI_Send(&sendBack, 1, MPI_INT, rankNeighborPrev, 0, comm);
		}
	}
}

void oddSortHorizontal(int rank, int y, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status){
	if ((rank % 2 == 0 && rankNeighborPrev != MPI_PROC_NULL) || (rank % 2 == 1 && rankNeighborNext != MPI_PROC_NULL)){ // check if the next procces is not null (for N*N matrix with odd N)
		int received, sendBack;

		if (rank % 2 == 1){
			// give number to even receive what to store
			MPI_Send(&matrix[rank], 1, MPI_INT, rankNeighborNext, 0, comm);
			MPI_Recv(&received, 1, MPI_INT, rankNeighborNext, 0, comm, status);
			matrix[rank] = received;
		}
		else {
			// receive number give what to store on odd
			MPI_Recv(&received, 1, MPI_INT, rankNeighborPrev, 0, comm, status);
			if (y % 2 == 0){
				if (received > matrix[rank]){
					sendBack = matrix[rank];
					matrix[rank] = received;
				}
				else {
					sendBack = received;
				}
			}
			else {
				if (received < matrix[rank]){
					sendBack = matrix[rank];
					matrix[rank] = received;
				}
				else {
					sendBack = received;
				}
			}
			MPI_Send(&sendBack, 1, MPI_INT, rankNeighborPrev, 0, comm);
		}
	}
}

void oddSortVertical(int rank, int x, int* matrix, int rankNeighborNext, int rankNeighborPrev, MPI_Comm comm, MPI_Status* status){
	if (x % 2 == 0 || (x % 2 == 1 && rankNeighborNext != MPI_PROC_NULL)){ // check if the next procces is not null (for N*N matrix with odd N)
		int received, sendBack;
		if (x % 2 == 1){
			// give number to even receive what to store
			MPI_Send(&matrix[rank], 1, MPI_INT, rankNeighborNext, 0, comm);
			MPI_Recv(&received, 1, MPI_INT, rankNeighborNext, 0, comm, status);
			matrix[rank] = received;
		}
		else {
			// receive number give what to store on odd
			MPI_Recv(&received, 1, MPI_INT, rankNeighborPrev, 0, comm, status);
			if (received > matrix[rank]){
				sendBack = matrix[rank];
				matrix[rank] = received;
			}
			else {
				sendBack = received;
			}
			MPI_Send(&sendBack, 1, MPI_INT, rankNeighborPrev, 0, comm);
		}
	}
}

void randMatrixNumbers(int* matrix, int sizeMatrix){
	srand(time(NULL));
	for (int i = 0; i < sizeMatrix * sizeMatrix; i++){
		matrix[i] = rand() % NUMBERS_RANGE_MAX;
	}
}

void printMatrix(int* matrix, int sizeMatrix, int myid){
	printf("%d is printing:\n", myid);
	for (int x = 0; x < sizeMatrix; x++){
		printf("[");
		for (int y = 0; y < sizeMatrix; y++){
			printf("%3d", matrix[x*sizeMatrix + y]);
			if (y < sizeMatrix - 1){
				printf(", ");
			}
		}
		printf("]\n");
	}
	printf("\n"); fflush(stdout);
}

void printMatrixSnakeSorted(int* matrix, int sizeMatrix, int myid){
	printf("%d is printing:\n", myid);
	printf("[");
	for (int x = sizeMatrix - 1; x >= 0; x--){
		if (x % 2 == 1){
			// regular
			for (int i = x * sizeMatrix; i < (x * sizeMatrix) + sizeMatrix; i++){
				printf("%3d ", matrix[i]);
			}
		}
		else {
			// reverse
			for (int i = (x * sizeMatrix) + sizeMatrix - 1; i >= x * sizeMatrix; i--){
				printf("%3d ", matrix[i]);
			}
		}
	}
	printf("]\n"); fflush(stdout);
}

double log_2(double n)
{
	return log(n) / log(2.0);
}

int toggleDirection(Direction direction){
	return (direction == HORIZONTAL) ? VERTICAL : HORIZONTAL;
}

int toggleOddEvent(OddEven oddEven){
	return (oddEven == EVEN) ? ODD : EVEN;
}