diff options
Diffstat (limited to 'lab6_malloclab/fcyc.c')
-rw-r--r-- | lab6_malloclab/fcyc.c | 251 |
1 files changed, 251 insertions, 0 deletions
diff --git a/lab6_malloclab/fcyc.c b/lab6_malloclab/fcyc.c new file mode 100644 index 0000000..7b62622 --- /dev/null +++ b/lab6_malloclab/fcyc.c @@ -0,0 +1,251 @@ +/* + * fcyc.c - Estimate the time (in CPU cycles) used by a function f + * + * Copyright (c) 2002, R. Bryant and D. O'Hallaron, All rights reserved. + * May not be used, modified, or copied without permission. + * + * Uses the cycle timer routines in clock.c to estimate the + * the time in CPU cycles for a function f. + */ +#include <stdlib.h> +#include <sys/times.h> +#include <stdio.h> + +#include "fcyc.h" +#include "clock.h" + +/* Default values */ +#define K 3 /* Value of K in K-best scheme */ +#define MAXSAMPLES 20 /* Give up after MAXSAMPLES */ +#define EPSILON 0.01 /* K samples should be EPSILON of each other*/ +#define COMPENSATE 0 /* 1-> try to compensate for clock ticks */ +#define CLEAR_CACHE 0 /* Clear cache before running test function */ +#define CACHE_BYTES (1<<19) /* Max cache size in bytes */ +#define CACHE_BLOCK 32 /* Cache block size in bytes */ + +static int kbest = K; +static int maxsamples = MAXSAMPLES; +static double epsilon = EPSILON; +static int compensate = COMPENSATE; +static int clear_cache = CLEAR_CACHE; +static int cache_bytes = CACHE_BYTES; +static int cache_block = CACHE_BLOCK; + +static int *cache_buf = NULL; + +static double *values = NULL; +static int samplecount = 0; + +/* for debugging only */ +#define KEEP_VALS 0 +#define KEEP_SAMPLES 0 + +#if KEEP_SAMPLES +static double *samples = NULL; +#endif + +/* + * init_sampler - Start new sampling process + */ +static void init_sampler() +{ + if (values) + free(values); + values = (double*) calloc(kbest, sizeof(double)); +#if KEEP_SAMPLES + if (samples) + free(samples); + /* Allocate extra for wraparound analysis */ + samples = calloc(maxsamples+kbest, sizeof(double)); +#endif + samplecount = 0; +} + +/* + * add_sample - Add new sample + */ +static void add_sample(double val) +{ + int pos = 0; + if (samplecount < kbest) { + pos = samplecount; + values[pos] = val; + } else if (val < values[kbest-1]) { + pos = kbest-1; + values[pos] = val; + } +#if KEEP_SAMPLES + samples[samplecount] = val; +#endif + samplecount++; + /* Insertion sort */ + while (pos > 0 && values[pos-1] > values[pos]) { + double temp = values[pos-1]; + values[pos-1] = values[pos]; + values[pos] = temp; + pos--; + } +} + +/* + * has_converged- Have kbest minimum measurements converged within epsilon? + */ +static int has_converged() +{ + return + (samplecount >= kbest) && + ((1 + epsilon)*values[0] >= values[kbest-1]); +} + +/* + * clear - Code to clear cache + */ +static volatile int sink = 0; + +static void clear() +{ + int x = sink; + int *cptr, *cend; + int incr = cache_block/sizeof(int); + if (!cache_buf) { + cache_buf = (int *) malloc(cache_bytes); + if (!cache_buf) { + fprintf(stderr, "Fatal error. Malloc returned null when trying to clear cache\n"); + exit(1); + } + } + cptr = (int *) cache_buf; + cend = cptr + cache_bytes/sizeof(int); + while (cptr < cend) { + x += *cptr; + cptr += incr; + } + sink = x; +} + +/* + * fcyc - Use K-best scheme to estimate the running time of function f + */ +double fcyc(test_funct f, void *argp) +{ + double result; + init_sampler(); + if (compensate) { + do { + double cyc; + if (clear_cache) + clear(); + start_comp_counter(); + f(argp); + cyc = get_comp_counter(); + add_sample(cyc); + } while (!has_converged() && samplecount < maxsamples); + } else { + do { + double cyc; + if (clear_cache) + clear(); + start_counter(); + f(argp); + cyc = get_counter(); + add_sample(cyc); + } while (!has_converged() && samplecount < maxsamples); + } +#ifdef DEBUG + { + int i; + printf(" %d smallest values: [", kbest); + for (i = 0; i < kbest; i++) + printf("%.0f%s", values[i], i==kbest-1 ? "]\n" : ", "); + } +#endif + result = values[0]; +#if !KEEP_VALS + free(values); + values = NULL; +#endif + return result; +} + + +/************************************************************* + * Set the various parameters used by the measurement routines + ************************************************************/ + +/* + * set_fcyc_clear_cache - When set, will run code to clear cache + * before each measurement. + * Default = 0 + */ +void set_fcyc_clear_cache(int clear) +{ + clear_cache = clear; +} + +/* + * set_fcyc_cache_size - Set size of cache to use when clearing cache + * Default = 1<<19 (512KB) + */ +void set_fcyc_cache_size(int bytes) +{ + if (bytes != cache_bytes) { + cache_bytes = bytes; + if (cache_buf) { + free(cache_buf); + cache_buf = NULL; + } + } +} + +/* + * set_fcyc_cache_block - Set size of cache block + * Default = 32 + */ +void set_fcyc_cache_block(int bytes) { + cache_block = bytes; +} + + +/* + * set_fcyc_compensate- When set, will attempt to compensate for + * timer interrupt overhead + * Default = 0 + */ +void set_fcyc_compensate(int compensate_arg) +{ + compensate = compensate_arg; +} + +/* + * set_fcyc_k - Value of K in K-best measurement scheme + * Default = 3 + */ +void set_fcyc_k(int k) +{ + kbest = k; +} + +/* + * set_fcyc_maxsamples - Maximum number of samples attempting to find + * K-best within some tolerance. + * When exceeded, just return best sample found. + * Default = 20 + */ +void set_fcyc_maxsamples(int maxsamples_arg) +{ + maxsamples = maxsamples_arg; +} + +/* + * set_fcyc_epsilon - Tolerance required for K-best + * Default = 0.01 + */ +void set_fcyc_epsilon(double epsilon_arg) +{ + epsilon = epsilon_arg; +} + + + + + |