Cache Practice Question

A Software Cache for a Hash Table

Suppose we have a machine with a 64 KB L1 data cache.

Our program uses a large hash table that maps 64-bit integer keys to float values. The table is much larger than the L1 cache, and we are worried that hash-table lookups will have poor locality.

Someone proposes building a small software-based cache for hash-table lookups. The cache should:

• use at most 32 KB of memory total,
• be 2-way set associative,
• use a 64-bit hash value to decide where an entry goes,
• store enough information to tell whether a lookup is a hit,
• store a cached copy of the corresponding float value.

For this question, assume:

• uint64_t is 8 bytes,
• float is 4 bytes,
• a simple cache entry will be padded/aligned to 16 bytes if it contains a uint64_t tag/hash and a float,
• each set has 2 entries.

One possible entry type is:

typedef struct cache_entry {
    uint64_t tag;
    float value;
    uint8_t valid;
    // padding inserted by compiler
} cache_entry_t;

Assume sizeof(cache_entry_t) == 16.

(When logged in, completion status appears here.)