authParallelAndDistributedSystemsCourseExercise2/NonBlocking/spaceOptimized/knnMPINonBlockingDeclarations.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#include "knnMPINonBlockingDeclarations.h"
#include "mpi.h"

void getArguments(int argc, char** argv){
	if (argc != 6) {
		printf("Usage: %s p d k filename\nwhere:\n", argv[0]);
		printf("\tp is the the number of points\n");
		printf("\td is the number of dimensions of each point\n");
		printf("\tk is the number of neighbors to search for\n");
		printf("\tdf is the filename of the dataset file\n");
		printf("\ttf is the filename of the dataset file\n");
		abExit(1);
	}
	numberOfPoints = atoi(argv[1]);
	numberOfDimensions = atoi(argv[2]);
	numberOfNeighbors = atoi(argv[3]);
	if (numberOfNeighbors >= numberOfPoints) {
		numberOfNeighbors = numberOfPoints - 1;
	}
	pointsFilename = argv[4];
	testFilename = argv[5];
}

void init(double ***pointsArray, double ***inBuffer, double ***outBuffer
	, neighbor ***sortedNeighborsArray, int chunksize, int offset){
	//Allocates memory for points array
	*pointsArray = cMalloc(chunksize, numberOfDimensions);
	//Allocates memory for the buffer storing points coming from another process
	*inBuffer = cMalloc(chunksize, numberOfDimensions);
	//Allocates memory for the buffer storing points going out to another process
	*outBuffer = cMalloc(chunksize, numberOfDimensions);

	//Allocates memory for neighbors array
	if ( (*sortedNeighborsArray = (neighbor**)(malloc((sizeof(neighbor *)) * chunksize))) != NULL ){
		for (int row = 0; row < chunksize; ++row){
			if ( ( (*sortedNeighborsArray)[row]
				= (neighbor*)(malloc((sizeof(neighbor)) * numberOfNeighbors)) ) == NULL ){
				printf("Error allocating memory\n");
				abExit(1);
			}
		}
	} else {
		printf("Error allocating memory\n");
		abExit(1);
	}

	//Reads coordinates from the file
	if (readPointsArrayFromFile(pointsArray, chunksize, offset)){
		abExit(1);
	}

	//Initializes neighbors array distances and ID's to -1
	for (int point=0; point<chunksize; ++point){
		for(int neighbor=0; neighbor<numberOfNeighbors; ++neighbor){
			(*sortedNeighborsArray)[point][neighbor].distance = -1;
			(*sortedNeighborsArray)[point][neighbor].neighborId = -1;
		}
	}
}

double **cMalloc(int rows, int columns){
	double **array;
	//allocates a continuous block of memory
	double *tempArray = (double *)calloc(rows * columns, sizeof(double));
	if (tempArray == NULL){
		printf("Error allocating memory\n");
		abExit(1);
	}

	//creates pointers to each row and column for easy indexing
	if ((array = ((double**)(malloc((sizeof(double *)) * rows)))) != NULL){
		for (int row = 0; row < rows; ++row){
			array[row] = &(tempArray[columns * row]);
		}
	} else {
		printf("Error allocating memory\n");
		abExit(1);
	}

	return array;
}

int readPointsArrayFromFile(double ***array, int chunksize, int offset){
	FILE *pointsBinaryFile = fopen(pointsFilename, "rb");

	if (pointsBinaryFile == NULL){
		printf("Couldn't open points file.\n");
		return 1;
	}
	if (fseek(pointsBinaryFile, offset * sizeof(double), SEEK_SET)){
		printf("Error reading the file. Quitting.\n");
		abExit(0);
	}
	for (int point=0; point<chunksize; ++point){
		if ( fread((*array)[point], sizeof(double), numberOfDimensions, pointsBinaryFile)
			!= numberOfDimensions ){
			if(feof(pointsBinaryFile)){
				printf("Premature end of file reached.\n");
			} else{
				printf("Error reading points file.");
			}
			fclose(pointsBinaryFile);
			return 1;
		}
	}
	fclose(pointsBinaryFile);

	return 0;
}

void printArray(int rows, int columns, double ***array){
	for (int row=0; row<rows; ++row){
		for (int column=0; column<columns; ++column){
			printf("[%d][%d] = %f\n", row, column, (*array)[row][column]);
		}
		printf("\n");
	}
}

