OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgomp/] [testsuite/] [libgomp.c/] [sort-1.c] - Blame information for rev 791

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 735 jeremybenn
/* Test and benchmark of a couple of parallel sorting algorithms.
2
   Copyright (C) 2008 Free Software Foundation, Inc.
3
 
4
   GCC is free software; you can redistribute it and/or modify it under
5
   the terms of the GNU General Public License as published by the Free
6
   Software Foundation; either version 3, or (at your option) any later
7
   version.
8
 
9
   GCC is distributed in the hope that it will be useful, but WITHOUT ANY
10
   WARRANTY; without even the implied warranty of MERCHANTABILITY or
11
   FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12
   for more details.
13
 
14
   You should have received a copy of the GNU General Public License
15
   along with GCC; see the file COPYING3.  If not see
16
   <http://www.gnu.org/licenses/>.  */
17
 
18
#include <limits.h>
19
#include <omp.h>
20
#include <stdbool.h>
21
#include <stdio.h>
22
#include <stdlib.h>
23
#include <string.h>
24
 
25
int failures;
26
 
27
#define THRESHOLD 100
28
 
29
static void
30
verify (const char *name, double stime, int *array, int count)
31
{
32
  int i;
33
  double etime = omp_get_wtime ();
34
 
35
  printf ("%s: %g\n", name, etime - stime);
36
  for (i = 1; i < count; i++)
37
    if (array[i] < array[i - 1])
38
      {
39
        printf ("%s: incorrectly sorted\n", name);
40
        failures = 1;
41
      }
42
}
43
 
44
static void
45
insertsort (int *array, int s, int e)
46
{
47
  int i, j, val;
48
  for (i = s + 1; i <= e; i++)
49
    {
50
      val = array[i];
51
      j = i;
52
      while (j-- > s && val < array[j])
53
        array[j + 1] = array[j];
54
      array[j + 1] = val;
55
    }
56
}
57
 
58
struct int_pair
59
{
60
  int lo;
61
  int hi;
62
};
63
 
64
struct int_pair_stack
65
{
66
  struct int_pair *top;
67
#define STACK_SIZE 4 * CHAR_BIT * sizeof (int)
68
  struct int_pair arr[STACK_SIZE];
69
};
70
 
71
static inline void
72
init_int_pair_stack (struct int_pair_stack *stack)
73
{
74
  stack->top = &stack->arr[0];
75
}
76
 
77
static inline void
78
push_int_pair_stack (struct int_pair_stack *stack, int lo, int hi)
79
{
80
  stack->top->lo = lo;
81
  stack->top->hi = hi;
82
  stack->top++;
83
}
84
 
85
static inline void
86
pop_int_pair_stack (struct int_pair_stack *stack, int *lo, int *hi)
87
{
88
  stack->top--;
89
  *lo = stack->top->lo;
90
  *hi = stack->top->hi;
91
}
92
 
93
static inline int
94
size_int_pair_stack (struct int_pair_stack *stack)
95
{
96
  return stack->top - &stack->arr[0];
97
}
98
 
99
static inline void
100
busy_wait (void)
101
{
102
#if defined __i386__ || defined __x86_64__
103
  __asm volatile ("rep; nop" : : : "memory");
104
#elif defined __ia64__
105
  __asm volatile ("hint @pause" : : : "memory");
106
#elif defined __sparc__ && (defined __arch64__ || defined __sparc_v9__)
107
  __asm volatile ("membar #LoadLoad" : : : "memory");
108
#else
109
  __asm volatile ("" : : : "memory");
110
#endif
111
}
112
 
113
static inline void
114
swap (int *array, int a, int b)
115
{
116
  int val = array[a];
117
  array[a] = array[b];
118
  array[b] = val;
119
}
120
 
121
static inline int
122
choose_pivot (int *array, int lo, int hi)
123
{
124
  int mid = (lo + hi) / 2;
125
 
126
  if (array[mid] < array[lo])
127
    swap (array, lo, mid);
128
  if (array[hi] < array[mid])
129
    {
130
      swap (array, mid, hi);
131
      if (array[mid] < array[lo])
132
        swap (array, lo, mid);
133
    }
134
  return array[mid];
135
}
136
 
137
static inline int
138
partition (int *array, int lo, int hi)
139
{
140
  int pivot = choose_pivot (array, lo, hi);
141
  int left = lo;
142
  int right = hi;
143
 
144
  for (;;)
145
    {
146
      while (array[++left] < pivot);
147
      while (array[--right] > pivot);
148
      if (left >= right)
149
        break;
150
      swap (array, left, right);
151
    }
152
  return left;
153
}
154
 
