From 3a7405d21a359924ff87a8143a8def4392ececf1 Mon Sep 17 00:00:00 2001 From: Eric Love Date: Sat, 22 Feb 2014 17:13:57 -0800 Subject: [PATCH] Sort fixes: support for repeated trials. --- benchmarks/sort/sort.h | 2 + benchmarks/sort/sort_gendata.scala | 14 +++-- benchmarks/sort/sort_main.c | 84 +++++++++++++++++++----------- 3 files changed, 65 insertions(+), 35 deletions(-) diff --git a/benchmarks/sort/sort.h b/benchmarks/sort/sort.h index 326d0de..517adcf 100644 --- a/benchmarks/sort/sort.h +++ b/benchmarks/sort/sort.h @@ -2,6 +2,8 @@ #include #include +#define USE_N_SQUARED_SORT + #define FAKE_MALLOC_INIT(words, name) \ uint32_t heap_##name[words]; \ const size_t max_alloc_##name = (words) * sizeof(uint32_t); \ diff --git a/benchmarks/sort/sort_gendata.scala b/benchmarks/sort/sort_gendata.scala index 820dbc8..2f44074 100755 --- a/benchmarks/sort/sort_gendata.scala +++ b/benchmarks/sort/sort_gendata.scala @@ -2,7 +2,13 @@ import scala.util.Sorting +if(args.size < 2) { + println("Usage: sort_gendata <# elements> <# trials>") + System.exit(1) +} + val size = args(0).toInt +val trials = args(1).toInt def rand_array(size: Int) = { var r = new scala.util.Random @@ -17,10 +23,8 @@ def print_array(name: String, size: Int, arr: Array[Float]) { } println("#define DATA_SIZE_SORT " + size) +println("#define TRIALS_SORT " + trials) -val a = rand_array(size) -val sorted = a.clone() -Sorting.quickSort(sorted) +val a = rand_array(size * trials) -print_array("input_data_sort", size, a) -print_array("verify_data_sort", size, sorted) +print_array("input_data_sort", size * trials, a) diff --git a/benchmarks/sort/sort_main.c b/benchmarks/sort/sort_main.c index a4df38d..15cb766 100644 --- a/benchmarks/sort/sort_main.c +++ b/benchmarks/sort/sort_main.c @@ -5,25 +5,38 @@ #include "util.h" #include "dataset.h" -#define USE_RADIX_SORT // Need 7 times the input size for: input data, indices, // four copies, and buckets. -FAKE_MALLOC_INIT( (8 * DATA_SIZE_SORT), radix ) +FAKE_MALLOC_INIT( (8 * DATA_SIZE_SORT * TRIALS_SORT), radix ) + + +#if defined(USE_N_SQUARED_SORT) +const char* algo = "N_SQUARED"; +#elif defined(USE_RADIX_SORT) +const char* algo = "RADIX"; +#elif defined(USE_INSERTION_SORT) +const char* algo = "INSERTION"; +#else +const char* algo = "QUICKSORT"; +#endif + + int main( int argc, char* argv[] ) { int err; - int* index = fake_malloc_radix (sizeof(int) * DATA_SIZE_SORT); - for ( int i = 0; i < DATA_SIZE_SORT; i++ ) - index[i] = i; + int* index = fake_malloc_radix (sizeof(int) * DATA_SIZE_SORT * TRIALS_SORT); + for(int trial = 0; trial < TRIALS_SORT; trial++) + for ( int i = 0; i < DATA_SIZE_SORT; i++ ) + index[i + (DATA_SIZE_SORT * trial)] = i; #ifdef PREALLOCATE // Access every element of input_data_sort to make sure it's in cache // (or at least that as much as possible of its beginning is). float sum = 0; - for(int i = DATA_SIZE_SORT-1; i >= 0; i--) { + for(int i = (DATA_SIZE_SORT * TRIALS_SORT)-1; i >= 0; i--) { sum += input_data_sort[i]; } if(sum < 0.1) @@ -41,50 +54,61 @@ int main( int argc, char* argv[] ) __tmp; }) - long cycles = read_csr_safe(cycle); - long instret = read_csr_safe(instret); + long cycles_total = 0; + long instret_total = 0; + + for(int i = 0; i < TRIALS_SORT; i++) { + long cycles = read_csr_safe(cycle); + long instret = read_csr_safe(instret); + + float* input_data_trial = &input_data_sort[DATA_SIZE_SORT * i]; + int* index_trial = &index[DATA_SIZE_SORT * i]; - // Do sorting #if defined(USE_N_SQUARED_SORT) - const char* algo = "N_SQUARED"; - err = n_squared_sort ( input_data_sort, index, DATA_SIZE_SORT ); + err = n_squared_sort ( input_data_trial, index_trial, DATA_SIZE_SORT ); #elif defined(USE_RADIX_SORT) - const char* algo = "RADIX"; - err = radix_sort_tuples ( (int *) input_data_sort, index, DATA_SIZE_SORT, RADIX_BITS ); + err = radix_sort_tuples ( (int *) input_data_trial, index_trial, DATA_SIZE_SORT, RADIX_BITS ); #elif defined(USE_INSERTION_SORT) - const char* algo = "INSERTION"; - err = insertion_sort ( input_data_sort, index, DATA_SIZE_SORT ); + err = insertion_sort ( input_data_trial, index_trial, DATA_SIZE_SORT ); #else - const char* algo = "QUICKSORT"; - err = quicksort ( input_data_sort, index, DATA_SIZE_SORT ); + err = quicksort ( input_data_trial, index_trial, DATA_SIZE_SORT ); #endif - - cycles = read_csr_safe(cycle) - cycles; - instret = read_csr_safe(instret) - instret; + + cycles_total += read_csr_safe(cycle) - cycles; + instret_total += read_csr_safe(instret) - instret; + } setStats(0); - // Validate result + printf("DONE SORTING.\n", 0); + + // Validate results err = 0; - for(int i = 0; i < DATA_SIZE_SORT-1; i++) + for(int trial = 0; trial < TRIALS_SORT; trial++) { - if((unsigned int) input_data_sort[i] > (unsigned int) input_data_sort[i+1]) + float* input_data_trial = &input_data_sort[DATA_SIZE_SORT * trial]; + int* index_trial = &index[DATA_SIZE_SORT * trial]; + + for(int i = 0; i < DATA_SIZE_SORT-1; i++) { - err = i; - for(int j = 0; j < DATA_SIZE_SORT; j++) - printf("%d:\t%d\n", j, input_data_sort[j]); - break; + if((unsigned int) input_data_trial[i] > (unsigned int) input_data_trial[i+1]) + { + err = i; + for(int j = 0; j < DATA_SIZE_SORT; j++) + printf("TRIAL %d, element %d:\t%d\n", trial, j, input_data_trial[j]); + break; + } } } - /*printf("sort_cycles = %ld\n", cycles); - printf("sort_instret = %d\n", instret); + printf("sort_cycles = %ld\n", cycles_total/TRIALS_SORT); + printf("sort_instret = %d\n", instret_total/TRIALS_SORT); printf("sort_size = %d\n", DATA_SIZE_SORT); + printf("sort_trials = %d\n", TRIALS_SORT); printf("sort_algo = %s\n", algo); printf("sort_radix_bits = %d\n", RADIX_BITS); printf("sort_prealloc = %s\n", prealloc ? "true" : "false"); printf("sort_err = %d\n", err); - */ return err; } -- 2.30.2