benchmarks/sort/sort_main.c

   1 // ****************************************************************************
   2 // sort benchmark from DARPA PERFECT TAV suite
   3 // ----------------------------------------------------------------------------
   4 #include "sort.h"
   5 #include "util.h"
   6 #include "dataset.h"
   7
   8
   9 // Need 7 times the input size for: input data, indices,
  10 // four copies, and buckets.
  11 FAKE_MALLOC_INIT( (8 * DATA_SIZE_SORT * TRIALS_SORT), radix )
  12
  13
  14 #if defined(USE_N_SQUARED_SORT)
  15 const char* algo = "N_SQUARED";
  16 #elif defined(USE_RADIX_SORT)
  17 const char* algo = "RADIX";
  18 #elif defined(USE_INSERTION_SORT)
  19 const char* algo = "INSERTION";
  20 #else
  21 const char* algo = "QUICKSORT";
  22 #endif
  23
  24
  25
  26 int main( int argc, char* argv[] )
  27 {
  28   int err;
  29
  30   int* index = fake_malloc_radix (sizeof(int) * DATA_SIZE_SORT * TRIALS_SORT);
  31   for(int trial = 0; trial < TRIALS_SORT; trial++)
  32     for ( int i = 0; i < DATA_SIZE_SORT; i++ )
  33       index[i + (DATA_SIZE_SORT * trial)] = i;
  34
  35 #ifdef PREALLOCATE
  36   // Access every element of input_data_sort to make sure it's in cache
  37   // (or at least that as much as possible of its beginning is).
  38   float sum = 0;
  39   for(int i = (DATA_SIZE_SORT * TRIALS_SORT)-1; i >= 0; i--) {
  40     sum += input_data_sort[i];
  41   }
  42   if(sum < 0.1)
  43     return 1;
  44
  45   const bool prealloc = true;
  46 #else
  47   const bool prealloc = false;
  48 #endif
  49
  50   setStats(1);
  51
  52 #define read_csr_safe(reg) ({ long __tmp = 0; \
  53   asm volatile ("csrr %0, " #reg : "+r"(__tmp)); \
  54   __tmp; })
  55
  56
  57   long cycles_total = 0;
  58   long instret_total = 0;
  59
  60   for(int i = 0; i < TRIALS_SORT; i++) {
  61     long cycles = read_csr_safe(cycle);
  62     long instret = read_csr_safe(instret);
  63
  64     float* input_data_trial = &input_data_sort[DATA_SIZE_SORT * i];
  65     int* index_trial = &index[DATA_SIZE_SORT * i];
  66
  67 #if defined(USE_N_SQUARED_SORT)
  68     err = n_squared_sort ( input_data_trial, index_trial, DATA_SIZE_SORT );
  69 #elif defined(USE_RADIX_SORT)
  70     err = radix_sort_tuples ( (int *) input_data_trial, index_trial, DATA_SIZE_SORT, RADIX_BITS );
  71 #elif defined(USE_INSERTION_SORT)
  72     err = insertion_sort ( input_data_trial, index_trial, DATA_SIZE_SORT );
  73 #else
  74     err = quicksort ( input_data_trial, index_trial, DATA_SIZE_SORT );
  75 #endif
  76
  77     cycles_total  += read_csr_safe(cycle) - cycles;
  78     instret_total += read_csr_safe(instret) - instret;
  79   }
  80
  81   setStats(0);
  82
  83   printf("DONE SORTING.\n", 0);
  84
  85   // Validate results
  86   err = 0;
  87   for(int trial = 0; trial < TRIALS_SORT; trial++)
  88   {
  89     float* input_data_trial = &input_data_sort[DATA_SIZE_SORT * trial];
  90     int* index_trial = &index[DATA_SIZE_SORT * trial];
  91
  92     for(int i = 0; i < DATA_SIZE_SORT-1; i++)
  93     {
  94       if((unsigned int) input_data_trial[i] > (unsigned int) input_data_trial[i+1])
  95       {
  96         err = i;
  97         for(int j = 0; j < DATA_SIZE_SORT; j++)
  98           printf("TRIAL %d, element %d:\t%d\n", trial, j, input_data_trial[j]);
  99         break;
 100       }
 101     }
 102   }
 103
 104   printf("sort_cycles  = %ld\n", cycles_total/TRIALS_SORT);
 105   printf("sort_instret = %d\n", instret_total/TRIALS_SORT);
 106   printf("sort_size    = %d\n", DATA_SIZE_SORT);
 107   printf("sort_trials  = %d\n", TRIALS_SORT);
 108   printf("sort_algo    = %s\n", algo);
 109   printf("sort_radix_bits = %d\n", RADIX_BITS);
 110   printf("sort_prealloc = %s\n", prealloc ? "true" : "false");
 111   printf("sort_err = %d\n", err);
 112
 113   return err;
 114 }
 115
 116
 117