c(pp)/dijkstra-parallel-example.c
// Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra ' s algorithm ; taking a graph its dimension and the starting point
void dijkstra(int graph[DIM][DIM], int start, int rank, int size){
	int i, j, k, minDistance, next, chunksize, rest, begin, end;
	int *recv_counts = NULL, *recv_displs = NULL, *sub_dist, *sub_parent;
	int global_min[2], local_min[2];
	int full_dist[DIM], full_parent[DIM];
	bool visited[DIM];
	chunksize = DIM / size; 
	begin = rank * chunksize; 
	end = begin + chunksize - 1; 
	rest = DIM % size;
	if (rank == size - 1){
		if (rest){
			chunksize += rest;			
			end += rest;
		}
	}
	sub_dist = (int *) malloc(chunksize * sizeof(int));
	for (i = begin; i <= end; i++){
		sub_dist[i - begin] = graph[start][i]; 
	}
	if (rank == 0){
		sub_dist[start] = 0; 
	}
	sub_parent = (int *) malloc(chunksize * sizeof(int));
	for (i = 0; i < chunksize; i++){
		sub_parent[i] = 0;
	}
	for (i = 0; i < DIM; i++){
		visited[i] = false; 
	}
	visited[start] = true; 
	for (i = 0; i < DIM; i++){
		local_min[0] = INF; 
		for (j = 0; j < chunksize ; j++){
			if (!visited[j + begin]){
				if (sub_dist[j] < local_min[0]){
					local_min[0] = sub_dist[j]; 
					local_min[1] = j + begin; 
				}
			}
		}
		if (rank != 0){
			MPI_Send(local_min, 2, MPI_INT, 0, 0, MPI_COMM_WORLD);
		}
		else {
			global_min[0] = local_min[0];
			global_min[1] = local_min[1];
			for (j = 1; j < size; j++){
				MPI_Recv(local_min, 2, MPI_INT, j, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
				if (local_min[0] < global_min[0]){
					global_min[0] = local_min[0];
					global_min[1] = local_min[1];
				}
			}
		}
		if (rank == 0){
			for (j = 1; j < size; j++){
				MPI_Send(global_min, 2, MPI_INT, j, 0, MPI_COMM_WORLD);
			}
		}
		else {
			MPI_Recv(global_min, 2, MPI_INT, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
		}
		minDistance = global_min[0];
		next = global_min[1];
		visited[next] = true;
		for (j = 0; j < chunksize; j++){
			if (!visited[j + begin]){
				if (minDistance + graph[next][j + begin] < sub_dist[j]){
					sub_dist[j] = minDistance + graph[next][j + begin];
					sub_parent[j] = next;
				}
			}
		}
	}
	----
	if (rank == 0){
		recv_displs = (int *) malloc(size * sizeof(int));
		recv_counts = (int *) malloc(size * sizeof(int));
	}
	MPI_Gather(&chunksize, 1, MPI_INT, recv_counts, 1, MPI_INT, 0, MPI_COMM_WORLD);
	if (rank == 0){
		recv_displs[0] = 0;
		for (i = 1; i < size; i++){
			recv_displs[i] = recv_displs[i - 1] + recv_counts[i - 1];
		}
	}
	MPI_Gatherv(sub_dist, chunksize, MPI_INT, full_dist, recv_counts, recv_displs, MPI_INT, 0, MPI_COMM_WORLD);
	MPI_Gatherv(sub_parent, chunksize, MPI_INT, full_parent, recv_counts, recv_displs, MPI_INT, 0, MPI_COMM_WORLD);
	----
	if (rank == 0){
		printf("Adjacency matrix:\n-----------------\n");
		printMatrix(graph);
		printf("\n\n");
		printf("Paths:\n------");
		for (i = 0; i < DIM; i++){
			printPath(i, start, full_parent, full_dist);
		}
		printf("\n");
	}
	free(sub_dist);
	free(recv_counts);
	free(recv_displs);
	return;
}
void dijkstra ( int graph [ DIM ] [ DIM ] , int start , int rank , int size ) { int i , j , k , minDistance , next , chunksize , rest , begin , end ; int * recv_counts = NULL , * recv_displs = NULL , * sub_dist , * sub_parent ; int global_min [ 2 ] , local_min [ 2 ] ; int full_dist [ DIM ] , full_parent [ DIM ] ; bool visited [ DIM ] ; chunksize = DIM / size ; begin = rank * chunksize ; end = begin + chunksize - 1 ; rest = DIM % size ; if ( rank == size - 1 ) { if ( rest ) { chunksize += rest ; end += rest ; } } sub_dist = ( int * ) malloc ( chunksize * sizeof ( int ) ) ; for ( i = begin ; i <= end ; i ++ ) { sub_dist [ i - begin ] = graph [ start ] [ i ] ; } if ( rank == 0 ) { sub_dist [ start ] = 0 ; } sub_parent = ( int * ) malloc ( chunksize * sizeof ( int ) ) ; for ( i = 0 ; i < chunksize ; i ++ ) { sub_parent [ i ] = 0 ; } for ( i = 0 ; i < DIM ; i ++ ) { visited [ i ] = false ; } visited [ start ] = true ; for ( i = 0 ; i < DIM ; i ++ ) { local_min [ 0 ] = INF ; for ( j = 0 ; j < chunksize ; j ++ ) { if ( ! visited [ j + begin ] ) { if ( sub_dist [ j ] < local_min [ 0 ] ) { local_min [ 0 ] = sub_dist [ j ] ; local_min [ 1 ] = j + begin ; } } } if ( rank != 0 ) { MPI_Send ( local_min , 2 , MPI_INT , 0 , 0 , MPI_COMM_WORLD ) ; } else { global_min [ 0 ] = local_min [ 0 ] ; global_min [ 1 ] = local_min [ 1 ] ; for ( j = 1 ; j < size ; j ++ ) { MPI_Recv ( local_min , 2 , MPI_INT , j , 0 , MPI_COMM_WORLD , MPI_STATUS_IGNORE ) ; if ( local_min [ 0 ] < global_min [ 0 ] ) { global_min [ 0 ] = local_min [ 0 ] ; global_min [ 1 ] = local_min [ 1 ] ; } } } if ( rank == 0 ) { for ( j = 1 ; j < size ; j ++ ) { MPI_Send ( global_min , 2 , MPI_INT , j , 0 , MPI_COMM_WORLD ) ; } } else { MPI_Recv ( global_min , 2 , MPI_INT , 0 , 0 , MPI_COMM_WORLD , MPI_STATUS_IGNORE ) ; } minDistance = global_min [ 0 ] ; next = global_min [ 1 ] ; visited [ next ] = true ; for ( j = 0 ; j < chunksize ; j ++ ) { if ( ! visited [ j + begin ] ) { if ( minDistance + graph [ next ] [ j + begin ] < sub_dist [ j ] ) { sub_dist [ j ] = minDistance + graph [ next ] [ j + begin ] ; sub_parent [ j ] = next ; } } } } if ( rank == 0 ) { recv_displs = ( int * ) malloc ( size * sizeof ( int ) ) ; recv_counts = ( int * ) malloc ( size * sizeof ( int ) ) ; } MPI_Gather ( & chunksize , 1 , MPI_INT , recv_counts , 1 , MPI_INT , 0 , MPI_COMM_WORLD ) ; if ( rank == 0 ) { recv_displs [ 0 ] = 0 ; for ( i = 1 ; i < size ; i ++ ) { recv_displs [ i ] = recv_displs [ i - 1 ] + recv_counts [ i - 1 ] ; } } MPI_Gatherv ( sub_dist , chunksize , MPI_INT , full_dist , recv_counts , recv_displs , MPI_INT , 0 , MPI_COMM_WORLD ) ; MPI_Gatherv ( sub_parent , chunksize , MPI_INT , full_parent , recv_counts , recv_displs , MPI_INT , 0 , MPI_COMM_WORLD ) ; if ( rank == 0 ) { printf ( " \n \n " ) ; printMatrix ( graph ) ; printf ( " \n \n " ) ; printf ( " \n " ) ; for ( i = 0 ; i < DIM ; i ++ ) { printPath ( i , start , full_parent , full_dist ) ; } printf ( " \n " ) ; } free ( sub_dist ) ; free ( recv_counts ) ; free ( recv_displs ) ; return ; }
Dijkstra's algorithm; taking a graph, its dimension and the starting point
Dijkstra ' s algorithm ; taking a graph its dimension and the starting point
// borders for MPI parallelization of arrays  // array size for each processor; int division // start index of array in loop // end index of array in loop // if #nodes is not divisible by #procs; remainder to last proc (imbalance) // loop 1: init distance vector; distances from start to adjescent nodes  // could als use i + begin /* set distance from start node to itself to zero; since the code works
	with parts of the full array, only node 0 will definitely be in the part
	assigned to rank 0, i.e. start nodes != 0 may be located in sub arrays of 
	other ranks; hence, the code will not work for other start nodes */ // loop 1': init parent node array; no exisiting parents yet // loop 1'': init status array; processed nodes are flagged with true  // not necessary, since zero is minDistance anyway; saves a bit of time as it circumvents the second if statement in loop 3  // loop 2: main part of algorithm; iterating over number of nodes // initializing minimum distance in every iteration /* loop 3: finding node with lowest distance value in distance vector
		(if node was not already visited); already processed nodes are
		excluded according to their visited status (true) */ // minimal distance value // index of the closest node // -------------------------------------------------------------------- // MPI part 1: start // find global minimum  //printf("rank %d: with min = %d and next = %d \n", rank, local_min[0], local_min[1]); // slaves send local minimum to the master //printf("rank %d: with min = %d and next = %d \n", rank, local_min[0], local_min[1]); // initialize global minimum with local min of master // checking for smaller values from slaves and updating // distribute the global minimum back to all procs // MPI part 1: end // -------------------------------------------------------------------- /* closest node in current distance list is found and thus given a
		processed flag, which will leave it untouched in further iterations */ /* loop 4: updating the distance vector with distances from next node 
		(graph[next][j]) -> including new connections (replacing INF) and
		shorter indirect paths; by adding the minDistance we keep track of the 
		distance already travelled w.r.t the start node; already processed
		nodes must again be excluded */ // ------------------------------------------------------------------------ // MPI part 2: start // initialize array for start index of concatenation (recv_displs) and chunksizes (recv_counts); preparation for MPI_Gatherv // gather chunksizes in array "recv_counts" for root // smarter: with recv_counts[rank] = chunksize // build recv_displs array with chunksizes from recv_counts // concatenate sub arrays // sub_dist and chunksize are basically local information of each thread // full_dist = destination array // recv_counts = array of dim size with chunksizes as elements // recv_displs = array of dim size with indexes for concatenation as elements // MPI part 2: end // ------------------------------------------------------------------------ // printing