package mpi;

import be.ac.vub.ir.util.Chrono;
import be.ac.vub.ir.util.GetOpt;


/**
 * @author Sarah ElShal
 * Parallel and sequential implementation of a prime number counter
 * 
 */

public class CountPrimesCollectiveComm {
		
	// Default program parameters
	final static int DEFAULTSIZE = 50000;

	public static void main(String[] args){	
		// *** INITIALIZE ***
		GetOpt options = new GetOpt("n:",args); // allows you to parse program options. 
		// ':' means that an argument is following after the option (here: -n 1000)
		String ns = options.getOptionParam('n');
		int arraySize = (ns != null) ? Integer.parseInt(ns) : DEFAULTSIZE ;
		
		// ** Start up **
		MPI.Init(args);
		int myRank = MPI.COMM_WORLD.Rank();
		int nbrProcesses = MPI.COMM_WORLD.Size();
		
		int[] data = new int [arraySize]; // in this MPI implementation, also slaves should allocate memory! This strange, because they do not send anything

		if (myRank == 0){			
			data = createAndFillArray(arraySize); // only master knows the data
		}
		
		// *** PARALLEL RUN  ***
		Chrono masterChrono = new Chrono();	
		
		int nbrPrimesPar = countPrimesPar(data, args);
		
		long mastertime = masterChrono.stop();			
			
		
		if (myRank == 0){
			System.out.println("Parallel solution found "+nbrPrimesPar+" primes among "+data.length+" odd numbers in "+masterChrono);
			
			// *** SEQUENTIAL RUN (master only) ***
			Chrono seqChrono = new Chrono();
			int nbrPrimesSeq = countPrimes(data);
			long seqtime = seqChrono.stop();
			
			if (nbrPrimesSeq == nbrPrimesPar)
				System.out.println("Sequential solution found the same number of primes. OK.");
			else
				System.err.println("Sequential solution found "+nbrPrimesSeq+" primes which is different!!!!!");
			
			System.out.println();
			System.out.println("PARALLEL RUNTIME   = "+masterChrono);
			System.out.println("SEQUENTIAL RUNTIME = "+seqChrono);
			System.out.println("speedup            = "+((float) seqtime/mastertime));
			System.out.println("efficiency         = "+((float) seqtime/mastertime/nbrProcesses));
			System.out.println(" ++++++++++ finished +++++++++++ ");
		}
	
		// ** Finalize **
		MPI.Finalize(); // Don't forget!!
		
	}
	// *** Array Filling ***
	static int[] createAndFillArray(int n){ // fills with all odd numbers
		int[] data = new int[n];
		for (int i=0;i<n;i++)
			data[i] = 1 + 2*i;
		return data;
	}
	
	// *** Sequential Prime Counting ***
	public static int countPrimes(int[] data) {
		int np = 0;
		for (int value: data)
			if (isPrime(value))
				np++;
		return np;		
	}
	
	// *** Parallel Prime Counting ***
	public static int countPrimesPar(int[] data, String[] args) {

		final int myRank = MPI.COMM_WORLD.Rank();
		final int NBR_PROCESSES = MPI.COMM_WORLD.Size();
		final int NBR_ELEMENTS_PER_PROCESS = data.length/NBR_PROCESSES;
		final int NBR_REST_ELEMENTS = data.length%NBR_PROCESSES; // modulo. 
		
		int[] process_data = new int[NBR_ELEMENTS_PER_PROCESS]; // send buffer cannot be reused in this MPI implementation...
		
		// scatter
		MPI.COMM_WORLD.Scatter(data, NBR_REST_ELEMENTS, process_data.length, MPI.INT , process_data, 0, process_data.length, MPI.INT, 0);	
		// rest is used as offset, will be processed by master
		
		// count primes
		Chrono slaveChrono = new Chrono();	
		int s_np = 0;
		if (myRank == 0){ // master processes rest terms
			for (int i=0;i<NBR_REST_ELEMENTS;i++)
				if (isPrime(data[i]))
					s_np++;
		}
		for (int value: process_data)
			if (isPrime(value))
				s_np++;
		
		slaveChrono.stop();
		
		System.out.println("Process " + myRank+ " found "+s_np+" primes among his "+(NBR_ELEMENTS_PER_PROCESS+(myRank == 0?NBR_REST_ELEMENTS:0))+" elements in "+slaveChrono);
		
		int[] send_buffer  = new int []{s_np};
		int[] recv_buffer = new int [1];
		
		// reduce
		MPI.COMM_WORLD.Reduce(send_buffer, 0, recv_buffer, 0, 1, MPI.INT, MPI.SUM, 0);
		int par_result = recv_buffer[0];
		
		return par_result;		
	}
	
	public static boolean isPrime(int value){ // this is not the most efficient implementation, we know...
		for (int j=2 ; j<value ; j++){
			if ((value % j) == 0)
				return false;
		}
		return true;
	}
}