diff options
author | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2019-01-19 13:33:57 +0100 |
---|---|---|
committer | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2019-01-19 13:33:57 +0100 |
commit | 6c5df17a302e99dec62aa749ffc30745cc7679a4 (patch) | |
tree | 3b0509425b547709fb44645bc375c7faa4595e56 /test | |
parent | caa53a3dce35e53ed913557f30aef1f063cf67c0 (diff) | |
download | compcert-kvx-6c5df17a302e99dec62aa749ffc30745cc7679a4.tar.gz compcert-kvx-6c5df17a302e99dec62aa749ffc30745cc7679a4.zip |
quicksort
Diffstat (limited to 'test')
-rw-r--r-- | test/monniaux/cycles.h | 26 | ||||
-rw-r--r-- | test/monniaux/mod_int_mat/int_mat_run.c | 28 | ||||
-rw-r--r-- | test/monniaux/quicksort/Makefile | 40 | ||||
-rw-r--r-- | test/monniaux/quicksort/quicksort.c | 42 | ||||
-rw-r--r-- | test/monniaux/quicksort/quicksort.h | 7 | ||||
-rw-r--r-- | test/monniaux/quicksort/quicksort_run.c | 22 |
6 files changed, 138 insertions, 27 deletions
diff --git a/test/monniaux/cycles.h b/test/monniaux/cycles.h new file mode 100644 index 00000000..212e65fc --- /dev/null +++ b/test/monniaux/cycles.h @@ -0,0 +1,26 @@ +typedef uint64_t cycle_t; + +#ifdef __K1C__ +#include <mppa_bare_runtime/k1c/registers.h> +static inline void cycle_count_config(void) +{ + /* config pmc for cycle count */ + uint64_t pmc_value = __builtin_k1_get(K1_SFR_PMC); + + pmc_value &= ~(0xfULL); + __builtin_k1_set(K1_SFR_PMC, pmc_value); +} + +static inline uint64_t get_cycle(void) +{ + return __builtin_k1_get(K1_SFR_PM0); +} +#else +static inline void cycle_count_config(void) { } +#ifdef __x86_64__ +#include <x86intrin.h> +static inline cycle_t get_cycle(void) { return __rdtsc(); } +#else +static inline cycle_t get_cycle(void) { return 0; } +#endif +#endif diff --git a/test/monniaux/mod_int_mat/int_mat_run.c b/test/monniaux/mod_int_mat/int_mat_run.c index 42cb54fb..f3955345 100644 --- a/test/monniaux/mod_int_mat/int_mat_run.c +++ b/test/monniaux/mod_int_mat/int_mat_run.c @@ -3,33 +3,7 @@ #include <stdio.h> #include <inttypes.h> #include "modint.h" - -typedef uint64_t cycle_t; - -#ifdef __K1C__ -#include <mppa_bare_runtime/k1c/registers.h> -static inline void cycle_count_config(void) -{ - /* config pmc for cycle count */ - uint64_t pmc_value = __builtin_k1_get(K1_SFR_PMC); - - pmc_value &= ~(0xfULL); - __builtin_k1_set(K1_SFR_PMC, pmc_value); -} - -static inline uint64_t get_cycle(void) -{ - return __builtin_k1_get(K1_SFR_PM0); -} -#else -static inline void cycle_count_config(void) { } -#ifdef __x86_64__ -#include <x86intrin.h> -static inline cycle_t get_cycle(void) { return __rdtsc(); } -#else -static inline cycle_t get_cycle(void) { return 0; } -#endif -#endif +#include "../cycles.h" int main() { const unsigned m = 40, n = 21, p = 30; diff --git a/test/monniaux/quicksort/Makefile b/test/monniaux/quicksort/Makefile new file mode 100644 index 00000000..1d8913dd --- /dev/null +++ b/test/monniaux/quicksort/Makefile @@ -0,0 +1,40 @@ +CFLAGS=-Wall -O3 +K1C_CC=k1-mbr-gcc +K1C_CFLAGS=-Wall -O3 -std=c99 +K1C_CCOMP=../../../ccomp +K1C_CCOMPFLAGS=-Wall -O3 -D__thread= -D__int128=int + +PRODUCTS=quicksort.host quicksort.gcc.k1c.out quicksort.ccomp.k1c.out quicksort.ccomp.k1c.s quicksort.gcc.k1c.s quicksort.gcc.k1c quicksort.ccomp.k1c + +all: $(PRODUCTS) + +%.gcc.k1c.s: %.c + $(K1C_CC) $(K1C_CFLAGS) -S $< -o $@ + +%.gcc.k1c.o: %.gcc.k1c.s + $(K1C_CC) $(K1C_CFLAGS) -c $< -o $@ + +%.ccomp.k1c.s: %.c + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) -S $< -o $@ + +%.ccomp.k1c.o: %.ccomp.k1c.s + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) -c $< -o $@ + +quicksort.host: quicksort.c quicksort_run.c quicksort.h + $(CC) $(CFLAGS) quicksort.c quicksort_run.c -o $@ + +quicksort.gcc.k1c.s quicksort.ccomp.k1c.s quicksort_run.gcc.k1c.s: quicksort.h + +quicksort.gcc.k1c: quicksort.gcc.k1c.o quicksort_run.gcc.k1c.o + $(K1C_CC) $(K1C_CFLAGS) $+ -o $@ + +quicksort.ccomp.k1c: quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) $+ -o $@ + +%.k1c.out: %.k1c + k1-cluster --cycle-based -- $< | tee $@ + +clean: + $(RM) -f $(PRODUCTS) quicksort.gcc.k1c.o quicksort.ccomp.k1c.o quicksort_run.gcc.k1c.o + +.PHONY: clean diff --git a/test/monniaux/quicksort/quicksort.c b/test/monniaux/quicksort/quicksort.c new file mode 100644 index 00000000..de04bf2d --- /dev/null +++ b/test/monniaux/quicksort/quicksort.c @@ -0,0 +1,42 @@ +#include "quicksort.h" + +/* Rosetta Code */ +void quicksort(data *A, int len) { + if (len < 2) return; + + data pivot = A[len / 2]; + + int i, j; + for (i = 0, j = len - 1; ; i++, j--) { + while (A[i] < pivot) i++; + while (A[j] > pivot) j--; + + if (i >= j) break; + + data temp = A[i]; + A[i] = A[j]; + A[j] = temp; + } + + quicksort(A, i); + quicksort(A + i, len - i); +} + +data data_random(void) { + static uint64_t next = 1325997111; + next = next * 1103515245 + 12345; + return next; +} + +void data_vec_random(data *a, unsigned len) { + for(unsigned i=0; i<len; i++) { + a[i] = data_random(); + } +} + +bool data_vec_is_sorted(const data *a, unsigned len) { + for(unsigned i=0; i<len-1; i++) { + if (a[i] > a[i+1]) return false; + } + return true; +} diff --git a/test/monniaux/quicksort/quicksort.h b/test/monniaux/quicksort/quicksort.h new file mode 100644 index 00000000..cc73e7c3 --- /dev/null +++ b/test/monniaux/quicksort/quicksort.h @@ -0,0 +1,7 @@ +#include <stdint.h> +#include <stdbool.h> + +typedef uint64_t data; +void quicksort(data *A, int len); +void data_vec_random(data *a, unsigned len); +bool data_vec_is_sorted(const data *a, unsigned len); diff --git a/test/monniaux/quicksort/quicksort_run.c b/test/monniaux/quicksort/quicksort_run.c new file mode 100644 index 00000000..c269cc48 --- /dev/null +++ b/test/monniaux/quicksort/quicksort_run.c @@ -0,0 +1,22 @@ +#include <stdio.h> +#include <stdlib.h> +#include <inttypes.h> +#include "quicksort.h" +#include "../cycles.h" + +int main (void) { + cycle_count_config(); + unsigned len=10000; + data *vec = malloc(sizeof(data) * len); + data_vec_random(vec, len); + cycle_t quicksort_time = get_cycle(); + quicksort(vec, len); + quicksort_time = get_cycle() - quicksort_time; + printf("sorted=%s\n" + "quicksort_time=%" PRIu64 "\n", + data_vec_is_sorted(vec, len)?"true":"false", + quicksort_time); + free(vec); + return 0; +} + |