Subversion Repositories openrisc

/* 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;

}