You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
251 lines
5.3 KiB
251 lines
5.3 KiB
/*
|
|
* 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;
|
|
}
|
|
|
|
|
|
|
|
|
|
|