Find maximum value in 1-D array.

parallel_find_max.cpp

#include <cstdio>
#include <mpi.h>
#include <algorithm>
#include <ctime>
#include <climits>

#define GRN   "\x1B[32m"
#define RESET "\x1B[0m"
#define CYN   "\x1B[36m"
#define RED    "\033[31m"  

#define MILLI 1000

#define MASTER_ID 0

#define MASTER_TAG 1
#define WORKER_TAG 2

#define SIZE 300000000

MPI_Status status;
int a[SIZE];


//generate numbers between -1000000000 and 1000000000
int GenerateRandomNumber(){
	return std::rand() % (20000001) + (-10000000);
}

void FillArrayWithRandomNumbers(){
	srand (time(NULL));
	for (int i = 0; i < SIZE; ++i){
		a[i] = GenerateRandomNumber();
	}
}

int main(int argc, char *argv[])
{
	int message_tag;
	int num_procs;
	int proc_id;
	int chunk_size;
	int rem;
	int send_count;
	int from = 0;
	int local_max;
	int num_workers;
	int max = INT_MIN;

	long long int starttime; 
	long long int endtime;

	MPI_Init(&argc, &argv);
	MPI_Comm_size(MPI_COMM_WORLD, &num_procs);
	MPI_Comm_rank(MPI_COMM_WORLD, &proc_id);

	num_workers = num_procs - 1;
	
	chunk_size = SIZE / num_workers;
	rem = SIZE % num_workers;

	if(proc_id == MASTER_ID){
		printf("%sFilling array with size %s%d%s with random values%s\n", CYN, GRN, SIZE, CYN, RESET);
		FillArrayWithRandomNumbers();
	}

	if(proc_id == MASTER_ID){
		starttime = clock();

		if(num_workers > 0){
			message_tag = MASTER_TAG;
			for (int worker_proc_id = 1; worker_proc_id <= num_workers; worker_proc_id ++){
				// printf("%sSending values to worker %s%d%s\n", CYN, RED, worker_proc_id, RESET);
				send_count = worker_proc_id <= rem ? chunk_size + 1 : chunk_size;

				MPI_Send(&send_count, 1, MPI_INT, worker_proc_id, message_tag, MPI_COMM_WORLD);
				MPI_Send(&a[from], send_count, MPI_INT, worker_proc_id, message_tag, MPI_COMM_WORLD);
				from += send_count;
			}

			message_tag = WORKER_TAG;
			for(int worker_proc_id = 1; worker_proc_id <= num_workers; worker_proc_id ++){
				MPI_Recv(&local_max, 1, MPI_INT, worker_proc_id, message_tag, MPI_COMM_WORLD, &status);
				max = local_max > max ? local_max : max;

				// printf("%sReceived max value %s%d%s from process %s%d%s\n", CYN, GRN, local_max, CYN, RED, worker_proc_id, RESET);
			}
		}
		else{
			for(int i = 0; i < SIZE; i ++){
				max = max < a[i] ? a[i] : max;
			}
		}

		endtime = clock();

		printf("%sMaximum value: %s%d %s\n", CYN, GRN, max, RESET);
		printf("%sThat took %s%lf%s milliseconds%s\n", CYN, RED, (double)((endtime - starttime) / (1.0 * MILLI)), CYN, RESET);
	}

	if(proc_id != MASTER_ID){
		message_tag = MASTER_TAG;
		
		MPI_Recv(&send_count, 1, MPI_INT, MASTER_ID, message_tag, MPI_COMM_WORLD, &status);
		MPI_Recv(&a, send_count, MPI_INT, MASTER_ID, message_tag, MPI_COMM_WORLD, &status);
		local_max = a[0];
		for (int i = 1; i < send_count; ++i){
			if(local_max < a[i]) local_max = a[i];
		}

		message_tag = WORKER_TAG;
		MPI_Send(&local_max, 1, MPI_INT, MASTER_ID, message_tag, MPI_COMM_WORLD);
	}

	MPI_Finalize();

	return 0;
}