c - 如何计算平均缓存未命中率 (ACMR)？

Question

我正在研究 Tom Forsyth 的线性速度顶点缓存优化，但我不明白他是如何计算 ACMR 的。根据我的阅读，我已经知道 ACMR = 缓存未命中数/三角形数，但我不明白正在使用哪种缓存(即 FIFO 或 LRU？)。

我已经编写了一个测试程序，它使用 FIFO 缓存计算和打印给定 3d 模型的 ACMR，您能告诉我这段代码是否正确吗？还是应该改用 LRU 缓存？

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

我找到了答案。现代 GPU 使用 FIFO 缓存来实现简单性和速度，因此使用 FIFO 缓存计算 ACMR 是有意义的。上面给出的代码是正确的，所以我会继续使用它。