fee68e56dca7cdedc4f8716cbfb0b48069a65227
1 // See LICENSE for license details.
3 //**************************************************************************
5 //--------------------------------------------------------------------------
7 // This benchmark uses quicksort to sort an array of integers. The
8 // implementation is largely adapted from Numerical Recipes for C. The
9 // input data (and reference data) should be generated using the
10 // qsort_gendata.pl perl script and dumped to a file named
11 // dataset1.h The smips-gcc toolchain does not support system calls
12 // so printf's can only be used on a host system, not on the smips
13 // processor simulator itself. You should not change anything except
14 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
20 //--------------------------------------------------------------------------
21 // Input/Reference Data
23 #define type unsigned int
27 #define BASE (1 << LOG_BASE)
29 void sort(size_t n
, type
* arrIn
, type
* scratchIn
)
33 size_t *bucket
= buckets
;
35 type
*arr
= arrIn
, *scratch
= scratchIn
, *p
;
38 while (log_exp
< CHAR_BIT
* sizeof(type
))
40 for (b
= bucket
; b
< bucket
+ BASE
; b
++)
43 for (p
= arr
; p
< &arr
[n
-3]; p
+= 4)
49 __sync_fetch_and_add(&bucket
[(a0
>> log_exp
) % BASE
], 1);
50 __sync_fetch_and_add(&bucket
[(a1
>> log_exp
) % BASE
], 1);
51 __sync_fetch_and_add(&bucket
[(a2
>> log_exp
) % BASE
], 1);
52 __sync_fetch_and_add(&bucket
[(a3
>> log_exp
) % BASE
], 1);
54 for ( ; p
< &arr
[n
]; p
++)
55 bucket
[(*p
>> log_exp
) % BASE
]++;
57 size_t prev
= bucket
[0];
58 prev
+= __sync_fetch_and_add(&bucket
[1], prev
);
59 for (b
= &bucket
[2]; b
< bucket
+ BASE
; b
+= 2)
61 prev
+= __sync_fetch_and_add(&b
[0], prev
);
62 prev
+= __sync_fetch_and_add(&b
[1], prev
);
64 static_assert(BASE
% 2 == 0);
66 for (p
= &arr
[n
-1]; p
>= &arr
[3]; p
-= 4)
72 size_t* pb0
= &bucket
[(a0
>> log_exp
) % BASE
];
73 size_t* pb1
= &bucket
[(a1
>> log_exp
) % BASE
];
74 size_t* pb2
= &bucket
[(a2
>> log_exp
) % BASE
];
75 size_t* pb3
= &bucket
[(a3
>> log_exp
) % BASE
];
76 type
* s0
= scratch
+ __sync_fetch_and_add(pb0
, -1);
77 type
* s1
= scratch
+ __sync_fetch_and_add(pb1
, -1);
78 type
* s2
= scratch
+ __sync_fetch_and_add(pb2
, -1);
79 type
* s3
= scratch
+ __sync_fetch_and_add(pb3
, -1);
85 for ( ; p
>= &arr
[0]; p
--)
86 scratch
[--bucket
[(*p
>> log_exp
) % BASE
]] = *p
;
95 memcpy(arr
, scratch
, n
*sizeof(type
));
98 //--------------------------------------------------------------------------
101 int main( int argc
, char* argv
[] )
103 static type scratch
[DATA_SIZE
];
104 // Output the input array
105 printArray( "input", DATA_SIZE
, input_data
);
106 printArray( "verify", DATA_SIZE
, verify_data
);
109 // If needed we preallocate everything in the caches
110 sort(DATA_SIZE
, verify_data
, scratch
);
111 if (verify(DATA_SIZE
, input_data
, input_data
))
117 sort(DATA_SIZE
, input_data
, scratch
);
120 // Print out the results
121 printArray( "test", DATA_SIZE
, input_data
);
124 return verify( DATA_SIZE
, input_data
, verify_data
);