binarysearch.cpp

A program written by C++ which is used to search using binary search concept on parallel processes,,

#include "mpi.h"
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc,char **argv)
{
	/** Parallel Finding the max in Arr **/
	
	const int Master = 0;
	const int Tag_Size = 1;
	const int Tag_Data= 2;
	const int Tag_Max=3;
      int max;
	  int MaxInAll;
	int MyId, P;
	int* A;
	int ArrSize, Target;
	int n, Start;
	int i, x;
	int Source, dest, Tag;
	int WorkersDone = 0 ;//num of proc finished getting their max
		
	MPI::Status RecvStatus;	

	//Initialize..
	MPI::Init(argc, argv);
	//Get Environment Info..
	P = MPI::COMM_WORLD.Get_size();
	MyId = MPI::COMM_WORLD.Get_rank();

	
		

	//start working..
	if (MyId == Master)
	{
		//print welcome message..
		cout<<"This is the master process on "<<P<<" Processes\n";
		MaxInAll=0;
		int GlobIndx;
		//Aquire needed input..
		cout<<"Enter the number of elements you want to generate..";
		cin>> ArrSize;
		//Allocate the needed space..
		A = new int[ArrSize];

	    //Randomly generate the data of the array
		srand ( P ); /* initialize random seed: */
		for ( i= 0; i<ArrSize; i++)
		{
			A[i] = rand();
			cout<<A[i]<<endl;
		}
		//find the number of data per process
		n = ArrSize/(P-1);

		//send the data to the rest of the processes ...
		for( i = 1; i < P; i++)
		{
			//cout<<"sending part of array to processor "<< P<<endl;
			dest = i;

			//send part size..
			if (i == P-1) 
  // be careful with the last process, it takes the
  //rest of the elements
				n = ArrSize - (n*(P-2));
 			Tag = Tag_Size;
			MPI::COMM_WORLD.Send(&n, 1, MPI::INT, dest, Tag);
			//THEN  send sub array elements
			Tag = Tag_Data;
			Start = (i - 1) * ( ArrSize/(P-1) );//all other than Master 			MPI::COMM_WORLD.Send(A+Start, n, MPI::INT, dest, Tag);
			MPI::COMM_WORLD.Send(A+Start, n, MPI::INT, dest, Tag);
		}		
		//Now, the master process waits for all other processes to 
//report that it is done..
		WorkersDone = 0;
		int MaxIndex = 0;
		while (WorkersDone < P-1 )
		{
        MPI::COMM_WORLD.Recv(&x, 1, MPI::INT, MPI::ANY_SOURCE, MPI::ANY_TAG, RecvStatus);
			Source = RecvStatus.Get_source();
			Tag = RecvStatus.Get_tag();
			if (Tag == Tag_Max)//msh 3rfa eh lzmet el tag 
			{
				 GlobIndx = (Source - 1)*(ArrSize/(P-1) ) + x;	
				if ( A[GlobIndx] > MaxInAll)
				{
					MaxInAll = A[GlobIndx];
					MaxIndex = GlobIndx;
				}

				WorkersDone++;
			}		 		
		}
		if(WorkersDone==P-1)//msh 3rfa eh lzmet el check dah :D
			cout << "Process "<<Source<<"  found the max of the array "<< MaxInAll<<"  at index "<<MaxIndex;
	//clean up the space reserved by Arr "A"
		delete [] A;
	}//Master Work done..
	else
	{
		max=0;
		//Worker's jobs starts here
		cout<<"Process  "<<MyId<<" is alive...\n";
		Source = Master;		
		//Receive Portion size ..
		Tag = Tag_Size;
		MPI::COMM_WORLD.Recv(&n, 1, MPI::INT, Source, Tag);
		//Receive Data..
		A = new int[n];
		Tag = Tag_Data;
		MPI::COMM_WORLD.Recv(A, n, MPI::INT, Source, Tag);
		cout<<"Process "<<MyId<< "Received "<<n<<" data elements\n";
		//Now do Finding the maximum part..
		int max_i;
		i = 0;
		while (i<n )
		{
			if ( A[i] > max )
			{ 
				max=A[i];				
				max_i=i;
			}
			
				i++;
		}
		//notify the master process that this process has  finished its  job 
		dest = Master;
		Tag = Tag_Max;
		cout<<"Process "<<MyId<< " has max equals  "<<max<<endl;
		MPI::COMM_WORLD.Send(&max_i, 1, MPI::INT, dest, Tag);
		//clean up "A" space
		delete [] A;
	}
	
MPI::Finalize();
	return 0;
	
}