Subversion Repositories Code-Repo

/*

 * 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;

}