--- /dev/null
+/* Test and benchmark of a couple of parallel sorting algorithms.
+ Copyright (C) 2008 Free Software Foundation, Inc.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 3, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>. */
+
+#include <limits.h>
+#include <omp.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int failures;
+
+#define THRESHOLD 100
+
+static void
+verify (const char *name, double stime, int *array, int count)
+{
+ int i;
+ double etime = omp_get_wtime ();
+
+ printf ("%s: %g\n", name, etime - stime);
+ for (i = 1; i < count; i++)
+ if (array[i] < array[i - 1])
+ {
+ printf ("%s: incorrectly sorted\n", name);
+ failures = 1;
+ }
+}
+
+static void
+insertsort (int *array, int s, int e)
+{
+ int i, j, val;
+ for (i = s + 1; i <= e; i++)
+ {
+ val = array[i];
+ j = i;
+ while (j-- > s && val < array[j])
+ array[j + 1] = array[j];
+ array[j + 1] = val;
+ }
+}
+
+struct int_pair
+{
+ int lo;
+ int hi;
+};
+
+struct int_pair_stack
+{
+ struct int_pair *top;
+#define STACK_SIZE 4 * CHAR_BIT * sizeof (int)
+ struct int_pair arr[STACK_SIZE];
+};
+
+static inline void
+init_int_pair_stack (struct int_pair_stack *stack)
+{
+ stack->top = &stack->arr[0];
+}
+
+static inline void
+push_int_pair_stack (struct int_pair_stack *stack, int lo, int hi)
+{
+ stack->top->lo = lo;
+ stack->top->hi = hi;
+ stack->top++;
+}
+
+static inline void
+pop_int_pair_stack (struct int_pair_stack *stack, int *lo, int *hi)
+{
+ stack->top--;
+ *lo = stack->top->lo;
+ *hi = stack->top->hi;
+}
+
+static inline int
+size_int_pair_stack (struct int_pair_stack *stack)
+{
+ return stack->top - &stack->arr[0];
+}
+
+static inline void
+busy_wait (void)
+{
+#if defined __i386__ || defined __x86_64__
+ __asm volatile ("rep; nop" : : : "memory");
+#elif defined __ia64__
+ __asm volatile ("hint @pause" : : : "memory");
+#elif defined __sparc__ && (defined __arch64__ || defined __sparc_v9__)
+ __asm volatile ("membar #LoadLoad" : : : "memory");
+#else
+ __asm volatile ("" : : : "memory");
+#endif
+}
+
+static inline void
+swap (int *array, int a, int b)
+{
+ int val = array[a];
+ array[a] = array[b];
+ array[b] = val;
+}
+
+static inline int
+choose_pivot (int *array, int lo, int hi)
+{
+ int mid = (lo + hi) / 2;
+
+ if (array[mid] < array[lo])
+ swap (array, lo, mid);
+ if (array[hi] < array[mid])
+ {
+ swap (array, mid, hi);
+ if (array[mid] < array[lo])
+ swap (array, lo, mid);
+ }
+ return array[mid];
+}
+
+static inline int
+partition (int *array, int lo, int hi)
+{
+ int pivot = choose_pivot (array, lo, hi);
+ int left = lo;
+ int right = hi;
+
+ for (;;)
+ {
+ while (array[++left] < pivot);
+ while (array[--right] > pivot);
+ if (left >= right)
+ break;
+ swap (array, left, right);
+ }
+ return left;
+}
+
+static void
+sort1 (int *array, int count)
+{
+ omp_lock_t lock;
+ struct int_pair_stack global_stack;
+ int busy = 1;
+ int num_threads;
+
+ omp_init_lock (&lock);
+ init_int_pair_stack (&global_stack);
+ #pragma omp parallel firstprivate (array, count)
+ {
+ int lo = 0, hi = 0, mid, next_lo, next_hi;
+ bool idle = true;
+ struct int_pair_stack local_stack;
+
+ init_int_pair_stack (&local_stack);
+ if (omp_get_thread_num () == 0)
+ {
+ num_threads = omp_get_num_threads ();
+ hi = count - 1;
+ idle = false;
+ }
+
+ for (;;)
+ {
+ if (hi - lo < THRESHOLD)
+ {
+ insertsort (array, lo, hi);
+ lo = hi;
+ }
+ if (lo >= hi)
+ {
+ if (size_int_pair_stack (&local_stack) == 0)
+ {
+ again:
+ omp_set_lock (&lock);
+ if (size_int_pair_stack (&global_stack) == 0)
+ {
+ if (!idle)
+ busy--;
+ if (busy == 0)
+ {
+ omp_unset_lock (&lock);
+ break;
+ }
+ omp_unset_lock (&lock);
+ idle = true;
+ while (size_int_pair_stack (&global_stack) == 0
+ && busy)
+ busy_wait ();
+ goto again;
+ }
+ if (idle)
+ busy++;
+ pop_int_pair_stack (&global_stack, &lo, &hi);
+ omp_unset_lock (&lock);
+ idle = false;
+ }
+ else
+ pop_int_pair_stack (&local_stack, &lo, &hi);
+ }
+
+ mid = partition (array, lo, hi);
+ if (mid - lo < hi - mid)
+ {
+ next_lo = mid;
+ next_hi = hi;
+ hi = mid - 1;
+ }
+ else
+ {
+ next_lo = lo;
+ next_hi = mid - 1;
+ lo = mid;
+ }
+
+ if (next_hi - next_lo < THRESHOLD)
+ insertsort (array, next_lo, next_hi);
+ else
+ {
+ if (size_int_pair_stack (&global_stack) < num_threads - 1)
+ {
+ int size;
+
+ omp_set_lock (&lock);
+ size = size_int_pair_stack (&global_stack);
+ if (size < num_threads - 1 && size < STACK_SIZE)
+ push_int_pair_stack (&global_stack, next_lo, next_hi);
+ else
+ push_int_pair_stack (&local_stack, next_lo, next_hi);
+ omp_unset_lock (&lock);
+ }
+ else
+ push_int_pair_stack (&local_stack, next_lo, next_hi);
+ }
+ }
+ }
+ omp_destroy_lock (&lock);
+}
+
+static void
+sort2_1 (int *array, int lo, int hi, int num_threads, int *busy)
+{
+ int mid;
+
+ if (hi - lo < THRESHOLD)
+ {
+ insertsort (array, lo, hi);
+ return;
+ }
+
+ mid = partition (array, lo, hi);
+
+ if (*busy >= num_threads)
+ {
+ sort2_1 (array, lo, mid - 1, num_threads, busy);
+ sort2_1 (array, mid, hi, num_threads, busy);
+ return;
+ }
+
+ #pragma omp atomic
+ *busy += 1;
+
+ #pragma omp parallel num_threads (2) \
+ firstprivate (array, lo, hi, mid, num_threads, busy)
+ {
+ if (omp_get_thread_num () == 0)
+ sort2_1 (array, lo, mid - 1, num_threads, busy);
+ else
+ {
+ sort2_1 (array, mid, hi, num_threads, busy);
+ #pragma omp atomic
+ *busy -= 1;
+ }
+ }
+}
+
+static void
+sort2 (int *array, int count)
+{
+ int num_threads;
+ int busy = 1;
+
+ #pragma omp parallel
+ #pragma omp single nowait
+ num_threads = omp_get_num_threads ();
+
+ sort2_1 (array, 0, count - 1, num_threads, &busy);
+}
+
+#if _OPENMP >= 200805
+static void
+sort3_1 (int *array, int lo, int hi)
+{
+ int mid;
+
+ if (hi - lo < THRESHOLD)
+ {
+ insertsort (array, lo, hi);
+ return;
+ }
+
+ mid = partition (array, lo, hi);
+ #pragma omp task
+ sort3_1 (array, lo, mid - 1);
+ sort3_1 (array, mid, hi);
+}
+
+static void
+sort3 (int *array, int count)
+{
+ #pragma omp parallel
+ #pragma omp single
+ sort3_1 (array, 0, count - 1);
+}
+#endif
+
+int
+main (int argc, char **argv)
+{
+ int i, count = 1000000;
+ double stime;
+ int *unsorted, *sorted, num_threads;
+ if (argc >= 2)
+ count = strtoul (argv[1], NULL, 0);
+
+ unsorted = malloc (count * sizeof (int));
+ sorted = malloc (count * sizeof (int));
+ if (unsorted == NULL || sorted == NULL)
+ {
+ puts ("allocation failure");
+ exit (1);
+ }
+
+ srand (0xdeadbeef);
+ for (i = 0; i < count; i++)
+ unsorted[i] = rand ();
+
+ omp_set_nested (1);
+ omp_set_dynamic (0);
+ #pragma omp parallel
+ #pragma omp single nowait
+ num_threads = omp_get_num_threads ();
+ printf ("Threads: %d\n", num_threads);
+
+ memcpy (sorted, unsorted, count * sizeof (int));
+ stime = omp_get_wtime ();
+ sort1 (sorted, count);
+ verify ("sort1", stime, sorted, count);
+
+ memcpy (sorted, unsorted, count * sizeof (int));
+ stime = omp_get_wtime ();
+ sort2 (sorted, count);
+ verify ("sort2", stime, sorted, count);
+
+#if _OPENMP >= 200805
+ memcpy (sorted, unsorted, count * sizeof (int));
+ stime = omp_get_wtime ();
+ sort3 (sorted, count);
+ verify ("sort3", stime, sorted, count);
+#endif
+
+ return 0;
+}
projects / msp430-gcc.git / blobdiff