benchmarks/sort/sort_main.c

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