1 // ****************************************************************************
2 // sort benchmark from DARPA PERFECT TAV suite
3 // ----------------------------------------------------------------------------
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
)
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";
21 const char* algo
= "QUICKSORT";
26 int main( int argc
, char* argv
[] )
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
;
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).
39 for(int i
= (DATA_SIZE_SORT
* TRIALS_SORT
)-1; i
>= 0; i
--) {
40 sum
+= input_data_sort
[i
];
45 const bool prealloc
= true;
47 const bool prealloc
= false;
52 #define read_csr_safe(reg) ({ long __tmp = 0; \
53 asm volatile ("csrr %0, " #reg : "+r"(__tmp)); \
57 long cycles_total
= 0;
58 long instret_total
= 0;
60 for(int i
= 0; i
< TRIALS_SORT
; i
++) {
61 long cycles
= read_csr_safe(cycle
);
62 long instret
= read_csr_safe(instret
);
64 float* input_data_trial
= &input_data_sort
[DATA_SIZE_SORT
* i
];
65 int* index_trial
= &index
[DATA_SIZE_SORT
* i
];
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
);
74 err
= quicksort ( input_data_trial
, index_trial
, DATA_SIZE_SORT
);
77 cycles_total
+= read_csr_safe(cycle
) - cycles
;
78 instret_total
+= read_csr_safe(instret
) - instret
;
83 printf("DONE SORTING.\n", 0);
87 for(int trial
= 0; trial
< TRIALS_SORT
; trial
++)
89 float* input_data_trial
= &input_data_sort
[DATA_SIZE_SORT
* trial
];
90 int* index_trial
= &index
[DATA_SIZE_SORT
* trial
];
92 for(int i
= 0; i
< DATA_SIZE_SORT
-1; i
++)
94 if((unsigned int) input_data_trial
[i
] > (unsigned int) input_data_trial
[i
+1])
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
]);
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
);