#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"

#include <sys/time.h>

#define N 512

double A[N*N],B[N*N];

int main(int argc,char *argv[])
{
	struct timeval s,e,ts,te;
	int i,j,k,m;
	double sum=0.0,sum0=0.0;

	int numprocs,my_rank;
	MPI_Init(&argc,&argv);
	MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
	MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
	if(my_rank==0) gettimeofday(&s,NULL);
	for(i=(N/numprocs)*my_rank;i<(N/numprocs)*(my_rank+1);i++){
		for(j=0;j<N;j++){ 
			//B初期化＆A単位行列
			A[N*i+j]=0; B[N*i+j]=0;
			if(i==j) A[N*i+j]=1;			
			//if((N*i+j)%(N+1)==0) A[N*i+j]=1;
			//printf("%lf ",A[N*i+j]);
		}
		//printf(" rank=%d\n",my_rank);
	}

	//共有
	gettimeofday(&ts,NULL);
	MPI_Allgather(&A[N*N/numprocs*my_rank], N*N/numprocs, MPI_DOUBLE, A, N*N/numprocs, MPI_DOUBLE, MPI_COMM_WORLD);
	gettimeofday(&te,NULL);
	printf("allgather time = %lf[s]\n",(te.tv_sec-ts.tv_sec)+(te.tv_usec-ts.tv_usec)*1.0E-6);
	/*
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			printf("%lf ",A[N*i+j]);
		}
		printf(" rank=%d\n",my_rank);
	}
	*/
	//if(my_rank == 0) gettimeofday(&ts,NULL);
	//二乗してBに格納
	for(i=(N/numprocs)*my_rank;i<(N/numprocs)*(my_rank+1);i++){
		for(j=0;j<N;j++){
			for(k=0;k<N;k++){
				B[N*i+j]=B[N*i+j]+A[N*i+k]*A[N*k+j];
			}
			//printf("%lf ",B[N*i+j]);
		}
		//printf(" rank=%d\n",my_rank);
	}
	/*	
	if(my_rank == 0){
		gettimeofday(&te,NULL);
		printf("N^3 time = %lf[s]\n",(te.tv_sec-ts.tv_sec)+(te.tv_usec-ts.tv_usec)*1.0E-6);
	}
	*/
	//rootに結合
	gettimeofday(&ts,NULL);
	MPI_Gather(&B[N*N/numprocs*my_rank], N*N/numprocs, MPI_DOUBLE, B, N*N/numprocs, MPI_DOUBLE, 0, MPI_COMM_WORLD);
	gettimeofday(&te,NULL);
	printf("gather time = %lf[s]\n",(te.tv_sec-ts.tv_sec)+(te.tv_usec-ts.tv_usec)*1.0E-6);
	/*
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			printf("%lf ",B[N*i+j]);
		}
		printf(" rank=%d\n",my_rank);

	}
	*/

	//1の数をカウント
	for(i=(N/numprocs)*my_rank;i<(N/numprocs)*(my_rank+1);i++){
		for(j=0;j<N;j++){
			sum+=B[N*i+j];
		}
	}
	//printf("%lf rank=%d\n",sum,my_rank);

	//合計
	gettimeofday(&ts,NULL);
	MPI_Reduce(&sum,&sum0,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);
	gettimeofday(&te,NULL);
	printf("reduce time = %lf[s]\n",((te.tv_sec-ts.tv_sec)+(te.tv_usec-ts.tv_usec)*1.0E-6)/10.0);
	MPI_Finalize();
	
	if(my_rank==0){
		gettimeofday(&e,NULL);
		printf("sum = %lf\ntime = %lf[s]\n",sum0,(e.tv_sec-s.tv_sec)+(e.tv_usec-s.tv_usec)*1.0E-6);
	}
}