Question

Using the template given in ParallelMergeSort.c write the functions to divide the original array into equal fractions given the number of threads and perform Parallel MergeSort pThreads. Your algorithm should work for 2 threads.

ParallelMergeSort.c

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define SIZE 100

int array[SIZE];

void fillArrayWithRandomNumbers(int arr[SIZE]) {
for(int i = 0; i<SIZE; i++) array[i] = rand()%100;
}

void printArray(int arr[SIZE]) {
for(int i = 0; i<SIZE; i++) printf("%5d", arr[i]);
printf("\n");
}

typedef struct StartEndIndexes {
int start;
int end;
} StartEndIndexes;

// Runs mergesort on the array segment described in the
// argument. Spawns two threads to mergesort each half
// of the array segment, and then merges the results.
void* mergeSort(void* args) {
return NULL;
}

int main() {
srand(time(0));
StartEndIndexes sei;
sei.start = 0;
sei.end = SIZE - 1;
  
// 1. Fill array with random numbers.
fillArrayWithRandomNumbers(array);
  
// 2. Print the array.
printf("Unsorted array: ");
printArray(array);
  
// 3. Create a 2 threads for merge sort.
  
// 4. Wait for mergesort to finish.
  
// 5. Print the sorted array.
printf("Sorted array: ");
printArray(array);
}

Makefile

mergeSort: ParallelMergeSort.c
   gcc -std=c99 -pthread -o ParallelMergeSort ParallelMergeSort.c -I.

Answer 1

Answer: Note: // & /* */ - indicates comment lines. To explain in detail, comment lines included.

ParallelMergeSort.c

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define SIZE 100

int array[SIZE];

void fillArrayWithRandomNumbers(int arr[SIZE]) {
for(int i = 0; i<SIZE; i++) array[i] = rand()%100;
}

void printArray(int arr[SIZE]) {
for(int i = 0; i<SIZE; i++) printf("%5d", arr[i]);
printf("\n");
}

typedef struct StartEndIndexes {
int start;
int end;
} StartEndIndexes;

// Runs mergesort on the array segment described in the
// argument. Spawns two threads to mergesort each half
// of the array segment, and then merges the results.
void* mergeSort(void* args) {

return NULL;
}

int main() {
srand(time(0));
StartEndIndexes sei;
sei.start = 0;
sei.end = SIZE - 1;
  
// 1. Fill array with random numbers.
fillArrayWithRandomNumbers(array);
  
// 2. Print the array.
printf("Unsorted array: ");
printArray(array);
  
// 3. Create a 2 threads for merge sort.

// p1 & p2 are thread ids

pthread_t p1, p2;

int retval;

/* create thread 1 - in the following function call - 4th argument is one (1) to indicate that the first thread should sort elements from 0 to 50. */

retval = pthread_create(&p1, NULL, &mergeSort, 1);

if (retval != 0)

{

printf("Error in thread1 creation\n");

return -1;

}

/* create thread 2 - in the following function call - 4th argument is two (2) to indicate that the first thread should sort elements from 50 to 100. */

retval = pthread_create(&p2, NULL, &mergeSort, 2);

if (retval != 0)

{

printf("Error in thread2 creation\n");

return -1;

}

// 4. Wait for mergesort to finish.

// Wait for first thread to finish mergesort
retval = pthread_join(p1, NULL);

if (retval != 0)

{

printf("Error in thread1 join\n");

return -1;

}

// Wait for second thread to finish mergesor

int retval1 = pthread_join(p2, NULL);

if (retval1 != 0)

{

printf("Error in thread2 join\n");

return -1;

}

// thread exit

pthread_exit(&retval);

// thread exit

pthread_exit(&retval1);
// 5. Print the sorted array.
printf("Sorted array: ");
printArray(array);
}