Need Help in implementing policies(lru , lfu, high and low) for Cachelab code included below:

#include #include #include #include #include #include #include

typedef struct { int valid; uintptr_t tag; int lru; int lfu; int high; int low; //more } line_t;

typedef struct { line_t* lines; } set_t;

typedef enum{ POLICY_LRU = 0, POLICY_LFU, POLICY_HIG, POLICY_LOW, }cache_policy_t;

typedef struct { unsigned s, E, b; unsigned hits, misses, evictions; cache_policy_t policy; set_t* sets; } cache_t;

void simulate (const char* file, unsigned s, unsigned E, unsigned b, cache_policy_t policy); void init_cache (cache_t* cache, unsigned s, unsigned E, unsigned b, cache_policy_t policy); void destroy_cache_sets (cache_t* cache); void touch (cache_t* cache, uintptr_t address);

int main (int argc, char** argv) { unsigned s = 0, E = 0, b = 0; char* filename = NULL; cache_policy_t policy = 0; char c;

while ((c = getopt (argc, argv, "s:E:b:t:p:")) != -1){ switch(c){ case 's': s = atoi (optarg); break; case 'E': E = atoi (optarg); break; case 'b': b = atoi (optarg); break; case 'p': if (strcmp (optarg, "lru") == 0) { policy = POLICY_LRU; } else if (strcmp (optarg, "lfu") == 0) { policy = POLICY_LFU; } else if(strcmp(optarg, "low") == 0) { policy = POLICY_LOW; } else if(strcmp(optarg, "high") == 0) { policy = POLICY_HIG; } break; case 't': filename = optarg; default: exit(2); }

}

if (s == 0 || E == 0 || b == 0 || filename == NULL || policy == 0) exit(1);

simulate (filename, s, E, b, policy); return 0; }

#define error(A...) do { fprintf (stderr, A); exit(1);} while (0) void simulate (const char* file, unsigned s, unsigned E, unsigned b, cache_policy_t policy){ cache_t tcache; cache_t* cache = &tcache;

init_cache (cache, s, E, b, policy);

FILE* f = fopen (file, "r"); if(f == NULL) error ("%s: could not open file. ", file);

char line[32]; while (fgets (line,32,f)){ if(line[0] == 'I' || line[1] == 'M' || line[1] == 'L' || line[1] == 'S') touch (cache, strtoul (line + 3, NULL, 16)); if(line[1] == 'M') touch (cache, strtoul (line + 3, NULL, 16)); } fclose (f); print_summary (cache->hits, cache->misses, cache->evictions); destroy_cache_sets (cache); }

void init_cache (cache_t* cache, unsigned s, unsigned E, unsigned b, cache_policy_t policy){ cache->s = s; cache->E = E; cache->b = b; cache->policy = policy; unsigned S = (1 << s); cache->sets = (set_t*) malloc (S * sizeof (set_t)); for( int i = 0; i < S; ++i) { cache->sets[i].lines = (line_t*) malloc (E * sizeof (line_t)); for(int j = 0; j < E; ++i) { cache->sets[i].lines[j].valid = 0; cache->sets[i].lines[j].tag = 0; cache->sets[i].lines[j].lru = 0; cache->sets[i].lines[j].lfu = 0; cache->sets[i].lines[j].high = 0; cache->sets[i].lines[j].low = 0;

} } }

void destroy_cache_sets (cache_t* cache){ // free cache->sets[i].lines for all i // free cache->sets unsigned s; cache->s = s; unsigned S = (1 << s);

for(int i = 0; i < S; ++i)

free(cache->sets[i].lines); free(cache->sets); }

void touch (cache_t* cache, uintptr_t address){ uintptr_t tag = address >> (cache->s + cache->b); uintptr_t set_index = 0; int cache->hit = 0; int cache->miss = 0;

//Is "tag" the tag of a line in cache->sets[set_index]? //Yes: cache->hit++; //No: cache->miss++; // if cache->sets[set_index] is full, evict a line // depending on policy // insert line with tag "tag" in the set.

cache->hit++;

else{ cache->miss++; } if(cache-sets[set_index] == 1)

}

The Notes for creating the policies are below:

4.3 Part 1: LRU Policy (60pts)

The Least Recently Used (LRU) policy is the one we have seen in the lectures. When a set is full and a new line needs to be inserted, the evicted line is the one that was least recently used. This means that each line should carry this extra bit of information and that the cache should have a notion of time (this is not the actual time, but a variable that is incremented with each line read from the trace). Each time a line is hit or inserted, its timestamp should be updated with the current time.

4.4 Part 2: LFU Policy (70pts)

The Least Frequency Used (LFU) policy favors eviction of lines that were least accessed since they got inserted. This means that each line should carry this extra bit of information. Each time a line is hit, its use counter should be incremented. Each time a line is inserted, its use counter is set to 1 (the line has been used, that is accessed, once).

If more than one line have the same lowest frequency, the line with lowest tag is evicted.

4.5 Part 3: HIG Policy (50pts)

The HIG policy favors eviction of lines with highest address. Since eviction takes place in a given set, this simply means that the line with highest tag will get evicted.

4.6 Part 4: LOW Policy (20pts)

The LOW policy favors eviction of lines with lowest address. Since eviction takes place in a given set, this simply means that the line with lowest tag will get evicted.