[SOLVED] CS CS3214 Fall 2014.

* Parallel Mergesort.
* Demo application that shows how one might use threadpools/futures
* in an application.
* Requires threadpool.c/threadpool.h

Copyright By Assignmentchef assignmentchef

* Written by Godmar Back for CS3214 Fall 2014.
* Updated Summer 2020

#include
#include
#include
#include
#include
#include
#include
#include
#include #include

/* When to switch from parallel to serial */
#define SERIAL_MERGE_SORT_THRESHOLD1000
static int min_task_size = SERIAL_MERGE_SORT_THRESHOLD;

#define INSERTION_SORT_THRESHOLD16
static int insertion_sort_threshold = INSERTION_SORT_THRESHOLD;

#include threadpool.h
#include threadpool_lib.h
#define DEFAULT_THREADS 4
static int nthreads = DEFAULT_THREADS;

typedef void (*sort_func)(int *, int);

/* Return true if array a is sorted. */
static bool
check_sorted(int a[], int n)
for (i = 0; i < n-1; i++)if (a[i] > a[i+1])
return false;
return true;

/* –
* Built-in qsort.
static int cmp_int(const void *a, const void *b)
return *(int *)a *(int *)b;

static void builtin_qsort(int *a, int N)
qsort(a, N, sizeof(int), cmp_int);

/* –
* Utilities: insertion sort.
static void insertionsort(int *a, int lo, int hi)
for (i = lo+1; i <= hi; i++) {int j = i;int t = a[j];while (j > lo && t < a[j – 1]) {a[j] = a[j – 1];static voidmerge(int * a, int * b, int bstart, int left, int m, int right)if (a[m] <= a[m+1])memcpy(b + bstart, a + left, (m – left + 1) * sizeof (a[0]));int i = bstart;int j = m + 1;int k = left;while (k < j && j <= right) {if (b[i] < a[j])a[k++] = b[i++];a[k++] = a[j++];memcpy(a + k, b + i, (j – k) * sizeof (a[0]));/* ————————————————————-* Serial implementation.static voidmergesort_internal(int * array, int * tmp, int left, int right)if (right – left < insertion_sort_threshold) {insertionsort(array, left, right);int m = (left + right) / 2;mergesort_internal(array, tmp, left, m);mergesort_internal(array, tmp, m + 1, right);merge(array, tmp, 0, left, m, right);static voidmergesort_serial(int * array, int n)if (n < insertion_sort_threshold) {insertionsort(array, 0, n);int * tmp = malloc(sizeof(int) * (n / 2 + 1));mergesort_internal(array, tmp, 0, n-1);free (tmp);/* ————————————————————-* Parallel implementation./* msort_task describes a unit of parallel work */struct msort_task {int *array;int left, right;/* Parallel mergesort */static voidmergesort_internal_parallel(struct thread_pool * threadpool, struct msort_task * s)int * array = s->array;
int * tmp = s->tmp;
int left = s->left;
int right = s->right;

if (right left <= min_task_size) {mergesort_internal(array, tmp + left, left, right);int m = (left + right) / 2;struct msort_task mleft = {.left = left,.right = m,.array = array,.tmp = tmpstruct future * lhalf = thread_pool_submit(threadpool,(fork_join_task_t) mergesort_internal_parallel,struct msort_task mright = {.left = m + 1,.right = right,.array = array,.tmp = tmpmergesort_internal_parallel(threadpool, &mright);future_get(lhalf);future_free(lhalf);merge(array, tmp, left, left, m, right);static void mergesort_parallel(int *array, int N) int * tmp = malloc(sizeof(int) * (N));struct msort_task root = {.left = 0, .right = N-1, .array = array, .tmp = tmpstruct thread_pool * threadpool = thread_pool_new(nthreads);struct future * top = thread_pool_submit(threadpool, (fork_join_task_t) mergesort_internal_parallel,future_get(top);future_free(top);thread_pool_shutdown_and_destroy(threadpool);free (tmp); * Benchmark one run of sort_func sorterstatic void benchmark(const char *benchmark_name, sort_func sorter, int *a0, int N, bool report)int *a = malloc(N * sizeof(int));memcpy(a, a0, N * sizeof(int));struct benchmark_data * bdata = start_benchmark();// parallel section here, including thread pool startup and shutdownsorter(a, N);stop_benchmark(bdata);// consistency checkif (!check_sorted(a, N)) {fprintf(stderr, “Sort failed
“);// report only if successfulif (report) {report_benchmark_results(bdata);printf(“%s result ok. Timings follow
“, benchmark_name);report_benchmark_results_to_human(stdout, bdata);free(bdata);static voidusage(char *av0, int exvalue)fprintf(stderr, “Usage: %s [-i ] [-n ] [-b] [-q] [-s ]

-iinsertion sort threshold, default %d

-mminimum task size before using serial mergesort, default %d

-nnumber of threads in pool, default %d

-brun built-in qsort

-sspecify srand() seed

-qalso run serial mergesort

, av0, INSERTION_SORT_THRESHOLD, SERIAL_MERGE_SORT_THRESHOLD, DEFAULT_THREADS);
exit(exvalue);

main(int ac, char *av[])
bool run_builtin_qsort = false;
bool run_serial_msort = false;

while ((c = getopt(ac, av, i:n:bhs:qm:)) != EOF) {
switch (c) {
insertion_sort_threshold = atoi(optarg);
min_task_size = atoi(optarg);
nthreads = atoi(optarg);
srand(atoi(optarg));
run_builtin_qsort = true;
run_serial_msort = true;
usage(av[0], EXIT_SUCCESS);
if (optind == ac)
usage(av[0], EXIT_FAILURE);

int N = atoi(av[optind]);

int i, * a0 = malloc(N * sizeof(int));
for (i = 0; i < N; i++)a0[i] = random();if (run_builtin_qsort)benchmark(“Built-in qsort”, builtin_qsort, a0, N, false);if (run_serial_msort)benchmark(“mergesort serial”, mergesort_serial, a0, N, false);printf(“Using %d threads, parallel/serials threshold=%d insertion sort threshold=%d
“, nthreads, min_task_size, insertion_sort_threshold);benchmark(“mergesort parallel”, mergesort_parallel, a0, N, true);return EXIT_SUCCESS; CS: assignmentchef QQ: 1823890830 Email: [email protected]