benchmarks/qsort/qsort_main.c

   1 //**************************************************************************
   2 // Quicksort benchmark
   3 //--------------------------------------------------------------------------
   4 //
   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.
  13
  14 int ncores = 1;
  15 #include "util.h"
  16
  17 //--------------------------------------------------------------------------
  18 // Macros
  19
  20 // Set HOST_DEBUG to 1 if you are going to compile this for a host
  21 // machine (ie Athena/Linux) for debug purposes and set HOST_DEBUG
  22 // to 0 if you are compiling with the smips-gcc toolchain.
  23
  24 #ifndef HOST_DEBUG
  25 #define HOST_DEBUG 0
  26 #endif
  27
  28 // Set PREALLOCATE to 1 if you want to preallocate the benchmark
  29 // function before starting stats. If you have instruction/data
  30 // caches and you don't want to count the overhead of misses, then
  31 // you will need to use preallocation.
  32
  33 #ifndef PREALLOCATE
  34 #define PREALLOCATE 0
  35 #endif
  36
  37 // Set SET_STATS to 1 if you want to carve out the piece that actually
  38 // does the computation.
  39
  40 #ifndef SET_STATS
  41 #define SET_STATS 0
  42 #endif
  43
  44 // The INSERTION_THRESHOLD is the size of the subarray when the
  45 // algorithm switches to using an insertion sort instead of
  46 // quick sort.
  47
  48 #define INSERTION_THRESHOLD 7
  49
  50 // NSTACK is the required auxiliary storage.
  51 // It must be at least 2*lg(DATA_SIZE)
  52
  53 #define NSTACK 50
  54
  55 // Swap macro for swapping two values.
  56
  57 #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
  58
  59 //--------------------------------------------------------------------------
  60 // Input/Reference Data
  61
  62 #include "dataset1.h"
  63
  64 //--------------------------------------------------------------------------
  65 // Helper functions
  66
  67 int verify( int n, int test[], int correct[] )
  68 {
  69   int i;
  70   for ( i = 0; i < n; i++ ) {
  71     if ( test[i] != correct[i] ) {
  72       return 2;
  73     }
  74   }
  75   return 1;
  76 }
  77
  78 #if HOST_DEBUG
  79 void printArray( char name[], int n, int arr[] )
  80 {
  81   int i;
  82   printf( " %10s :", name );
  83   for ( i = 0; i < n; i++ )
  84     printf( " %3d ", arr[i] );
  85   printf( "\n" );
  86 }
  87 #endif
  88
  89 void setStats( int enable )
  90 {
  91 #if ( !HOST_DEBUG && SET_STATS )
  92   asm( "mtpcr %0, cr10" : : "r" (enable) );
  93 #endif
  94 }
  95
  96 //--------------------------------------------------------------------------
  97 // Quicksort function
  98
  99 void sort( int n, int arr[] )
 100 {
 101   int i,j,k;
 102   int ir = n;
 103   int l = 1;
 104   int jstack = 0;
 105   int a, temp;
 106
 107   int istack[NSTACK];
 108
 109   for (;;) {
 110
 111 #if HOST_DEBUG
 112     printArray( "", n, arr );
 113 #endif
 114
 115     // Insertion sort when subarray small enough.
 116     if ( ir-l < INSERTION_THRESHOLD ) {
 117
 118       for ( j = l+1; j <= ir; j++ ) {
 119         a = arr[j-1];
 120         for ( i = j-1; i >= l; i-- ) {
 121           if ( arr[i-1] <= a ) break;
 122           arr[i] = arr[i-1];
 123         }
 124         arr[i] = a;
 125       }
 126
 127       if ( jstack == 0 ) break;
 128
 129       // Pop stack and begin a new round of partitioning.
 130       ir = istack[jstack--];
 131       l = istack[jstack--];
 132
 133     }
 134     else {
 135
 136       // Choose median of left, center, and right elements as
 137       // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
 138
 139       k = (l+ir) >> 1;
 140       SWAP(arr[k-1],arr[l])
 141       if ( arr[l-1] > arr[ir-1] ) {
 142         SWAP(arr[l-1],arr[ir-1])
 143       }
 144       if ( arr[l] > arr[ir-1] ) {
 145         SWAP(arr[l],arr[ir-1])
 146       }
 147       if ( arr[l-1] > arr[l] ) {
 148         SWAP(arr[l-1],arr[l])
 149       }
 150
 151       // Initialize pointers for partitioning.
 152       i = l+1;
 153       j = ir;
 154
 155       // Partitioning element.
 156       a = arr[l];
 157
 158       for (;;) {                       // Beginning of innermost loop.
 159         do i++; while (arr[i-1] < a);  // Scan up to find element > a.
 160         do j--; while (arr[j-1] > a);  // Scan down to find element < a.
 161         if (j < i) break;              // Pointers crossed. Partitioning complete.
 162         SWAP(arr[i-1],arr[j-1]);       // Exchange elements.
 163       }                                // End of innermost loop.
 164
 165       // Insert partitioning element.
 166       arr[l] = arr[j-1];
 167       arr[j-1] = a;
 168       jstack += 2;
 169
 170       // Push pointers to larger subarray on stack,
 171       // process smaller subarray immediately.
 172
 173 #if HOST_DEBUG
 174       if ( jstack > NSTACK ) { printf("NSTACK too small in sort.\n"); exit(1); }
 175 #endif
 176
 177       if ( ir-i+1 >= j-l ) {
 178         istack[jstack]   = ir;
 179         istack[jstack-1] = i;
 180         ir = j-1;
 181       }
 182       else {
 183         istack[jstack]   = j-1;
 184         istack[jstack-1] = l;
 185         l = i;
 186       }
 187     }
 188
 189   }
 190
 191 }
 192
 193 //--------------------------------------------------------------------------
 194 // Main
 195
 196 int main( int argc, char* argv[] )
 197 {
 198
 199   // Output the input array
 200
 201 #if HOST_DEBUG
 202   printArray( "input", DATA_SIZE, input_data );
 203   printArray( "verify", DATA_SIZE, verify_data );
 204 #endif
 205
 206   // If needed we preallocate everything in the caches
 207
 208 #if PREALLOCATE
 209   sort( DATA_SIZE, input_data );
 210 #endif
 211
 212   // Do the sort
 213
 214   setStats(1);
 215   sort( DATA_SIZE, input_data );
 216   setStats(0);
 217
 218   // Print out the results
 219
 220 #if HOST_DEBUG
 221   printArray( "test", DATA_SIZE, input_data );
 222 #endif
 223
 224   // Check the results
 225
 226   finishTest(verify( DATA_SIZE, input_data, verify_data ));
 227
 228 }