Question

1 Overview

The goal of this assignment is to help you understand caches better. You are required to write a cache simulator using the C programming language. The programs have to run on iLab machines. We are providing real program memory traces as input to your cache simulator. The format and structure of the memory traces are described below. We will not give you improperly formatted files. You can assume all your input files will be in proper format as described.

2 Memory Access Traces The input to the cache simulator is a memory access trace, which we have generated by executing real programs. The trace contains memory addresses accessed during program execution. Your cache simulator will have to use these addresses to determine if the access is a hit or a miss, and the actions to perform in each case. The memory trace file consists of multiple lines. Each line of the trace file corresponds to a memory accesses performed by the program. Each line consists of multiple columns, which are space separated. The first column reports the PC (program counter) when this particular memory access occurred, followed by a colon(:). Second column lists whether the memory access is a read (R) or a write (W) operation. And the last column reports the actual 48-bit memory address that has been accessed by the program. In this assignment, you only need to consider the second and the third columns (i.e. you dont really need to know the PCs). The last line of the trace file will be the string #eof. We have provided you three input trace files (some of them are larger in size). Here is a sample trace file. 0x804ae19: R 0x9cb3d40 0x804ae19: W 0x9cb3d40 0x804ae1c: R 0x9cb3d44 0x804ae1c: W 0x9cb3d44 0x804ae10: R 0xbf8ef498 #eof 1

3 Cache Simulator

You will implement a cache simulator to evaluate different configurations of caches. It should be able to run with different traces files. The followings are the requirements for your cache simulator: • Simulate only one level cache; i.e., an L1 cache. • The cache size, associativity, the replacement policy, and the block size are input parameters. Cache size and block size are specfied in bytes. • Replacement algorithm: Least Recently Used (LRU). When a block needs to be replaced, the cache evicts the block that was accessed least recently. It does not take into account whether the block is frequently accessed. • You have to simulate a write through cache.

4 Cache Simulator Interface

You have to name your cache simulator first. Your program should support the following usage interface: ./first where: A) is the total size of the cache in bytes. This number should be a power of 2. B) is one of: direct - simulate a direct mapped cache. assoc - simulate a fully associative cache. assoc:n - simulate an n way associative cache. n will be a power of 2. C) Here is valid cache policy is lru. D) is a power of 2 integer that specifies the size of the cache block in bytes. E) is the name of the trace file. Your program should check if all the inputs are in valid format, if not print error and then terminate the program.

5 Cache Prefetcher

Prefetching is a common technique to increase the spatial locality of the caches beyond the cache line. The idea of prefetching is to bring the data into the cache before it is needed (accessed). In a normal cache, you bring a block of data into the cache whenever you experience a cache-miss. Now, we want you to explore a different type of cache that prefetches, not only bringing in the block corresponding to the access but also prefetches one adjacent block, which will result in one extra memory read. For example, if a memory address 0x40 misses in the cache and the block size is 4 bytes, then the prefetcher would bring the block corresponding to 0x40 + 4 into the cache. The prefetcher is 2 activated only on misses and it is not active on a cache hit. If the prefetched block is already in the cache, it does not issue a memory read. With respect to cache replacement policies, if the prefetched block hits in the cache, the line replacement policy status should not be updated. Otherwise, it is treated similar to a block that missed the cache. 6 Cache Replacement Policy The goal of the cache replacement policy is to decide which block has to be evicted in case there is no space in the set for an incoming cache block. It is always preferable - to achieve the best performance - to replace the block that will be re-referenced furthest in the future. There are different ways one can implement cache replacement policy. Here we use LRU replacement policy. 6.1 LRU Using this algorithm, you can always evict the block accessed least recently in the set without any regard to how often or how many times it was accessed before. So let us say that your cache is empty initially and that each set has two ways. Now suppose that you access blocks A, B, A, C. To make room for C, you would evict B since it was accessed less recently than A. 7 Sample Run Your program should print out the number of memory reads (per cache block), memory writes (per cache block), cache hits, and cache misses for normal cache and the cache with prefetcher. You should follow the exact same format shown below (pay attention to case sensitivity of the letters), otherwise, the autograder cannot grade your program properly. $./first 32 assoc:2 lru 4 trace1.txt no-prefetch Memory reads: 336 Memory writes: 334 Cache hits: 664 Cache misses: 336 with-prefetch Memory reads: 336 Memory writes: 334 Cache hits: 832 Cache misses: 168 In this example above, we are simulating 2-way set associate cache of size 32 bytes. Each cache block is 4 bytes. The trace file name is trace1.txt. As you can see, the simulator should simulate both catch types with the prefetcher and without the prefetcher in a single run and display the results for both. Note: Some of the trace files are quite large. So it might take a few minutes for the autograder to grade for all the testcases. 3

