Program to Simulate the Cache Implementation in C Language Assignment Solution

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