implementation of a multithreaded version of mergesort.

[argusDawn]

Hello,

Im working on making a multithreaded version of mergesort.
[The // Perform "cleanup" work by merging remaining sections. part]

I have the normal merge and mergesort functions, the biggest issue is with the
indices passed to the merge function. when i try running it, it causes a segmentaion fault but i dont know whats wrong :(

*Here's my thought process*

the issue is "indices passed to the merge function" were wrong

so, I made a new object for the clean up mergeing that has m, left, and right stored in it.

this code is supposed to be setting them correctly (values_left is half of the threads)
m_args[i].m = (((i + 1) * size / values_left - 1) + (i * size /values_left) )2;
m_args[i].left = i * size / values_left;
m_args[i].right = (i + 1) * size / values_left - 1;

so when this is called
pthread_create(&threads[i], NULL, merge_wrap, &m_args[i]) != 0

it goes to merge_wrap, and that sends the values from above into the merge method.

 #define _POSIX_C_SOURCE 199309
#include <time.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>


#define DEFAULT_SIZE 10000000
#define DEFAULT_THREADS 1


void multithreaded_mergesort(int A[], int size, int num_threads);

typedef struct {
	int* A;
	int left;
	int right;
} mergesort_arg;

typedef struct {
	int* A;
	int left;
	int m;
	int right;
} mergeing_arg;

void* mergesort_wrapper(const mergesort_arg* arg);


void mergesort(int A[], int left, int right);
void* merge_wrap(mergeing_arg* arg);
int merge( int A[] , int left , int m , int right);

int ms_diff(struct timespec start, struct timespec stop);
void show_usage(const char* exe);


int main(int argc, char* argv[]) {
	int size = DEFAULT_SIZE;
	int num_threads = DEFAULT_THREADS;

	// Process command-line arguments.
	if (argc == 3) {
		char *end;
		size = strtol(argv[1], &end, 10);
		if (*end != 0) {
			show_usage(argv[0]);
			return EXIT_FAILURE;
		}
		num_threads = strtol(argv[2], &end, 10);
		if (*end != 0) {
			show_usage(argv[0]);
			return EXIT_FAILURE;
		}
		if (size < 1 || num_threads < 1) {
			show_usage(argv[0]);
			return EXIT_FAILURE;
		}
	} else if (argc != 1) {
		show_usage(argv[0]);
		return EXIT_FAILURE;
	}

	// Seed the random number generator.
	srand(time(NULL));

	// Allocate and populate an array.
	int* A = (int*)malloc(size * sizeof(int));
	if (A == NULL) {
		printf("ERROR: Unable to allocate array.\n");
		return EXIT_FAILURE;
	}
	for (int i = 0; i < size; i++)
		A[i] = rand();

	// Start tracking execution time.
	struct timespec start;
	clock_gettime(CLOCK_REALTIME, &start);

	multithreaded_mergesort(A, size, num_threads);
	

	// Stop tracking execution time.
	struct timespec stop;
	clock_gettime(CLOCK_REALTIME, &stop);
	printf("%d ms elapsed.\n", ms_diff(start, stop));

	free(A);
	return EXIT_SUCCESS;
}

void multithreaded_mergesort(int A[], int size, int num_threads) {
	// Conceptually partition the array and use separate threads to
	// independently sort each section.  The thread that invoked this
	// function will wait for all other threads to finish.

	// Create function arguments for all threads.
	mergesort_arg ms_args[num_threads];
	for (int i = 0; i < num_threads; i++) {
		ms_args[i].A = A;
		ms_args[i].left = i * size / num_threads;
		ms_args[i].right = (i + 1) * size / num_threads - 1;
	}

	// Create and start each thread.
	pthread_t threads[num_threads];
	for (int i = 0; i < num_threads; i++)
		if (pthread_create(&threads[i], NULL, mergesort_wrapper, &ms_args[i]) != 0) {
			printf("ERROR: Unable to create new thread.\n");
			exit(EXIT_FAILURE);
		}

	// Wait for all threads to finish.
	for (int i = 0; i < num_threads; i++)
		pthread_join(threads[i], NULL);
		

	// Perform "cleanup" work by merging remaining sections.
	mergeing_arg m_args[num_threads / 2];
	for (int values_left = num_threads; values_left > 1; values_left = (values_left + 1) / 2) {
	
		// Set function arguments.
		for (int i = 0; i < values_left / 2; i++) {
			m_args[i].m = (((i + 1) * size / values_left - 1) + (i * size / values_left) ) / 2;
			m_args[i].left = i * size / values_left;
			m_args[i].right = (i + 1) * size / values_left - 1;
		}
		
		// Create and start threads.
		for (int i = 0; i < values_left / 2; i++)
			if (pthread_create(&threads[i], NULL, merge_wrap, &m_args[i]) != 0) {
				printf("ERROR: Unable to create new thread.\n");
				exit(EXIT_FAILURE);
			}
			
		// Wait for all threads to finish.
		for (int i = 0; i < values_left / 2; i++)
			pthread_join(threads[i], NULL);
	
	}
	
}

void* mergesort_wrapper(const mergesort_arg* arg) {
	fprintf(stderr, "Sorting section %d-%d.\n", arg->left, arg->right);
	mergesort(arg->A, arg->left, arg->right);
	return NULL;
}

void* merge_wrap(mergeing_arg* arg) {
	merge(arg->A, arg->left, arg->m, arg->right);
	return NULL;
}

// Indices left and right are inclusive.
void mergesort(int A[], int left, int right) {

	if( left < right){
	int m = (right + left )/2;
	mergesort(A , left , m );
	mergesort(A, m+1 , right);
	merge( A, left, m, right);
	}

}

int merge( int A[] , int left , int m , int right){

	//int* A = (int*)malloc(size * sizeof(int));
	int* b = (int*)malloc( ((right - left) + 1) * sizeof(int));
	int i = left;
	int j = m + 1;
	int k = 0;
	
	while( i <= m && j <= right ){
		if(A[i] <= A[j])
			b[k++] = A[i++];
		else
			b[k++] = A[j++];
	}
	while ( i <= m )
		b[k++] = A[i++];
	while( j <= right)
		b[k++] = A[j++];
	
	k--;
	while( k >= 0 ){
		A[left+ k] = b[k];
		k--;
	}
	
	free(b);
}



int ms_diff(struct timespec start, struct timespec stop) {
	return 1000 * (stop.tv_sec - start.tv_sec) + (stop.tv_nsec - start.tv_nsec) / 1000000;
}

void show_usage(const char* exe) {
	printf("Usage: %s [<array-size> <num-threads>]\n", exe);
	printf("  If omitted, <array-size> defaults to %d.\n", DEFAULT_SIZE);
	printf("  If omitted, <num-threads> defaults to %d.\n", DEFAULT_THREADS);
}