8 Simulation Details

1. (a) When your program starts, there is nothing in the cache. So, all cache lines are empty (invalid). (b) you can assume that the memory size is 2pow48 . Therefore, memory addresses are 48 bit (zero extend the addresses in the trace file if theyre less than 48-bit in length). (c) the number of bits in the tag, cache address, and byte address are determined by the cache size and the block size. 2. For a write-through cache, there is the question of what should happen in case of a write miss. In this assignment, the assumption is that the block is fist read from memory (one read memory), and then followed by a memory write. 3. You do not need to simulate the memory in this assignment. Because, the traces doesnt contain any information on data values transferred between the memory and the caches. 4. You have to compile your program with the following flags: -Wall -Werror -fsanitize=address 9 Submission You have to e-submit the assignment using Sakai . Put all files (source code + Makefile + report.pdf) into a directory named first, which itself is a sub-directory under pa4 . Then, create a tar file (follow the instructions in the previous assignments to create the tar file). Your submission should be only a tar file named pa4.tar. You have to e-submit the assignment using Sakai. Your submission should be a tar file named pa4.tar. To create this file, put everything that you are submitting into a directory named pa4. Then, cd into the directory containing pa4 (that is, pa4s parent directory) and run the following command: $tar cvf pa4.tar pa4 To check that you have correctly created the tar file, you should copy it (pa4.tar) into an empty directory and run the following command: $tar xvf pa4.tar This is how the folder structure should be. • pa4 – first ∗ first.c ∗ first.h ∗ Makefile ∗ report.txt Source code: all source code files necessary for building your programs. e.g. first.c and first.h. Makefile: There should be at least two rules in your Makefile: first: build the executables (first). clean: prepare for rebuilding from scratch. report.txt: In a text file, you should briefly describe the main data structures being used in your program. More importantly, you should report your observation on how the prefetcher changed the cache hits and number of memory reads. Explain why?

Answer 1

Please let me know if you have any doubts or you want me to modify the answer. And if you find this answer useful then don't forget to rate my answer as thumps up. Thank you! :)

//main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "catcheSimulator.h"

int num_of_hits = 0;
int num_of_misses = 0;
int reads = 0;
int writes = 0;
int num_of_lines = 0;
int cache_size = 0;
int block_size = 0;
int assoc = 0;
int block_sub = 0;
int set_sub = 0;
char write_policy[] = " ";
char replacement_policy[] = "    ";
Line* cache;

