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.
14 //--------------------------------------------------------------------------
17 // Set HOST_DEBUG to 1 if you are going to compile this for a host
18 // machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
19 // to 0 if you are compiling with the smips-gcc toolchain.
25 // Set PREALLOCATE to 1 if you want to preallocate the benchmark
26 // function before starting stats. If you have instruction/data
27 // caches and you don't want to count the overhead of misses, then
28 // you will need to use preallocation.
34 // Set SET_STATS to 1 if you want to carve out the piece that actually
35 // does the computation.
41 // The INSERTION_THRESHOLD is the size of the subarray when the
42 // algorithm switches to using an insertion sort instead of
45 #define INSERTION_THRESHOLD 7
47 // NSTACK is the required auxiliary storage.
48 // It must be at least 2*lg(DATA_SIZE)
52 // Swap macro for swapping two values.
54 #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
56 //--------------------------------------------------------------------------
57 // Input/Reference Data
61 //--------------------------------------------------------------------------
64 int verify( int n
, int test
[], int correct
[] )
67 for ( i
= 0; i
< n
; i
++ ) {
68 if ( test
[i
] != correct
[i
] ) {
76 void printArray( char name
[], int n
, int arr
[] )
79 printf( " %10s :", name
);
80 for ( i
= 0; i
< n
; i
++ )
81 printf( " %3d ", arr
[i
] );
86 void finishTest( int toHostValue
)
89 if ( toHostValue
== 1 )
90 printf( "*** PASSED ***\n" );
92 printf( "*** FAILED *** (tohost = %d)\n", toHostValue
);
95 asm( "mtpcr %0, cr30" : : "r" (toHostValue
) );
100 void setStats( int enable
)
102 #if ( !HOST_DEBUG && SET_STATS )
103 asm( "mtpcr %0, cr10" : : "r" (enable
) );
107 //--------------------------------------------------------------------------
108 // Quicksort function
110 void sort( int n
, int arr
[] )
123 printArray( "", n
, arr
);
126 // Insertion sort when subarray small enough.
127 if ( ir
-l
< INSERTION_THRESHOLD
) {
129 for ( j
= l
+1; j
<= ir
; j
++ ) {
131 for ( i
= j
-1; i
>= l
; i
-- ) {
132 if ( arr
[i
-1] <= a
) break;
138 if ( jstack
== 0 ) break;
140 // Pop stack and begin a new round of partitioning.
141 ir
= istack
[jstack
--];
142 l
= istack
[jstack
--];
147 // Choose median of left, center, and right elements as
148 // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
151 SWAP(arr
[k
-1],arr
[l
])
152 if ( arr
[l
-1] > arr
[ir
-1] ) {
153 SWAP(arr
[l
-1],arr
[ir
-1])
155 if ( arr
[l
] > arr
[ir
-1] ) {
156 SWAP(arr
[l
],arr
[ir
-1])
158 if ( arr
[l
-1] > arr
[l
] ) {
159 SWAP(arr
[l
-1],arr
[l
])
162 // Initialize pointers for partitioning.
166 // Partitioning element.
169 for (;;) { // Beginning of innermost loop.
170 do i
++; while (arr
[i
-1] < a
); // Scan up to find element > a.
171 do j
--; while (arr
[j
-1] > a
); // Scan down to find element < a.
172 if (j
< i
) break; // Pointers crossed. Partitioning complete.
173 SWAP(arr
[i
-1],arr
[j
-1]); // Exchange elements.
174 } // End of innermost loop.
176 // Insert partitioning element.
181 // Push pointers to larger subarray on stack,
182 // process smaller subarray immediately.
185 if ( jstack
> NSTACK
) { printf("NSTACK too small in sort.\n"); exit(1); }
188 if ( ir
-i
+1 >= j
-l
) {
190 istack
[jstack
-1] = i
;
194 istack
[jstack
] = j
-1;
195 istack
[jstack
-1] = l
;
204 //--------------------------------------------------------------------------
207 int main( int argc
, char* argv
[] )
210 // Output the input array
213 printArray( "input", DATA_SIZE
, input_data
);
214 printArray( "verify", DATA_SIZE
, verify_data
);
217 // If needed we preallocate everything in the caches
220 sort( DATA_SIZE
, input_data
);
226 sort( DATA_SIZE
, input_data
);
229 // Print out the results
232 printArray( "test", DATA_SIZE
, input_data
);
237 finishTest(verify( DATA_SIZE
, input_data
, verify_data
));