Instructions
Objective
Write a C assignment program to simulate the cache in C language.
Requirements and Specifications
Cache Simulation
A cache is a collection of cache lines, each of which may store a block of memory along with some additional information about the block (for example, which addresses it contains). Each block contains the same number of bytes, known as the block size. The block size will always be a power of two. The cache size is the block size multiplied by the number of cache lines (that is, the additional information is not counted in the cache size). Consider a system with 48-bit addresses and a block size of 16 bytes. Each block will begin with an address divisible by 16. Because 16 = 24, the last 4 bits of an address will determine its offset within a particular block. For example, the address ffff0000abcd (hexadecimal) will have offset d. The remaining 44 bits of the address may be considered a block identifier.
If the block size were 8 bytes, then the last 3 bits of the address would be its block offset. The last three bits of ffff000abcd are 101 (binary) or 5 (hexadecimal). The most-significant 45 bits will be the block identifier. (Exercise: write the block identifier in hexadecimal.1)
For a cache with a single cache line, that cache line will store the 16 bytes of the block (the data) along with the validity bit and block identifier (the metadata). Each memory access will first check whether the address is part of the block currently in the cache (if any). Since we are only simulating memory reads and writes, you cache will not need to store the actual blocks.
Screenshots of output
Source Code
#include
#include
#include
#include
#include
// associativity type
enum {DIRECT, NWAY};
// replacement policy type
enum {FIFO, LRU};
// Definition of a single line in the cache
typedef struct
{
unsigned long tag; // tag of the cached block
bool valid; // valid flag
unsigned time; // time of entry for fifo, time of last access for lru
}CacheLine;
// gets the log 2 of the number, x must be a power of 2. It simply gets the
// position of the first 1
int log_2(unsigned int x)
{
int n = 0;
while ((x & 1) == 0)
{
x >>= 1;
n++;
}
return n;
}
// simulate the cache using the given arguments and reading from the given file
void simulate(FILE *f, int cachesize, int blksize, int nways, int assoc, int policy, int prefetch)
{
char buffer[50];
int cache_misses = 0;
int cache_hits = 0;
int memory_reads = 0;
int memory_writes = 0;
// number of lines in cache
int nlines = cachesize / blksize;
// create the cache
CacheLine *cache = (CacheLine *) malloc(nlines * sizeof(CacheLine));
// clear cache entries
memset(cache, 0, nlines * sizeof(CacheLine));
// calculate the offset bits
int obits = log_2(blksize);
// calculate the set bits
int sbits = log_2(nlines / nways);
// get the bitmasks for the set and the tag fields
unsigned long setmsk = (1 << sbits) - 1;
unsigned long tagmsk = ((unsigned long) 1 << (48 - sbits - obits)) - 1;
fseek(f, 0, SEEK_SET); // rewind file pointer
bool halt = false;
unsigned time = 0;
while (!halt)
{
if (fgets(buffer, 50, f) != NULL)
{
if (!strncmp(buffer, "#eof", 4) || !strncmp(buffer, "#end", 4))
halt = true;
else if (buffer[0] != 0) // avoid empty lines
{
char rw;
unsigned long address;
// read trace line
sscanf(buffer, "%*x: %c 0x%lx", &rw, &address);
// get set and tag fields from address
unsigned long set = (address >> obits) & setmsk;
unsigned long tag = (address >> (sbits + obits)) & tagmsk;
if (assoc == DIRECT)
{
// if tag was cached
if (cache[set].valid && cache[set].tag == tag)
{
cache_hits++;
if (rw == 'W') // a write to cache will write memory
memory_writes++;
}
else // tag not found in cache
{
cache_misses++;
memory_reads++; // reads the block from memory
if (rw == 'W')
memory_writes++; // the write first reads, then writes
cache[set].tag = tag; // update tag
cache[set].valid = true; // mark line as valid
if (prefetch)
{
// increment tag if set + 1 overflows the number of set bits
tag += (set + 1) >> sbits;
// leave only the correct number of bits for set + 1
set = (set + 1) & setmsk;
if (!cache[set].valid || cache[set].tag != tag)
{
memory_reads++; // if set + 1 is not loaded, read memory
cache[set].tag = tag;
cache[set].valid = true;
}
}
}
}
else
{
bool found = false;
// search tag in all ways for the selected set
for (int i = 0; i < nways && !found; i++)
{
// if we found the tag in one of the ways
if (cache[set * nways + i].valid && cache[set * nways + i].tag == tag)
{
cache_hits++;
if (rw == 'W') // a write to cache will write memory
memory_writes++;
if (policy == LRU) // if LRU, any access updates the line time
cache[set * nways + i].time = time++;
found = true;
}
}
if (!found) // tag not found in cache
{
// set minimum to current time + 1 (above any time in cache)
int min_t = time + 1;
int sel_i = -1; // no selected way
// search for an empty line and, if all are full,
// find the line with the minimum time
for (int i = 0; i < nways && !found; i++)
{
// if free line
if (!cache[set * nways + i].valid)
{
sel_i = i; // select this line
found = true;
}
// if not free, see if we need to update the minimum
else if (cache[set * nways + i].time < min_t)
{
min_t = cache[set * nways + i].time;
sel_i = i;
}
}
// get the position of the selected line in the cache
int pos = set * nways + sel_i;
cache_misses++;
memory_reads++; // read the block from memory
if (rw == 'W')
memory_writes++; // the write first reads, then writes
cache[pos].tag = tag; // update tag
cache[pos].valid = true; // mark line as valid
cache[pos].time = time++; // update its time of entry/access
if (prefetch)
{
// increment tag if set + 1 overflows the number of set bits
tag += (set + 1) >> sbits;
// leave only the correct number of bits for set + 1
set = (set + 1) & setmsk;
found = false;
// search tag in all ways for set + 1
for (int i = 0; i < nways && !found; i++)
{
if (cache[set * nways + i].valid && cache[set * nways + i].tag == tag)
found = true; // if found, we don't need to prefetch
}
if (!found) // if tag is not in set + 1
{
// set minimum to current time + 1 (above any time in cache)
min_t = time + 1;
sel_i = -1;
// search for an empty line and, if all are full,
// find the line with the minimum time
for (int i = 0; i < nways && !found; i++)
{
// if free line
if (!cache[set * nways + i].valid)
{
sel_i = i; // select this line
found = true; // break loop
}
// if not free, see if we need to update the minimum
else if (cache[set * nways + i].time < min_t)
{
min_t = cache[set * nways + i].time;
sel_i = i;
}
}
// get the position of the selected line in the cache
pos = set * nways + sel_i;
memory_reads++; // read the block from memory
cache[pos].tag = tag; // update tag
cache[pos].valid = true; // mark line as valid
cache[pos].time = time++; // update its time of entry/access
}
}
}
}
}
}
else
halt = true;
}
// free the allocated memory
free(cache);
// print the statistics
printf("Prefetch %d\n", prefetch);
printf("Memory reads: %d\n", memory_reads);
printf("Memory writes: %d\n", memory_writes);
printf("Cache hits: %d\n", cache_hits);
printf("Cache misses: %d\n", cache_misses);
}
int main(int argc, char **argv)
{
int cache_size;
int assoc;
int block_size;
int nways;
int policy;
FILE *f;
if (argc != 6)
{
printf("Usage:\n");
printf(" %s (direct | assoc[:n]) (fifo | lru) \n", argv[0]);
return 0;
}
cache_size = atoi(argv[1]);
if (cache_size <= 0 || (cache_size & (cache_size - 1)) != 0)
{
printf("Error: Invalid cache size.\n");
return 1;
}
block_size = atoi(argv[4]);
if (block_size <= 0 || (block_size & (block_size - 1)) != 0)
{
printf("Error: Invalid block size.\n");
return 1;
}
if (strcmp(argv[2], "direct") == 0)
{
assoc = DIRECT;
nways = 1;
}
else if (strcmp(argv[2], "assoc") == 0)
{
assoc = NWAY; // we treat full as n-way with n = number of lines
// set number of ways to number of lines
nways = cache_size/block_size;
}
else if (strncmp(argv[2], "assoc:", 6) == 0)
{
assoc = NWAY;
if (sscanf(argv[2], "assoc:%d", &nways) != 1)
{
printf("Error: Invalid number of ways.\n");
return 1;
}
}
else
{
printf("Error: Invalid associativity.\n");
return 1;
}
if (strcmp(argv[3], "fifo") == 0)
policy = FIFO;
else if (strcmp(argv[3], "lru") == 0)
policy = LRU;
else
{
printf("Error: Invalid replacement policy.\n");
return 1;
}
f = fopen(argv[5], "rt");
if (f == NULL)
{
printf("Error: unable to open trace file.\n");
return 1;
}
// simulate without prefetch
simulate(f, cache_size, block_size, nways, assoc, policy, 0);
// simulate using prefetch
simulate(f, cache_size, block_size, nways, assoc, policy, 1);
fclose(f);
return 0;
}