Where are cachesim.h and math.h

The attached file ls.trace.zip contains a compressed trace file obtained by executing ls -l in one of the directories of my computer. Each line contains a record of one memory reference. The first symbol is the access type (Instruction, Load, Store, or M ?), followed by the virtual address, followed by a comma and another number that is not of importance to us. Using a programming language of your choice (acceptable: Python, C, C++, Java), write a program that simulates a fully associative CPU Level 1 cache. A cache line equals the page size, which in turn equals 4096 bytes. The page number is used as the associative key (tag), and the page content is the line itself. The cache has N entries and is initially cold (invalid). When the cache runs out of capacity, a random cache line is selected victim and evicted from the cache. Run your program on the trace file and count the numbers of cache misses and cache line evictions for N=8, 16, 32, 64, 128, 256, 512, and 1024 (eight experiments). Plot both numbers vs N in two separate charts. Explain what you see. For extra credit, simulate a cache with separate D/I partitions and plot the results together with the results of the single-partition cache. Deliverable: the program, two charts, and an explanation.

#include

#include

#include

#include

#include "cachesim.h"

int main(int argc, char *argv[])

{

if (argc != 3) {

printf("Usage: %s ", argv[0]);

return 1;

}

#ifdef DBG

printf("BLOCK SIZE = %d Bytes ", BLOCK_SIZE);

printf("%d-WAY ", WAY_SIZE);

printf("CACHE SIZE = %d Bytes ", CACHE_SIZE);

printf("NUMBER OF BLOCKS = %d ", NUM_BLOCKS);

printf("NUMBER OF SETS = %d ", NUM_SETS);

printf(" ");

#endif

char* trace_file_name = argv[2];

struct direct_mapped_cache d_cache;

char mem_request[20];

uint64_t address;

FILE *fp;

/* Initialization */

for (int i=0; i

d_cache.valid_field[i] = 0;

d_cache.dirty_field[i] = 0;

d_cache.tag_field[i] = 0;

}

d_cache.hits = 0;

d_cache.misses = 0;

/* Opening the memory trace file */

fp = fopen(trace_file_name, "r");

if (strncmp(argv[1], "direct", 6)==0) { /* Simulating direct-mapped cache */

/* Read the memory request address and access the cache */

while (fgets(mem_request, 20, fp)!= NULL) {

address = convert_address(mem_request);

direct_mapped_cache_access(&d_cache, address);

}

double totalMemAcesss = d_cache.hits + d_cache.misses;

double missRate = d_cache.misses / totalMemAcess;

double hitRate = 1 - missRate;

/*Print out the results*/

printf(" ================================== ");

printf("Cache type: Direct-Mapped Cache ");

printf("================================== ");

printf("Cache Hits: %d ", d_cache.hits);

printf("Cache Misses: %d ", d_cache.misses);

printf("Cache Hit rate: %d ", hitRate);

printf("Cache miss rate: %d ", missRate);

printf(" ");

}

fclose(fp);

return 0;

}

uint64_t convert_address(char memory_addr[])

/* Converts the physical 32-bit address in the trace file to the "binary" \\

* (a uint64 that can have bitwise operations on it) */

{

uint64_t binary = 0;

int i = 0;

while (memory_addr[i] != ' ') {

if (memory_addr[i] = '0') {

binary = (binary*16) + (memory_addr[i] - '0');

} else {

if(memory_addr[i] == 'a' || memory_addr[i] == 'A') {

binary = (binary*16) + 10;

}

if(memory_addr[i] == 'b' || memory_addr[i] == 'B') {

binary = (binary*16) + 11;

}

if(memory_addr[i] == 'c' || memory_addr[i] == 'C') {

binary = (binary*16) + 12;

}

if(memory_addr[i] == 'd' || memory_addr[i] == 'D') {

binary = (binary*16) + 13;

}

if(memory_addr[i] == 'e' || memory_addr[i] == 'E') {

binary = (binary*16) + 14;

}

if(memory_addr[i] == 'f' || memory_addr[i] == 'F') {

binary = (binary*16) + 15;

}

}

i++;

}

#ifdef DBG

printf("%s converted to %llu ", memory_addr, binary);

#endif

return binary;

}

void direct_mapped_cache_access(struct direct_mapped_cache *cache, uint64_t address)

{

uint64_t block_addr = address >> (unsigned)log2(BLOCK_SIZE);

uint64_t index = block_addr % NUM_BLOCKS;

uint64_t tag = block_addr >> (unsigned)log2(NUM_BLOCKS);

#ifdef DBG

printf("Memory address: %llu, Block address: %llu, Index: %llu, Tag: %llu ", address, block_addr, index, tag);

#endif

if (cache->valid_field[index] && cache->tag_field[index] == tag) { /* Cache hit */

cache->hits += 1;

#ifdef DBG

printf("Hit! ");

#endif

} else {

/* Cache miss */

cache->misses += 1;

#ifdef DBG

printf("Miss! ");

#endif

if (cache->valid_field[index] && cache->dirty_field[index]) {

/* Write the cache block back to memory */

}

cache->tag_field[index] = tag;

cache->valid_field[index] = 1;

cache->dirty_field[index] = 0;

}

}