* Parallel Mergesort.
* Demo application that shows how one might use threadpools/futures
* in an application.
* Requires threadpool.c/threadpool.h
Copyright By PowCoder代写 加微信 powcoder
* Written by Godmar Back for CS3214 Fall 2014.
* Updated Summer 2020
#include
#include
#include
#include
#include
#include
#include
#include
#include
/* When to switch from parallel to serial */
#define SERIAL_MERGE_SORT_THRESHOLD 1000
static int min_task_size = SERIAL_MERGE_SORT_THRESHOLD;
#define INSERTION_SORT_THRESHOLD 16
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 void
merge(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 void
mergesort_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 void
mergesort_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 void
mergesort_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 = tmp
struct 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 = tmp
mergesort_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 = tmp
struct 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 sorter
static 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 shutdown
sorter(a, N);
stop_benchmark(bdata);
// consistency check
if (!check_sorted(a, N)) {
fprintf(stderr, "Sort failed\n");
// report only if successful
if (report) {
report_benchmark_results(bdata);
printf("%s result ok. Timings follow\n", benchmark_name);
report_benchmark_results_to_human(stdout, bdata);
free(bdata);
static void
usage(char *av0, int exvalue)
fprintf(stderr, "Usage: %s [-i
” -i insertion sort threshold, default %d\n”
” -m minimum task size before using serial mergesort, default %d\n”
” -n number of threads in pool, default %d\n”
” -b run built-in qsort\n”
” -s specify srand() seed\n”
” -q also run serial mergesort\n”
, 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\n",
nthreads, min_task_size, insertion_sort_threshold);
benchmark("mergesort parallel", mergesort_parallel, a0, N, true);
return EXIT_SUCCESS;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com