aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c')
-rw-r--r--gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c379
1 files changed, 0 insertions, 379 deletions
diff --git a/gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c b/gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c
deleted file mode 100644
index 269d69da1..000000000
--- a/gcc-4.4.3/libgomp/testsuite/libgomp.c/sort-1.c
+++ /dev/null
@@ -1,379 +0,0 @@
-/* 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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-26 10:15:54 +0000