/*
  ************************************************
  Somma di n numeri calcolati su macchine tipo MIMD
  
  Progetto Realizzato da 
  
  Giovanni Di Cecca
  ACM Student Member
  Association for Computing Machinery
     
  Web Site: http://www.dicecca. net

  E-Mail: info@dicecca.net
  
  ************************************************
  
  Richiede Librerie MPI
  
  Per compialzione in Windows XP, scaricare la libreria:
  http://lnx.dicecca.net/portale/cartelle-web/doc_download/79-mpi-library-for-windows.html
  
  Manuale MPI
  http://lnx.dicecca.net/portale/cartelle-web/doc_download/80-mpi-library-for-windows-manual.html
  
  Manuale Operativo del Progetto
  
  http://lnx.dicecca.net/portale/cartelle-web/doc_download/99-somma-di-n-numeri-su-architettura-mimd.html
  ************************************************
*/

// Parte preprocessore
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "mpi.h"

// Inizio del programma 
int main (int argc, char **argv)
{
	// Dichiarazioni variabili
    int menum,nproc,tag; // Variabili per MPI
	int n,nloc,i,sum,resto,nlocgen;
	int ind,p,r,inviaA,ricevida,tmp;
	int *pot,*vett,*vett_loc,passi=0;
	int sumloc=0;
	
	/* 
	********************************************
	** Fase di inizializzazione dell'ambiente di calcolo
	********************************************		
	*/
	
    // Variabili per verificare il livello delle prestazioni
	double T_inizio,T_fine,T_max;

	// Contiene le informazioni sulla ricezione del messaggio
	MPI_Status info;
	
	// Inizializzazione dell'ambiente di calcolo MPI
	MPI_Init(&argc,&argv);
	
	// Identificativo del processore (contenuto in menum)
	MPI_Comm_rank(MPI_COMM_WORLD, &menum);
	
	// Verifica del numero di processori della rete di calcolo
	MPI_Comm_size(MPI_COMM_WORLD, &nproc);


	/* 
	********************************************
	** Fase di inserimento dei dati
	********************************************		
	*/
	
	// Seleziona il processore P0
	if (menum==0)
	{
		system("clear"); // pulisci schermo
		printf("Inserire quanti numeri vuoi sommare: ");
		scanf("%d",&n);
		
        // Allocazione dinamica di un vettore di n elementi interi nel processore P0
		vett=(int*)calloc(n,sizeof(int));
	}

	// Invio del valore di n a tutti i processori appartenenti a MPI_COMM_WORLD
	MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);

	// calcolo del numero di addendi da assegnare a ciascun processore
	nlocgen=n/nproc;
	
    //Calcolo del resto. Stabiliamo se ci sono altri addendi da ripartire tra i processori*/
	resto=n%nproc;

	// Se ci sono addendi in piu, il processore di identificativo menum incrementa il numero di addendi ricevuti 
	if(menum<resto)
	{
		nloc=nlocgen+1;
	}
	
	// altrimenti gli addendi restano quelli assegnati in precedenza 
	else
	{
		nloc=nlocgen;
	}
	
	// Crea dinamicamente dei vettori locali nei processori per le somme parziali
	vett_loc=(int*)calloc(nloc, sizeof(int));
    
	// Il processore P0  inserisce i dati nel vettore
	if (menum==0)
	{
        // Inizializza la generazione random degli addendi utilizzando... l'ora attuale del sistema
        srand((unsigned int) time(0)); 
        
        // Inserisi i dati meterialmente nel vettore
        for(i=0; i<n; i++)
		{
			// Creazione del vettore contenenti addendi generati a random
			*(vett+i)=(int)rand()%50+1;
		}
		
		// Stampa del vettore che contiene i dati da sommare (flag di controllo)
		// Se sono superiori a 100, però, salta la visualizzazione
		if (n<100)
		{
			for (i=0; i<n; i++)
			{
				printf("\n\nElemento %d del vettore = %d",i,*(vett+i));
			}
        }
		
        for(i=0;i<nloc;i++)
		{
			// creazione del vettore locale per il processore P0
			*(vett_loc+i)=*(vett+i);
		}
        
		ind=nloc;

		// Ciclo for con cui PO invia i dati parziali prestabiliti  agli altri processori per il calcolo
		for(i=1; i<nproc; i++)
		{
			tag=i; // assegnazione id del messaggio
			//SE ci sono addendi in sovrannumero da ripartire tra i processori 
            if (i<resto) 
			{
				// il processore P0 gli invia il corrispondete vettore locale considerando un addendo in più
				MPI_Send(vett+ind,nloc,MPI_INT,i,tag,MPI_COMM_WORLD);
				ind=ind+nloc;
			} // END THEN
			
            else 
			{
				// Il processore P0 invia il corrispondete vettore locale
				MPI_Send(vett+ind,nlocgen,MPI_INT,i,tag,MPI_COMM_WORLD);
				ind=ind+nlocgen;
			}// end else
		}//end for
	}// end THEN 
    // SE non siamo il processore P0 riceviamo i dati trasmessi dal processore P0
    else
    {
		// tag è uguale numero di processore
		tag=menum;
  
		// fase di ricezione
		MPI_Recv(vett_loc,nloc,MPI_INT,0,tag,MPI_COMM_WORLD,&info);
	}// end else

	
	/* 
	********************************************
	** Calcolo delle somma parziali e totali
	********************************************		
	*/
	
	// Uso di MPI_Barrier per la fase di sincronizzazione
	// fornisce un meccanismo sincronizzante per tutti i processori del MPI_COMM_WORLD
	// ogni processore si ferma aspettando che l'istruzione venga eseguita dal resto dei processori
	MPI_Barrier(MPI_COMM_WORLD);
 
	T_inizio=MPI_Wtime(); //inizio del cronometro per il calcolo del tempo di inizio

	for(i=0;i<nloc;i++)
	{
		// ogni processore effettua la somma parziale
		sumloc=sumloc+*(vett_loc+i);
	}

	// p è il numero di processori
	p=nproc;

	// Fase di calcolo del logaritmo in base 2 di nproc per selezionare 
	// i processori che effettuerann le somme parziali
	while(p!=1)
	{
		// shifta di un bit a destra 
		p=p>>1;
		
		// determina il numero dei passi per sapere quante spedizioni di somme parziali bisogna fare
		passi++;
	}
 
 	// allocazione dinamica del vettore pot che calcola la potenza di 2^n
	pot=(int*)calloc(passi+1,sizeof(int));

	for(i=0;i<=passi;i++)
	{
		// creazione del vettore pot di elementi passi+1, contenente le potenze di 2
		pot[i]=p<<i;
	}

	
	// Fase di comunicazione tra processori
	// viene mandata la somma parziale con i dati da sommare
	// finché ci sono ancora dei passi da eseguire ...
	for(i=0;i<passi;i++)
	{
		// ... calcolo identificativo del processore
		r=menum%pot[i+1];
		
		// Se l'identificativo non corrisponde a quello del processore P0...
		if(r==pot[i])
		{
			// calcolo dell'identificativo del processore a cui spedire la somma locale
			inviaA=menum-pot[i];
			tag=inviaA;
			// invio del risultato della propria somma parziale a inviaA
			MPI_Send(&sumloc,1,MPI_INT,inviaA,tag,MPI_COMM_WORLD);
		}//end then
		else if(r==0) // se sono il processore P0
		{
			ricevida=menum+pot[i];
			tag=menum;
			// ricezione del risultato della somma parziale di ricevida
			MPI_Recv(&tmp,1,MPI_INT,ricevida,tag,MPI_COMM_WORLD,&info);
			// calcolo della somma parziale al passo i
			sumloc=sumloc+tmp;
		}//end else
	}// end for

	MPI_Barrier(MPI_COMM_WORLD);
	T_fine=MPI_Wtime()-T_inizio; // calcolo del tempo di fine
 
	// Calcolo del tempo di esecuzione
	MPI_Reduce(&T_fine,&T_max,1,MPI_DOUBLE,MPI_MAX,0,MPI_COMM_WORLD);

	if(menum==0)
	{
	
		// Visualizza i dati
		printf("\n\nProcessori impegnati: %d\n", nproc);
		printf("\nLa somma e': %d\n", sumloc);
		printf("\nTempo locale: %lf\n", T_fine);
		printf("\nMPI_Reduce max time: %f\n",T_max);
	}// end if
 
	// routine chiusura MPI
	MPI_Finalize();
}// fine prg