iknn.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "mpi.h"
#define lines 60000

struct point {
    int id;
    double dist;
};
int size;
int cmpfunc(const void * a, const void * b);
double fdist(double **A, double **B, int i, int j);
void knn(double **A, double **B, struct point **D, int size, int n);
void switcharrays(double **sendv , double ** recv);

int main(int argc,char **argv){
	
  int  nproc, pid, size, next, prev;
  double **sendv, **recv, **vals;
  FILE *file;
  char buff[512], *d;
  struct point **distid, finalD[lines][30];
  size=lines/nproc+lines%nproc;
  
  MPI_Request req[2];
  MPI_Status status[2];
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &pid);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  file = fopen( "data.bin", "rb");

  prev = pid-1;
  next = pid+1;
  if (pid == 0)  prev = nproc - 1;
  if (pid == (nproc - 1))  next = 0;
  
  distid=(struct point**)malloc(size*sizeof(struct point));
  sendv=(double**)malloc(size*(sizeof(double))); 
  recv=(double**)malloc(size*(sizeof(double))); 
  vals=(double**)malloc(size*(sizeof(double))); 
  
  for(int i=0; i<size;i++){sendv[i]=(double*)malloc(30*sizeof(double));
                           recv[i]=(double*)malloc(30*sizeof(double));
                           vals[i]=(double*)malloc(30*sizeof(double));
                           distid[i]=(struct point*)malloc(30*sizeof(struct point));}         
			
  for(int k=0; k<size*pid; k++){fgets(buff, 512, (FILE*)file);}
			
  for(int i=0; i<size; i++){
	 fgets(buff, 512, file);
     int j=0;
	 for(d = strtok(buff, " ,"); d; d = strtok(NULL, " ,")){
		sendv[i][j]= atof(d);
		recv[i][j]= atof(d);
		vals[i][j]= atof(d);
		j++;
	 }
  }
				
  knn(vals, sendv, distid, size, 0);


  
  for (int k=0; k<nproc-1; k++){
    for (int i=0; i<size; i++){
      for (int j=0; j<30; j++){
       MPI_Isend(&(sendv[i][j]), 1, MPI_DOUBLE, next, 0, MPI_COMM_WORLD, &req[0]);	
       MPI_Irecv(&(recv[i][j]), 1, MPI_DOUBLE, prev, 0, MPI_COMM_WORLD, &req[1]);
      } 
	   MPI_Waitall(2, req, status);
	}
	switcharrays(sendv, recv);
    knn(vals, sendv, distid, size, -1);  
  }
  
  for (int i=0; i<size; i++){ 
	  for (int j=0; j<30; j++){
         printf("line: %i  pid: %i \n",i,pid);
		 printf("%lf %i \n", distid[i][j].dist,distid[i][j].id);
	  }
	  printf("\n");
  }	 
  MPI_Finalize();	
  fclose(file);		
  return 0;
}

void knn(double **A, double **B, struct point **D, int size, int n){
    int k=n;
	double d;
	
	for (int i=0; i<size; i++){
	    if(k!=-1 && k!=30){k=0;}
		for (int j=0; j<size; j++){
			d= fdist(A, B, i, j);
		    if(k<30 && d!=0){
		       D[i][k].dist=d;
			   D[i][k].id=j;
			   if(k==29){qsort(D[i],30,sizeof(struct point),cmpfunc);}
            }else if(d<D[i][29].dist && d!=0){
               D[i][29].dist=d;
			   D[i][k].id=j;
			   qsort(D[i], 30, sizeof(struct point), cmpfunc);
		    }
		    if(k!=-1 && d!=0){k++;}
	    }            
       
	}
}


int cmpfunc(const void * a, const void * b){
  struct point *A = (struct point *)a;
  struct point *B = (struct point *)b;
  if (A->dist < B->dist)
     return -1;

  else if (A->dist > B->dist)
     return 1;

  else
     return 0;
}

double fdist(double **A, double **B, int i, int j){
	double tmp=0, sum=0; 
    for (int k=0; k<30; k++){
		 tmp=(A[i][k]-B[j][k])*(A[i][k]-B[j][k]);
         sum+=tmp;
	}		 
    sum=sqrt(sum);
	return sum;
}

void switcharrays(double **sendv , double ** recv){
  for(int i=0; i<size; i++ ){
     for(int j=0; j<30;j++){
     sendv[i][j]=recv[i][j];
     }
  }
} 

knn.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "mpi.h"
#define rows 60000
#define columns 30


