1 //**************************************************************************
3 //--------------------------------------------------------------------------
5 // This benchmark uses quicksort to sort an array of integers. The
6 // implementation is largely adapted from Numerical Recipes for C. The
7 // input data (and reference data) should be generated using the
8 // qsort_gendata.pl perl script and dumped to a file named
9 // dataset1.h The smips-gcc toolchain does not support system calls
10 // so printf's can only be used on a host system, not on the smips
11 // processor simulator itself. You should not change anything except
12 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
18 //--------------------------------------------------------------------------
19 // Input/Reference Data
21 #define type unsigned int
25 #define BASE (1 << LOG_BASE)
27 void sort(size_t n
, type
* arrIn
, type
* scratchIn
)
31 size_t *bucket
= buckets
;
33 type
*arr
= arrIn
, *scratch
= scratchIn
, *p
;
36 while (log_exp
< CHAR_BIT
* sizeof(type
))
38 for (b
= bucket
; b
< bucket
+ BASE
; b
++)
41 for (p
= arr
; p
< &arr
[n
-3]; p
+= 4)
47 __sync_fetch_and_add(&bucket
[(a0
>> log_exp
) % BASE
], 1);
48 __sync_fetch_and_add(&bucket
[(a1
>> log_exp
) % BASE
], 1);
49 __sync_fetch_and_add(&bucket
[(a2
>> log_exp
) % BASE
], 1);
50 __sync_fetch_and_add(&bucket
[(a3
>> log_exp
) % BASE
], 1);
52 for ( ; p
< &arr
[n
]; p
++)
53 bucket
[(*p
>> log_exp
) % BASE
]++;
55 size_t prev
= bucket
[0];
56 prev
+= __sync_fetch_and_add(&bucket
[1], prev
);
57 for (b
= &bucket
[2]; b
< bucket
+ BASE
; b
+= 2)
59 prev
+= __sync_fetch_and_add(&b
[0], prev
);
60 prev
+= __sync_fetch_and_add(&b
[1], prev
);
62 static_assert(BASE
% 2 == 0);
64 for (p
= &arr
[n
-1]; p
>= &arr
[3]; p
-= 4)
70 size_t* pb0
= &bucket
[(a0
>> log_exp
) % BASE
];
71 size_t* pb1
= &bucket
[(a1
>> log_exp
) % BASE
];
72 size_t* pb2
= &bucket
[(a2
>> log_exp
) % BASE
];
73 size_t* pb3
= &bucket
[(a3
>> log_exp
) % BASE
];
74 type
* s0
= scratch
+ __sync_fetch_and_add(pb0
, -1);
75 type
* s1
= scratch
+ __sync_fetch_and_add(pb1
, -1);
76 type
* s2
= scratch
+ __sync_fetch_and_add(pb2
, -1);
77 type
* s3
= scratch
+ __sync_fetch_and_add(pb3
, -1);
83 for ( ; p
>= &arr
[0]; p
--)
84 scratch
[--bucket
[(*p
>> log_exp
) % BASE
]] = *p
;
93 memcpy(arr
, scratch
, n
*sizeof(type
));
96 //--------------------------------------------------------------------------
99 int main( int argc
, char* argv
[] )
101 static type scratch
[DATA_SIZE
];
102 // Output the input array
103 printArray( "input", DATA_SIZE
, input_data
);
104 printArray( "verify", DATA_SIZE
, verify_data
);
107 // If needed we preallocate everything in the caches
108 sort(DATA_SIZE
, verify_data
, scratch
);
109 if (verify(DATA_SIZE
, input_data
, input_data
))
115 sort(DATA_SIZE
, input_data
, scratch
);
118 // Print out the results
119 printArray( "test", DATA_SIZE
, input_data
);
122 return verify( DATA_SIZE
, input_data
, verify_data
);