void calculateDistances(double ***firstPointsSet, double ***secondPointsSet
	, neighbor ***sortedNeighborsArray, int chunksize, int myOffset, int indexOffset){
	for (int firstPoint=0; firstPoint<chunksize; ++firstPoint){
		for (int secondPoint=0; secondPoint<chunksize; ++secondPoint){
			if (myOffset + firstPoint == indexOffset + secondPoint){
				continue;
			}
			double distance = 0;
			for (int dimensionIndex=0; dimensionIndex<numberOfDimensions; ++dimensionIndex){
				double tmpDiff = (*firstPointsSet)[firstPoint][dimensionIndex]
					- (*secondPointsSet)[secondPoint][dimensionIndex];
				distance += tmpDiff * tmpDiff;
			}
			addDistanceAndShift(sortedNeighborsArray, firstPoint, indexOffset + secondPoint
				, distance);
		}
	}
}

void addDistanceAndShift(neighbor ***sortedNeighborsArray, int firstPointId, int secondPointId
	, double pointsDistance){
	for (int arrayIndex=0; arrayIndex<numberOfNeighbors; ++arrayIndex){
		//Gets distance stored in the array for this index
		double thisNeighborDistance = (*sortedNeighborsArray)[firstPointId][arrayIndex].distance;

		if (thisNeighborDistance == -1){ //Loop reached the end of the array
			(*sortedNeighborsArray)[firstPointId][arrayIndex].distance = pointsDistance;
			(*sortedNeighborsArray)[firstPointId][arrayIndex].neighborId = secondPointId;
			break;
		} else if (thisNeighborDistance > pointsDistance){
			//Distance at the this index is greater than the distance being inserted
			//Shifts right all non empty columns holding distances lower than pointsDistance
			for (int moveColumn=numberOfNeighbors-2; moveColumn>=arrayIndex; --moveColumn){
				double tempDistance = (*sortedNeighborsArray)[firstPointId][moveColumn].distance;
				if (tempDistance == -1){ //Skips empty columns
					continue;
				}
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].distance = tempDistance;
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].neighborId
					= (*sortedNeighborsArray)[firstPointId][moveColumn].neighborId;
			}

			/*
					Forward iteration is slower than reverse!
			*/
			/*for (int moveColumn=arrayIndex; moveColumn<numberOfNeighbors-1; ++moveColumn){
				double tempDistance = (*sortedNeighborsArray)[firstPointId][moveColumn].distance;
				if (tempDistance == -1){ //Skips empty columns
					break;
				}
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].distance = tempDistance;
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].neighborId
					= (*sortedNeighborsArray)[firstPointId][moveColumn].neighborId;
			}*/

			//Inserts pointsDistance in the space created after shifting
			(*sortedNeighborsArray)[firstPointId][arrayIndex].distance = pointsDistance;
			(*sortedNeighborsArray)[firstPointId][arrayIndex].neighborId = secondPointId;
			break;
		}
	}
}

void swapPointers(double ***firstArray, double ***secondArray){
	double **tempPtr = *firstArray;
	*firstArray = *secondArray;
	*secondArray = tempPtr;
}

int test(neighbor ***sortedNeighborsArray, int chunksize, int offset, char *testFilename){
	FILE *testFile = fopen(testFilename, "r");
	char *discarded = NULL;
	size_t n = 0;

	if (testFile == NULL){
		printf("Couldn't open test file.\n");
		perror("fopen");
		return 1;
	}
	if (offset){
		for (int line=0; line<offset; ++line){
			if (getline(&discarded, &n, testFile) == -1){
				perror("Error reading test file");
				return 1;
			}
			n = 0;
		}
		free(discarded);
	}
	for (int point=0; point<chunksize; ++point){
		for (int i=0; i<numberOfNeighbors; ++i){
			int tempID = 0;
			if (fscanf(testFile, "%d,", &tempID) == EOF){
				printf("Premature end of file reached.\n");
				fclose(testFile);
				return 1;
			}
			if ((*sortedNeighborsArray)[point][i].neighborId != tempID - 1){ //-1 because f@ck matlab
				fclose(testFile);
				return 1;
			}
		}
	}

	fclose(testFile);
	return 0;
}

void cleanUp(double ***pointsArray, double ***inBuffer, double ***outBuffer
	, neighbor ***sortedNeighborsArray, int chunksize){
	free((*pointsArray)[0]);
	free(*pointsArray);

	free((*inBuffer)[0]);
	free(*inBuffer);

	free((*outBuffer)[0]);
	free(*outBuffer);

	for (int row=0; row<chunksize; ++row){
		free((*sortedNeighborsArray)[row]);
	}
	free(*sortedNeighborsArray);
}

void abExit(int exitCode){
	int initialized = 0;
	MPI_Initialized(&initialized);
	if (initialized){
		MPI_Abort(MPI_COMM_WORLD, -1);
	}
	exit(0);
}