struct point {
    int id;
    double dist;
};
int size;
int cmpfunc(const void * a, const void * b);
double fdist(double **A, double **B, int i, int j);
void knn(double **A, double **B, struct point **D, int size, int n);
void switcharrays(double **sendv , double ** recv);

int main(int argc,char **argv){
	
  int  nproc, pid, size, next, prev;
  double **sendv, **recv, **vals;
  FILE *file;
  char buff[512], *d;
  struct point **distid;
  size=rows/nproc+rows%nproc;

  MPI_Status status;
  MPI_Init(&argc, &argv);
  MPI_Comm_rank(MPI_COMM_WORLD, &pid);
  MPI_Comm_size(MPI_COMM_WORLD, &nproc);
  file = fopen( "data.bin", "rb");

  prev = pid-1;
  next = pid+1;
  if (pid == 0)  prev = nproc - 1;
  if (pid == (nproc - 1))  next = 0;
  
  distid=(struct point**)malloc(size*sizeof(struct point));
  sendv=(double**)malloc(size*(sizeof(double))); 
  recv=(double**)malloc(size*(sizeof(double))); 
  vals=(double**)malloc(size*(sizeof(double))); 
  
  for(int i=0; i<size;i++){sendv[i]=(double*)malloc(columns*sizeof(double));
                           recv[i]=(double*)malloc(columns*sizeof(double));
                           vals[i]=(double*)malloc(columns*sizeof(double));
                           distid[i]=(struct point*)malloc(columns*sizeof(struct point));}         
			
  for(int k=0; k<size*pid; k++){fgets(buff, 512, (FILE*)file);}
			
  for(int i=0; i<size; i++){
	 fgets(buff, 512, file);
     int j=0;
	 for(d = strtok(buff, " ,"); d; d = strtok(NULL, " ,")){
		sendv[i][j]= atof(d);
		recv[i][j]= atof(d);
		vals[i][j]= atof(d);
		j++;
	 }
  }
				
  knn(vals, sendv, distid, size, 0);
  
  for (int k=0; k<nproc-1; k++){
    for (int i=0; i<size; i++){
      for (int j=0; j<columns; j++){
        MPI_Send(&(sendv[i][j]),1, MPI_DOUBLE, next, 0, MPI_COMM_WORLD);
	    MPI_Recv(&(recv[i][j]),1, MPI_DOUBLE, prev, 0, MPI_COMM_WORLD, &status); 
      } 
	}
	MPI_Barrier(MPI_COMM_WORLD);
	switcharrays(sendv, recv);
    knn(vals, sendv, distid, size, -1);
  }
  
  
  
  for (int i=0; i<size; i++){ 
	  for (int j=0; j<30; j++){
         printf("line: %i  pid: %i \n",i,pid);
		 printf("%lf %i \n", distid[i][j].dist,distid[i][j].id);
	  }
	  printf("\n");
  }	 
  MPI_Barrier(MPI_COMM_WORLD);
  MPI_Finalize();	
  fclose(file);		
  return 0;
}

void knn(double **A, double **B, struct point **D, int size, int n){
    int k=n;
	double d;
	
	for (int i=0; i<size; i++){
	    if(k!=-1 && k!=30){k=0;}
		for (int j=0; j<size; j++){
			d= fdist(A, B, i, j);
		    if(k<30 && d!=0){
		       D[i][k].dist=d;
			   D[i][k].id=j;
			   if(k==29){qsort(D[i],30,sizeof(struct point),cmpfunc);}
            }else if(d<D[i][29].dist && d!=0){
               D[i][29].dist=d;
			   D[i][k].id=j;
			   qsort(D[i], 30, sizeof(struct point), cmpfunc);
		    }
		    if(k!=-1 && d!=0){k++;}
	    }            
       
	}
}


int cmpfunc(const void * a, const void * b){
  struct point *A = (struct point *)a;
  struct point *B = (struct point *)b;
  if (A->dist < B->dist)
     return -1;

  else if (A->dist > B->dist)
     return 1;

  else
     return 0;
}

double fdist(double **A, double **B, int i, int j){
	double tmp=0, sum=0; 
    for (int k=0; k<columns; k++){
		 tmp=(A[i][k]-B[j][k])*(A[i][k]-B[j][k]);
         sum+=tmp;
	}		 
    sum=sqrt(sum);
	return sum;
}

void switcharrays(double **sendv , double ** recv){
  for(int i=0; i<size; i++ ){
     for(int j=0; j<columns;j++){
     sendv[i][j]=recv[i][j];
     }
  }
}