commit 328337343bb5137b66dcec935617bceaaaf990a7
parent 3143d9955c248ea40b5a676e09ac453136e1cbde
Author: Christos Margiolis <christos@margiolis.net>
Date: Thu, 12 Jan 2023 16:25:20 +0200
ex2a done
Diffstat:
2 files changed, 85 insertions(+), 39 deletions(-)
diff --git a/c_parallel_systems/ex2/Makefile b/c_parallel_systems/ex2/Makefile
@@ -1,6 +1,5 @@
all:
cc ex2a.c -fopenmp -lomp -o ex2a
- cc ex2b.c -fopenmp -lomp -o ex2b
clean:
- rm -f ex2a ex2b *.core
+ rm -f ex2a *.core
diff --git a/c_parallel_systems/ex2/ex2a.c b/c_parallel_systems/ex2/ex2a.c
@@ -1,38 +1,14 @@
#include <err.h>
-#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
+#include <time.h>
#include <omp.h>
-static int safe_input(const char *, ...);
static void pretty_print(int *, int, const char *);
-
-static int
-safe_input(const char *fmt, ...)
-{
- va_list args;
- char buf[48];
- int n, rc;
-
- /* Collect the arguments into a buffer. */
- va_start(args, fmt);
- vsnprintf(buf, sizeof(buf), fmt, args);
- va_end(args);
-
- /*
- * The following loop keeps asking for input as long as the current
- * input wasn't correct. In this case "incorrect" input means anything
- * other than digits.
- */
- do {
- printf("\r%s", buf);
- rc = scanf("%d", &n);
- (void)getchar();
- } while (rc != 1);
-
- return (n);
-}
+static int cmpfunc(const void *, const void *);
+static void merge(int *, int *, int *, int *, int *);
+static void multisort(int *, int *, int);
/*
* Print the contents of a 2D array like:
@@ -50,33 +26,104 @@ pretty_print(int *arr, int n, const char *name)
printf("]\n");
}
+/*
+ * Passed to qsort(3).
+ */
+static int
+cmpfunc(const void *a, const void *b)
+{
+ return (*(int *)a - *(int *)b);
+}
+
+static void
+merge(int *a, int *enda, int *b, int *endb, int *res)
+{
+ while (a <= enda && b <= endb) {
+ if (*a < *b)
+ *res++ = *a++;
+ else
+ *res++ = *b++;
+ }
+ while (a <= enda)
+ *res++ = *a++;
+ while (b <= endb)
+ *res++ = *b++;
+}
+
+static void
+multisort(int *arr, int *space, int n)
+{
+ int quarter, *sta, *spa, *stb, *spb, *stc, *spc, *std, *spd;
+
+ if ((quarter = n / 4) < 4)
+ qsort(arr, n, sizeof(int), cmpfunc);
+ else {
+ /* Split the array into 4 quarters. */
+ sta = arr;
+ spa = space;
+ stb = sta + quarter;
+ spb = spa + quarter;
+ stc = stb + quarter;
+ spc = spb + quarter;
+ std = stc + quarter;
+ spd = spc + quarter;
+#pragma omp task
+ multisort(sta, spa, quarter);
+#pragma omp task
+ multisort(stb, spb, quarter);
+#pragma omp task
+ multisort(stc, spc, quarter);
+#pragma omp task
+ multisort(std, spd, n - 3 * quarter);
+ /* Wait for the tasks above to finish. */
+#pragma omp taskwait
+#pragma omp task
+ /* Merge A and B into SpaceA */
+ merge(sta, sta + quarter - 1, stb, stb + quarter - 1, spa);
+#pragma omp task
+ /* Merge C and D into SpaceC */
+ merge(stc, stc + quarter - 1, std, arr + n - 1, spc);
+#pragma omp taskwait
+ /* Merge the two resulting couples (SpaceA and SpaceC). */
+ merge(spa, spc - 1, spc, space + n - 1, arr);
+ }
+}
+
int
main(int argc, char *argv[])
{
- int *a, i, n, ntd;
+ int *a, *space, i, n, ntd;
double start, end;
- ntd = safe_input("threads: ", 0);
+ if (argc < 3) {
+ fprintf(stderr, "usage: %s nthreads n\n", getprogname());
+ return (1);
+ }
+ if ((ntd = atoi(argv[1])) < 1)
+ err(1, "can't use nthreads n < 1");
+ if ((n = atoi(argv[2])) < 1)
+ err(1, "can't use n < 1");
+
+ srand(time(NULL));
omp_set_num_threads(ntd);
- n = safe_input("n: ", 0);
if ((a = malloc(n * sizeof(int))) == NULL)
err(1, "malloc");
+ if ((space = malloc(n * sizeof(int))) == NULL)
+ err(1, "malloc");
for (i = 0; i < n; i++)
- a[i] = safe_input("a[%d]: ", i);
+ a[i] = rand() % 100;
start = omp_get_wtime();
- /* TODO */
- <++>
+ pretty_print(a, n, "A_unsorted");
+ multisort(a, space, n);
+ pretty_print(a, n, "A_multisort");
end = omp_get_wtime();
printf("Total time: %f seconds\n", end - start);
- pretty_print(a, n, "A_unsorted");
- pretty_print(a, n, "A_multisort");
-
free(a);
return (0);