int main(int argc, char *argv[]) {
    int i;
    if (argc != 7){
        printf("Not enough arguments.\n");
        //return;
    }

    cache_size = atoi(argv[1]);
    if(!((cache_size != 0) && (cache_size & (cache_size - 1)) == 0)){
        printf("Cache size is not a power of 2 or cache size is 0.\n");
        return 1;
    }

    block_size = atoi(argv[3]);
    if(!((block_size != 0) && ((block_size & (block_size - 1)) == 0))){
        printf("Block size is not a power of 2 or cache size is 0.\n");
        return 1;
    }else{
        for(i = 1; i < block_size; i*=2){
            block_sub++;
        }
    }

    char *c;
    if(strcmp(argv[2], "direct") == 0){
        assoc = 1;
    }else if(strcmp(argv[2], "assoc") == 0){
        assoc = (int)(cache_size/block_size);
    }else{
        c = strtok(argv[2], ":");
        c = strtok(NULL, ":");
        if(c == NULL){
            printf("Associativity is invalid.\n");
            return 1;
        }
        assoc = atoi(c);
    }

    if(strcmp(argv[4], "LRU") == 0){
        strcpy(replacement_policy, "LRU ");
    }else if(strcmp(argv[4], "FIFO") == 0){
        strcpy(replacement_policy, "FIFO");
    }else{
        printf("Invalid Replacement Policy.\n");
        return 1;
    }

    if(strcmp(argv[5], "wt") == 0){
        strcpy(write_policy, "wt");
    }else if(strcmp(argv[5], "wb") == 0){
        strcpy(write_policy, "wb");
    }else{
        printf("Incorrect Write Policy.\n");
        return 1;
    }

    FILE *file = fopen(argv[6], "r");
    if(file == 0){
        printf("File not found.\n");
        return 1;
    }

    num_of_lines = (int)(cache_size/block_size);
    for(i = 1; i < (num_of_lines / assoc); i*=2){
        set_sub++;
    }

    char ip[20];
    char wr[2];
    char address[20];
    char *binary;

    cache = create_cache();
    if(num_of_lines / assoc * assoc * block_size != cache_size || cache_size == 0){
        printf("Invalid size, block size, or associativity.\n");
        return 1;
    }

    while (fscanf(file, "%s %s %s", ip, wr, address) != EOF) {
        if(strcmp(ip, "#eof") == 0){
            break;
        }
        if (strcmp(replacement_policy, "FIFO") == 0){
            if(strcmp(write_policy, "wt") == 0){
                binary = get_binary_addr(address);
                if(strcmp(wr, "W") == 0){
                    write_to_cache(binary);
                }else if(strcmp(wr, "R") == 0){
                    read_from_cache(binary);
                }
            }else{
                binary = get_binary_addr(address);
                if(strcmp(wr, "W") == 0){
                    write_to_cache_wb(binary);
                }else if(strcmp(wr, "R") == 0){
                    read_from_cache_wb(binary);
                }
            }
        }
    }
    printf("Memory reads: %d\n", reads);
    printf("Memory writes: %d\n", writes);
    printf("Cache hits: %d\n", num_of_hits);
    printf("Cache misses: %d\n", num_of_misses);
    fclose(file);
    free_cache();
    return 0;
}

Line *create_cache(){
    Line *cache = malloc(sizeof(Line) * num_of_lines);
    int i;
    for(i = 0; i < num_of_lines; i++){
        cache[i].valid = 0;
        cache[i].tag = (char *)malloc(sizeof(char) * 81);
        strcpy(cache[i].tag, "-");
        cache[i].set = i / assoc;
        cache[i].recent = 0;
        cache[i].dirty = 0;
        cache[i].tag_length = 1;
    }
    return cache;
}

int find_tag_length(char addr[]){
    return strlen(addr) - set_sub - block_sub;
}

char *get_binary_addr(char addr[]){
    int i;
    char *binary = (char *)malloc(sizeof(char) * 81);
    for(i = 2; i < strlen(addr); i++){
        switch(addr[i]){
            case '0':
                strcat(binary, "0000");
                break;
            case '1':
                strcat(binary, "0001");
                break;
            case '2':
                strcat(binary, "0010");
                break;
            case '3':
                strcat(binary, "0011");
                break;
            case '4':
                strcat(binary, "0100");
                break;
            case '5':
                strcat(binary, "0101");
                break;
            case '6':
                strcat(binary, "0110");
                break;
            case '7':
                strcat(binary, "0111");
                break;
            case '8':
                strcat(binary, "1000");
                break;
            case '9':
                strcat(binary, "1001");
                break;
            case 'a':
                strcat(binary, "1010");
                break;
            case 'b':
                strcat(binary, "1011");
                break;
            case 'c':
                strcat(binary, "1100");
                break;
            case 'd':
                strcat(binary, "1101");
                break;
            case 'e':
                strcat(binary, "1110");
                break;
            case 'f':
                strcat(binary, "1111");
                break;
        }
    }
    return binary;
}

int get_index(char address[], int tag_length){
    int index = 0;
    int exp = 1;
    int i;
    for(i = strlen(address) - 1 - block_sub; i >= tag_length; i--){
        if(address[i] == '1'){
            index += exp;
        }
        exp = exp<<1;
    }
    return index;
}

void update_recents(int new_index, int index){
    int i;
    for(i = index * assoc; i < index; i++){
        cache[i].recent++;
    }
    cache[new_index].recent = 0;
}

