Project 6: Cache

Learning Goals

How to use a Cache Simulator to make inference aboout caches with different parameters. In this Project we will develop our own basic Cache Simulator, that will further help you understand cache basics and strengthen your C Programming skills.

/*
 * csim.c:
 * A cache simulator that can replay traces (from Valgrind) and output
 * statistics for the number of hits, misses, and evictions.
 * The replacement policy is LRU.
 *
 * Implementation and assumptions:
 *  1. Each load/store can cause at most 1 cache miss plus a possible eviction.
 *  2. Instruction loads (I) are ignored.
 *  3. Data modify (M) is treated as a load followed by a store to the same
 *  address. Hence, an M operation can result in two cache hits, or a miss and a
 *  hit plus a possible eviction.
 */

CSIM.c: This is the main file that will take a memory trace as an input, simulates the hit/miss/eviciton behavior of cache memory of the trace, and then outputs the total number of hits, misses, and evictions as show below:

hits:4 misses:5 evictions:3

The directory traces contains a collection of memory trace files that we will use to evaluate the correctness of our csim implementation. These memory trace files are generated by a Linux program called Valgrind.

Basic of Caches

Cache Block: The basic unit for Cache storage, may contain multiple bytes/words of data.

Cache Line: Same as a Cache Block. Note that this is not the same thing as a ‘row’ of Cache.

Cache Set: A ‘row” in the Cache. The number of blocks per set is determined by the layout of the Cache (e.g Direct Mapped)

Tag: A unique identifer for a group of data

Valid Bit: A bit of information that indicates whether the data in a block is valid (1) or not (0).

Import Needed Libraries and Global Variables

#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <limits.h>
#include <string.h>
#include <errno.h>
#include <stdbool.h>

/******************************************************************************/
/* DO NOT MODIFY THESE VARIABLES **********************************************/

//Globals set by command line args.
int b = 0; //number of block (b) bits
int s = 0; //number of set (s) bits
int E = 0; //number of lines per set

//Globals derived from command line args.
int B; //block size in bytes: B = 2^b
int S; //number of sets: S = 2^s

//Global counters to track cache statistics in access_data().
int hit_cnt = 0;
int miss_cnt = 0;
int evict_cnt = 0;

//Global to control trace output
int verbosity = 0; //print trace if set
/******************************************************************************/

Setting Data Types

int lru_counter = 0; // Global Variable to track the next value for lru

//Type mem_addr_t: Use when dealing with addresses or address masks.
typedef unsigned long long int mem_addr_t;

// Type cache_line_t: Use when dealing with Cache lines.

typedef struct cache_line {                    
    char valid;
    mem_addr_t tag;
    int lru; // used for lru tracking
} cache_line_t;

// Type cache_set_t: Use when dealing with cache sets
// Note: Each set is a Pointer to a heap array of one or more cache lines.
typedef cache_line_t* cache_set_t;

// Type cache_t: Use when dealing with the cache.
// Note: A cache is a pointer to a heap array of "one or more sets".
typedef cache_set_t* cache_t;


// Create the cache (i.e., pointer var) we're simulating.
// Cache is a Combination of Sets
cache_t cache;  

Functions to Implement

Allocates the data structure for a Cache with S sets and E lines per set. Then it Initializes all valid bits and tags with 0s.

void init_cache() {

		S = 1; // initiallizes S to 1       

		for(int i = 0; i < s; i++){ // calculates the value of S

				S *= 2;
  	}
		cache = (cache_t)malloc(sizeof(cache_set_t)*S); // Allocates Memory for 'S' sets
        
        // Iterates through all the Sets 'S'
 		for(int i = 0; i < S; i++){ 

				*(cache+i)= (cache_set_t)malloc(sizeof(cache_line_t)*E); // Allocates Memory for E lines in the current set

                // Iterates through all lines in the Current Set

				for(int j = 0; j < E; j++){ 

     				(*(*(cache+i)+j)).valid = 0; // Sets valid bit to 0

      			(*(*(cache+i)+j)).tag = 0; // Sets tag bits to 0
                
						(*(*(cache+i)+j)).lru = 0; // Sets the lru count of the line to 0
				}
  	}	
} 

Free Cache Function

Frees all heap allocated memory used by the cache.

void free_cache() {             
        // Iterate backwares through all the Sets
		for(int i = S-1; i >= 0; i--){

  			free(cache[i]);
            cache[i] = 0;               // Frees the Memory each Set is pointing and Sets it to NULL
  	}
  	free(cache); // Frees the Memory Cache
    cache = 0; 
}  

Access Data Function

Simulates data access at a given “address” memory address in the Cache. If already in Cache, increment hit_cnt If not in the Cache, Cache it (set tag), increment miss_cnt If a line is evicted, increment evict_cnt

void access_data(mem_addr_t addr) {      

		// get set and tag
		mem_addr_t tag = addr >> (s+b);
		int set = (addr - (tag << (s+b))) >> b;

		// Hit (Block is in our Cache)
		for(int i = 0; i < E; i++){
				if(cache[set][i].valid && cache[set][i].tag == tag){

						hit_cnt++;

						cache[set][i].lru = lru_counter;

						lru_counter++;

						return;
				}
		}

		// If not a hit, then it will be a miss!

		miss_cnt++;

        // Lets Check the type of Miss (Miss or Miss and Eviction)

		for(int i = 0; i < E; i++){

         if(!cache[set][i].valid){ // if only a miss, then a least one line is not valid

					cache[set][i].valid = 1; // sets validity

				    cache[set][i].lru = lru_counter; // udates counter

				    cache[set][i].tag = tag; // updates tag bit
					
                    return;
					}  
     }

		// if program reaches here, then an eviction should occur
	    evict_cnt++;

    int change_line = 0; // the line to be changed

    // find the line to change

    for(int i = 0; i < E; i++){

        if(cache[set][i].lru < cache[set][change_line].lru)

            change_line = i;
    }
 
		// Update the values in the line to be changed

		cache[set][change_line].lru = lru_counter; // Updates Counter

		cache[set][change_line].tag = tag; // Updates tag

}

