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 = 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 = 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; |
} |
|
|
|
|
|