void write_to_cache(char addr[]){
    int highest = 0;
    int index = get_index(addr, find_tag_length(addr)) * assoc;
    int highest_index = index;
    int i;
    writes++;
    for(i = index; i < index + assoc; i++){
        if(strncmp(cache[i].tag, addr, cache[i].tag_length) == 0){
            if(cache[i].valid == 1){
                num_of_hits++;
                strcpy(cache[i].tag, addr);
                cache[i].tag_length = find_tag_length(addr);
                update_recents(i, cache[i].set);
                return;
            }
        }
    }
    num_of_misses++;
    reads++;
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 0){
            cache[i].valid = 1;
            strcpy(cache[i].tag, addr);
            cache[i].tag_length = find_tag_length(addr);
            update_recents(i, cache[i].set);
            return;
        }
    }
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].recent > highest){
            highest = cache[i].recent;
            highest_index = i;
        }
    }
    cache[highest_index].tag_length = find_tag_length(addr);
    strcpy(cache[highest_index].tag, addr);
    update_recents(highest_index, cache[highest_index].set);
}

void read_from_cache(char addr[]){
    int index = get_index(addr, find_tag_length(addr)) * assoc;
    int highest_index = index;
    int highest = 0;
    int i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 1){
            if(strncmp(cache[i].tag, addr, cache[i].tag_length) == 0){
                num_of_hits++;
                update_recents(i, cache[i].set);
                return;
            }
        }
    }
    num_of_misses++;
    reads++;
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 0){
            cache[i].valid = 1;
            cache[i].tag_length = find_tag_length(addr);
            strcpy(cache[i].tag, addr);
            update_recents(i, cache[i].set);
            return;
        }
    }
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].recent > highest){
            highest = cache[i].recent;
            highest_index = i;
        }
    }
    cache[highest_index].tag_length = find_tag_length(addr);
    strcpy(cache[highest_index].tag, addr);
    update_recents(highest_index, cache[highest_index].set);
}

void write_to_cache_wb(char address[]){
    int index = get_index(address, find_tag_length(address)) * assoc;
    int highest_index = index;
    int highest = 0;
    int i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 1){
            if(strncmp(cache[i].tag, address, cache[i].tag_length) == 0){
                num_of_hits++;
                cache[i].tag_length = find_tag_length(address);
                cache[i].dirty = 1;
                update_recents(i, cache[i].set);
                return;
            }
        }
    }
    num_of_misses++;
    reads++;
    index = get_index(address, find_tag_length(address)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 0){
            cache[i].valid = 1;
            cache[i].tag_length = find_tag_length(address);
            strcpy(cache[i].tag, address);
            cache[i].dirty = 1;
            update_recents(i, cache[i].set);
            return;
        }
    }
    index = get_index(address, find_tag_length(address)) * assoc;
    for(i = index; i < index + assoc; i++){
        if(cache[i].recent > highest){
            highest = cache[i].recent;
            highest_index = i;
        }
    }
    if(cache[highest_index].dirty == 1){
        writes++;
    }
    cache[highest_index].tag_length = find_tag_length(address);
    strcpy(cache[highest_index].tag, address);
    cache[highest_index].dirty = 1;
    update_recents(highest_index, cache[highest_index].set);
}

void read_from_cache_wb(char addr[]){
    int i;
    int index = get_index(addr, find_tag_length(addr)) * assoc;
    int highest_index = index;
    int highest = 0;
    for(i = index; i < index + assoc; i++){
        if(cache[i].valid == 1){
            if(strncmp(cache[i].tag, addr, cache[i].tag_length) == 0){
                num_of_hits++;
                update_recents(i, cache[i].set);
                return;
            }
        }
    }
    reads++;
    num_of_misses++;
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 0){
            cache[i].valid = 1;
            cache[i].dirty = 0;
            cache[i].tag_length = find_tag_length(addr);
            strcpy(cache[i].tag, addr);
            update_recents(i, cache[i].set);
            return;
        }
    }
    index = get_index(addr, find_tag_length(addr)) * assoc;
    for(i = index; i < index + assoc; i++){
        if(cache[i].recent > highest){
            highest = cache[i].recent;
            highest_index = i;
        }
    }
    if(cache[highest_index].dirty == 1){
        writes++;
    }
    cache[highest_index].tag_length = find_tag_length(addr);
    strcpy(cache[highest_index].tag, addr);
    cache[highest_index].dirty = 0;
    update_recents(highest_index, cache[highest_index].set);
}

