How the Average Cache Miss Ratio (ACMR) is calculated?

Question

I'm studying Tom Forsyth's Linear-Speed Vertex Cache Optimization and i don't understand how he calculates the ACMR. From what i have read i already know that ACMR = number of cache misses / number of triangles, but what i don't understand is what kind of cache is being used (i.e. FIFO or LRU?).

I have written a test program that calculates and prints the ACMR of a given 3d model using a FIFO cache, can you please tell me if this code is ok? or should i use an LRU cache instead?

/* the number of entries in a FIFO cache */
#define FIFO_CACHE_SIZE     32

struct fifo_cache {
    long entries[FIFO_CACHE_SIZE];
};

/**
 * init_cache - initializes a FIFO cache
 * @cache: A pointer to the FIFO cache structure to be initialized.
 *
 * Before a FIFO cache can be used, it must be initialized by calling this
 * function.
 */
static void init_cache(struct fifo_cache *cache)
{
    int i = 0;

    /* initialize cache entries to an invalid value */
    for (i = 0;i < FIFO_CACHE_SIZE;i++)
        cache->entries[i] = -1;
}

/**
 * check_entry - checks if the same entry is already added to the cache
 * @cache: A pointer to the FIFO cache structure to be searched.
 * @entry: An entry to be searched for.
 *
 * Return: If the same entry was found, the return value is nonzero. Otherwise,
 *         the return value is zero.
 */
static int check_entry(const struct fifo_cache *cache, u16 entry)
{
    int i = 0;

    for (i = 0;i < FIFO_CACHE_SIZE;i++) {
        if (cache->entries[i] == (long)entry)
            return 1;
    }

    return 0;
}

/**
 * add_entry - adds a new entry to the FIFO cache
 * @cache: A pointer to the FIFO cache structure the entry will be added to.
 * @entry: An entry to add.
 */
static void add_entry(struct fifo_cache *cache, u16 entry)
{
    long aux = 0;
    long aux2 = 0;
    int i = 0;

    aux = cache->entries[0];
    cache->entries[0] = (long)entry;

    for (i = 1;i < FIFO_CACHE_SIZE;i++) {
        aux2 = cache->entries[i];
        cache->entries[i] = aux;
        aux = aux2;
    }
}

/**
 * calculate_acmr - calculates the average cache miss ratio (aka. ACMR)
 * @indices: The list of vertex indices.
 * @count: The number of vertex indices in the @indices list.
 */
float calculate_acmr(const u16 *indices, size_t count)
{
    struct fifo_cache cache = {0};
    long total = 0; /* the total number of cache misses */
    long i = 0;

    /* initialize the cache */
    init_cache(&cache);

    for (i = 0;i < count;i++) {
        if (!check_entry(&cache, indices[i])) {
            /* an entry doesn't exist in the cache, so add it */
            add_entry(&cache, indices[i]);

            total++;
        }
    }

    return ((float)total / (count / 3));
}

Answer 1

I found the answer. Modern GPUs uses FIFO caches for simplicity and speed, so it makes sense to calculate the ACMR using FIFO cache. The code given above is correct, so i'll keep using that.