29b46c53930c3d12eeaff1cd6498799851bb8856
1 // See LICENSE for license details.
3 // ****************************************************************************
4 // sort benchmark from DARPA PERFECT TAV suite
5 // ----------------------------------------------------------------------------
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
)
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";
23 const char* algo
= "QUICKSORT";
28 int main( int argc
, char* argv
[] )
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
;
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).
41 for(int i
= (DATA_SIZE_SORT
* TRIALS_SORT
)-1; i
>= 0; i
--) {
42 sum
+= input_data_sort
[i
];
47 const bool prealloc
= true;
49 const bool prealloc
= false;
54 #define read_csr_safe(reg) ({ long __tmp = 0; \
55 asm volatile ("csrr %0, " #reg : "+r"(__tmp)); \
59 long cycles_total
= 0;
60 long instret_total
= 0;
62 for(int i
= 0; i
< TRIALS_SORT
; i
++) {
63 long cycles
= read_csr_safe(cycle
);
64 long instret
= read_csr_safe(instret
);
66 float* input_data_trial
= &input_data_sort
[DATA_SIZE_SORT
* i
];
67 int* index_trial
= &index
[DATA_SIZE_SORT
* i
];
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
);
76 err
= quicksort ( input_data_trial
, index_trial
, DATA_SIZE_SORT
);
79 cycles_total
+= read_csr_safe(cycle
) - cycles
;
80 instret_total
+= read_csr_safe(instret
) - instret
;
85 printf("DONE SORTING.\n", 0);
89 for(int trial
= 0; trial
< TRIALS_SORT
; trial
++)
91 float* input_data_trial
= &input_data_sort
[DATA_SIZE_SORT
* trial
];
92 int* index_trial
= &index
[DATA_SIZE_SORT
* trial
];
94 for(int i
= 0; i
< DATA_SIZE_SORT
-1; i
++)
96 if((unsigned int) input_data_trial
[i
] > (unsigned int) input_data_trial
[i
+1])
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
]);
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
);