void write_to_cache_LRU(char addr[]){
    int highest = 0;
    int index = get_index(addr, find_tag_length(addr)) * assoc;
    int highest_index = index;
    int i;
    writes++;
    for(i = index; i < index + assoc; i++){
        if(strncmp(cache[i].tag, addr, cache[i].tag_length) == 0){
            if(cache[i].valid == 1){
                if(cache[i].recent == 0){
                    num_of_hits++;
                    strcpy(cache[i].tag, addr);
                    cache[i].tag_length = find_tag_length(addr);
                    update_recents(i, cache[i].set);
                    return;
                }
            }
        }
    }
    num_of_misses++;
    reads++;
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].valid == 0){
            cache[i].valid = 1;
            if(cache[i].recent == 0){
                num_of_hits++;
                strcpy(cache[i].tag, addr);
                cache[i].tag_length = find_tag_length(addr);
                update_recents(i, cache[i].set);
                return;
            }
        }
    }
    index = get_index(addr, find_tag_length(addr)) * assoc;
    i = index;
    for(; i < index + assoc; i++){
        if(cache[i].recent > highest){
            highest = cache[i].recent;
            highest_index = i;
        }
    }
    cache[highest_index].tag_length = find_tag_length(addr);
    strcpy(cache[highest_index].tag, addr);
    update_recents(highest_index, cache[highest_index].set);
}

void print_cache(){
    int i;
    int j;
    for(i = 0; i < num_of_lines; i++){
        printf("index: %d set: %d valid: %d recent: %d tag length: %d tag:", i, cache[i].set, cache[i].valid, cache[i].recent, cache[i].tag_length);
        for(j = 0; j < cache[i].tag_length; j++){
            printf("%c", cache[i].tag[j]);
        }
        printf("\n");
    }
}

void free_cache(){
    int i;
    for(i = 0; i < num_of_lines; i++){
        free(cache[i].tag);
    }
    free(cache);
}
------------------------------------------------------------------------------------------------------------------------------------------------
//catcheSimulator.h

#ifndef CACHESIMULATOR_CATCHESIMULATOR_H
#define CACHESIMULATOR_CATCHESIMULATOR_H

typedef struct Line{
    int valid;
    char *tag;
    char *block;
    int set;
    int recent;
    int dirty;
    int tag_length;
}Line;

Line *create_cache();
int find_tag_length(char address[]);
char *get_binary_addr(char address[]);
int get_index(char address[], int tag_length);
void update_recents(int new, int index);
void write_to_cache(char address[]);
void read_from_cache(char address[]);
void write_to_cache_wb(char address[]);
void read_from_cache_wb(char address[]);
void print_cache();
void free_cache();

#endif //CACHESIMULATOR_CATCHESIMULATOR_H

CacheSimulator [~/CLionProjectsCacheSimulator]-../main.c main.c * 끗 *- CAlakeLists.txt.-, main.c" aiput.txt Project catchesimulator.h CacheSimulator /CLionProjects/CacheSimulator #include <stdlib.h> #include <string.h> catcheSimulator.h 즈 cakeLists.txt E input.txt i #include "catcheSimulator.h" 4 int num-of-hits = e; int nun of misses-8 int reads = 0; int writes- int num of lines -; int cache size-; int block size ; int assoc = 0; int block-sub-e; int set-sub e; char write policy[1 char rep Linex cache main.c lilh External Libraries scratches and Consoles 14 17 2int main(int argc, char argvl) int i; if (argc !7) printf("Not enough arguments.In) //return cache size atoi(argv[1]): if(!((cache_size ! 0) && (cache-size & (cache-size-1))-0)){ 28 printf("Cache size is not a power of 2 or cache size is e.Ln") block size atoi(argv[3]): İt( !((block-size !-@) && ((block-size & (block.size-1))-8))){ printf("Block size is not a power of 2 or cache size is e.Ln") elset for(1+1; İ<block-size; i-2){ block sub++; . char *c if(str㎝n(arav 121, "direct", I -014 main Run:CacheSimulator ■ Terminal CMake -0: Messages Build finished in 892 ms (8 minutes ago) 4: 6: TOOO 24:18 LF: UTF-8 : 4 spaces: Context: CacheSimulator