155
static void
156
sort1 (int *array, int count)
157
{
158
  omp_lock_t lock;
159
  struct int_pair_stack global_stack;
160
  int busy = 1;
161
  int num_threads;
162
 
163
  omp_init_lock (&lock);
164
  init_int_pair_stack (&global_stack);
165
  #pragma omp parallel firstprivate (array, count)
166
  {
167
    int lo = 0, hi = 0, mid, next_lo, next_hi;
168
    bool idle = true;
169
    struct int_pair_stack local_stack;
170
 
171
    init_int_pair_stack (&local_stack);
172
    if (omp_get_thread_num () == 0)
173
      {
174
        num_threads = omp_get_num_threads ();
175
        hi = count - 1;
176
        idle = false;
177
      }
178
 
179
    for (;;)
180
      {
181
        if (hi - lo < THRESHOLD)
182
          {
183
            insertsort (array, lo, hi);
184
            lo = hi;
185
          }
186
        if (lo >= hi)
187
          {
188
            if (size_int_pair_stack (&local_stack) == 0)
189
              {
190
              again:
191
                omp_set_lock (&lock);
192
                if (size_int_pair_stack (&global_stack) == 0)
193
                  {
194
                    if (!idle)
195
                      busy--;
196
                    if (busy == 0)
197
                      {
198
                        omp_unset_lock (&lock);
199
                        break;
200
                      }
201
                    omp_unset_lock (&lock);
202
                    idle = true;
203
                    while (size_int_pair_stack (&global_stack) == 0
204
                           && busy)
205
                      busy_wait ();
206
                    goto again;
207
                  }
208
                if (idle)
209
                  busy++;
210
                pop_int_pair_stack (&global_stack, &lo, &hi);
211
                omp_unset_lock (&lock);
212
                idle = false;
213
              }
214
            else
215
              pop_int_pair_stack (&local_stack, &lo, &hi);
216
          }
217
 
218
        mid = partition (array, lo, hi);
219
        if (mid - lo < hi - mid)
220
          {
221
            next_lo = mid;
222
            next_hi = hi;
223
            hi = mid - 1;
224
          }
225
        else
226
          {
227
            next_lo = lo;
228
            next_hi = mid - 1;
229
            lo = mid;
230
          }
231
 
232
        if (next_hi - next_lo < THRESHOLD)
233
          insertsort (array, next_lo, next_hi);
234
        else
235
          {
236
            if (size_int_pair_stack (&global_stack) < num_threads - 1)
237
              {
238
                int size;
239
 
240
                omp_set_lock (&lock);
241
                size = size_int_pair_stack (&global_stack);
242
                if (size < num_threads - 1 && size < STACK_SIZE)
243
                  push_int_pair_stack (&global_stack, next_lo, next_hi);
244
                else
245
                  push_int_pair_stack (&local_stack, next_lo, next_hi);
246
                omp_unset_lock (&lock);
247
              }
248
            else
249
              push_int_pair_stack (&local_stack, next_lo, next_hi);
250
          }
251
      }
252
    }
253
  omp_destroy_lock (&lock);
254
}
255
 
256
static void
257
sort2_1 (int *array, int lo, int hi, int num_threads, int *busy)
258
{
259
  int mid;
260
 
261
  if (hi - lo < THRESHOLD)
262
    {
263
      insertsort (array, lo, hi);
264
      return;
265
    }
266
 
267
  mid = partition (array, lo, hi);
268
 
269
  if (*busy >= num_threads)
270
    {
271
      sort2_1 (array, lo, mid - 1, num_threads, busy);
272
      sort2_1 (array, mid, hi, num_threads, busy);
273
      return;
274
    }
275
 
276
  #pragma omp atomic
277
    *busy += 1;
278
 
279
  #pragma omp parallel num_threads (2) \
280
                       firstprivate (array, lo, hi, mid, num_threads, busy)
281
  {
282
    if (omp_get_thread_num () == 0)
283
      sort2_1 (array, lo, mid - 1, num_threads, busy);
284
    else
285
      {
286
        sort2_1 (array, mid, hi, num_threads, busy);
287
        #pragma omp atomic
288
          *busy -= 1;
289
      }
290
  }
291
}
292
 
293
static void
294
sort2 (int *array, int count)
295
{
296
  int num_threads;
297
  int busy = 1;
298
 
299
  #pragma omp parallel
300
    #pragma omp single nowait
301
      num_threads = omp_get_num_threads ();
302
 
303
  sort2_1 (array, 0, count - 1, num_threads, &busy);
304
}
305
 
306
#if _OPENMP >= 200805
307
static void
308
sort3_1 (int *array, int lo, int hi)
309
{
310
  int mid;
311
 
312
  if (hi - lo < THRESHOLD)
313
    {
314
      insertsort (array, lo, hi);
315
      return;
316
    }
317
 
318
  mid = partition (array, lo, hi);
319
  #pragma omp task
320
    sort3_1 (array, lo, mid - 1);
321
  sort3_1 (array, mid, hi);
322
}
323
 
324
static void
325
sort3 (int *array, int count)
326
{
327
  #pragma omp parallel
328
    #pragma omp single
329
      sort3_1 (array, 0, count - 1);
330
}
331
#endif
332
 
333
int
334
main (int argc, char **argv)
335
{
336
  int i, count = 1000000;
337
  double stime;
338
  int *unsorted, *sorted, num_threads;
339
  if (argc >= 2)
340
    count = strtoul (argv[1], NULL, 0);
341
 
342
  unsorted = malloc (count * sizeof (int));
343
  sorted = malloc (count * sizeof (int));
344
  if (unsorted == NULL || sorted == NULL)
345
    {
346
      puts ("allocation failure");
347
      exit (1);
348
    }
349
 
350
  srand (0xdeadbeef);
351
  for (i = 0; i < count; i++)
352
    unsorted[i] = rand ();
353
 
354
  omp_set_nested (1);
355
  omp_set_dynamic (0);
356
  #pragma omp parallel
357
    #pragma omp single nowait
358
      num_threads = omp_get_num_threads ();
359
  printf ("Threads: %d\n", num_threads);
360
 
361
  memcpy (sorted, unsorted, count * sizeof (int));
362
  stime = omp_get_wtime ();
363
  sort1 (sorted, count);
364
  verify ("sort1", stime, sorted, count);
365
 
366
  memcpy (sorted, unsorted, count * sizeof (int));
367
  stime = omp_get_wtime ();
368
  sort2 (sorted, count);
369
  verify ("sort2", stime, sorted, count);
370
 
371
#if _OPENMP >= 200805
372
  memcpy (sorted, unsorted, count * sizeof (int));
373
  stime = omp_get_wtime ();
374
  sort3 (sorted, count);
375
  verify ("sort3", stime, sorted, count);
376
#endif
377
 
378
  return 0;
379
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.