Replay Trace

Replays the given Trace file against the Cache, and reads the input trace file line by line.

Extracts the type of each memory access : L/S/M

Translate each ‘L’ as a load i.e. 1 Memory Access Translate each ‘S’ as a store i.e. 1 Memory Access Translate each ‘M’ as a load followed by a store i.e. 2 Memory Access

void replay_trace(char* trace_fn) {           
    char buf[1000];  
    mem_addr_t addr = 0;
    unsigned int len = 0;
    FILE* trace_fp = fopen(trace_fn, "r"); 

    if (!trace_fp) { 
        fprintf(stderr, "%s: %s\n", trace_fn, strerror(errno));
        exit(1);   
    }
    while (fgets(buf, 1000, trace_fp) != NULL) {
        if (buf[1] == 'S' || buf[1] == 'L' || buf[1] == 'M') {
            sscanf(buf+3, "%llx,%u", &addr, &len);
      
            if (verbosity)
                printf("%c %llx,%u ", buf[1], addr, len);

            // GIVEN: 1. addr has the address to be accessed
            //        2. buf[1] has type of acccess(S/L/M)
            // call access_data function here depending on type of access
						if(buf[1] == 'L'){ // checks if buf[1] is of type L
								access_data(addr); // accesses data to load
						}
						else if(buf[1] == 'S'){ // check if buf[1] is of type S
								access_data(addr); // accesses data to store 
						}
						else if(buf[1] == 'M'){ // check if buf[1] is of type M
								access_data(addr); // accesses memory twice
                access_data(addr);
						}
						else{
								// does nothing because buf[1] is not valid
						}
            if (verbosity)
                printf("\n");
        }
    }

    fclose(trace_fp);
}     

Print Usage Function

Prints information on how to use csim to Standard Output. This function is provided.

void print_usage(char* argv[]) {          

    printf("Usage: %s [-hv] -s <num> -E <num> -b <num> -t <file>\n", argv[0]);
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of s bits for set index.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of b bits for block offsets.\n");
    printf("  -t <file>  Trace file.\n");
    printf("\nExamples:\n");
    printf("  macos>  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]);
    printf("  macos>  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]);
    exit(0);
}

Print Summary

Prints summary of the Cache Simulation Statistics of a file passed in. This Function is provided.

void print_summary(int hits, int misses, int evictions) {        

    printf("hits:%d misses:%d evictions:%d\n", hits, misses, evictions);

    FILE* output_fp = fopen(".csim_results", "w");

    assert(output_fp);

    fprintf(output_fp, "%d %d %d\n", hits, misses, evictions);

    fclose(output_fp);
}

Main Function to Run

Main function that makes the Caches and runs everything.

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

    char* trace_file = NULL;
    char c; 

    // Parse the command line arguments: -h, -v, -s, -E, -b, -t 
    while ((c = getopt(argc, argv, "s:E:b:t:vh")) != -1) {
        switch (c) {
            case 'b':
                b = atoi(optarg);
                break;
            case 'E':
                E = atoi(optarg);
                break;
            case 'h':
                print_usage(argv);
                exit(0);
            case 's':
                s = atoi(optarg);
                break;
            case 't':
                trace_file = optarg;
                break;
            case 'v':
                verbosity = 1;
                break;
            default:
                print_usage(argv);
                exit(1);
        }
    }

    //Make sure that all required command line args were specified.
    if (s == 0 || E == 0 || b == 0 || trace_file == NULL) {
        printf("%s: Missing required command line argument\n", argv[0]);
        print_usage(argv);
        exit(1);
    }

    // Initialize Cache.
    init_cache();

    // Replay the memory access trace.
    replay_trace(trace_file);

    // Free memory allocated for cache.
    free_cache();

    //Print the statistics to a file.
    //DO NOT REMOVE: This function must be called for test_csim to work.
    print_summary(hit_cnt, miss_cnt, evict_cnt);
    return 0;   
}           

Compile Program with Makefile

CC = gcc
CFLAGS = -Wall -std=gnu99 -m64 -g

all: csim.c
	$(CC) $(CFLAGS) -o csim csim.c -lm 

#
# Clean the src dirctory
#
clean:
	rm -f csim

Run the Makefile

make

Sould output a csim exectuable file in our directory.

Testing Program

./csim

Output:

./csim: Missing required command line argument
Usage: ./csim [-hv] -s <num> -E <num> -b <num> -t <file>
Options:
  -h         Print this help message.
  -v         Optional verbose flag.
  -s <num>   Number of set index bits.
  -E <num>   Number of lines per set.
  -b <num>   Number of block offset bits.
  -t <file>  Trace file.

Examples:
  macos>  ./csim -s 4 -E 1 -b 4 -t traces/yi.trace
  macos>  ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace

Run with Trace

./csim -s 4 -E 1 -b 4 -t traces/yi.trace