cache.py

from common import eprint
from linkedlist import LinkedList
import math 

from abc import ABC
import heapq


# Abstract Base class acting as template for cache implementations, and contains some common methods

class Cache(ABC):

    # Initialises cache state variables 
    def __init__(self, name, size, line_size, kind, mem_addr_bit_length = 64):
        self.name = name
        self.size = size
        self.line_size = line_size
        self.kind = kind
        self.num_cache_lines = int(size / line_size)
        self.mem_addr_bit_length = mem_addr_bit_length

        # Maps the kind of cache to its level of associativity
        self.way_associativity = self._map_kind_to_associativity()

        # Calculating index, tag and offset bit lengths - assuming memory is byte-addressable (opposed to word-addressable)
        self.offset_length = int(math.log2(line_size))
        self.number_of_sets = int(self.num_cache_lines / self.way_associativity)

        self.index_length = int(math.log2(self.number_of_sets))
        self.tag_length = int(mem_addr_bit_length - self.index_length - self.offset_length)

        # This cache simulator allows the user to work with memory addresses that aren't 64 bits, so need safety checks 
        if self.tag_length <= 0 :
            eprint(f"[Error] Memory address bit length ({mem_addr_bit_length}) is too small for implementing cache")
            eprint(f"[Error] Offset bit length = {self.offset_length}, Index bit length = {self.index_length}")
            return None


    # Resets cache state for processing trace file
    def reset_simulation(self):
        # Reset performance metric counters
        self.hits = 0
        self.misses = 0


    # Maps the kind of cache to its level of associativity
    def _map_kind_to_associativity(self):
        if self.kind == "direct":
            return 1 # one-way
        elif self.kind == "full":
            return self.num_cache_lines
        else:
            # nway - extracting 'n' value
            return int(self.kind[:-3])


    # Performs memory operation - W/R type ignored
    def step(tag, index, mem_op_size):
        pass



# Direct Mapped Cache Implementation

class DirectCache(Cache):

    def __init__(self, name, size, line_size, kind, mem_addr_bit_length=64):
        super().__init__(name, size, line_size, kind, mem_addr_bit_length)
        super().reset_simulation()

        # tag_maintainer is an array data structure for storing cache tags during runtime, 
        # which can be used to check for hits or misses
        self.tag_maintainer = [-1] * self.num_cache_lines

    # Perform a step of the trace file
    def step(self, mem_addr_int, mem_op_size):
        
        # Extract index and tag 
        index = int((mem_addr_int >> self.offset_length) & ((1 << self.index_length) - 1))
        tag = int((mem_addr_int >> (self.offset_length + self.index_length)) & ((1 << self.tag_length) - 1))

        # Determine where to start looking for tag in tag_maintainer (which is a contiguous data structure)
        target_cache_line_index = (index * self.way_associativity)

        # Check if cache line full/valid
        if self.tag_maintainer[target_cache_line_index] != -1:
            # Check if tags match
            if self.tag_maintainer[target_cache_line_index] == tag:
                self.hits = self.hits + 1
                eprint(f"[Debug - Cache {self.name}] Hit with Tag {tag}")
                return True
        
        self.misses = self.misses + 1
        eprint(f"[Debug - Cache {self.name}] Miss with Tag {tag}")
        self.tag_maintainer[target_cache_line_index] = tag # replace existing tag with new tag  
        return False




# Associative Caches

# Cache for supporting the Round Robin replacement policy
class RRCache(Cache):

    def __init__(self, name, size, line_size, kind, mem_addr_bit_length=64):
        super().__init__(name, size, line_size, kind, mem_addr_bit_length)
        self.reset_simulation()


    def reset_simulation(self):
        super().reset_simulation()
        
        # tag_maintainer is an array data structure for storing cache tags during runtime, 
        # which can be used to check for hits or misses
        self.tag_maintainer = [None] * self.num_cache_lines

        # Due to the O(1) lookup time complexity of sets, I use them to check for cache hits/misses 
        self.tag_sets = []
        self.victim_counters = [] # A counter for each cache set, which points at the cache line to be replaced 
        for _ in range(self.number_of_sets):
            self.tag_sets.append(set())
            self.victim_counters.append([0, 0]) # [Ptr to cache line (in cache set) to be replaced, Ptr to next free space in cache set]
            # ^ The second value in victim counters [_,x] gives O(1) lookup time for empty cache lines
            # I decided to include this so that my cache doesn't have to perform a linear search (O(n) time complexity) 
            # - but obviously this comes at the cost of more memory usage
        
    # Adds tag to cache
    def _add_tag_to_cache(self, target_tag_string, cache_line_index):
        self.tag_maintainer[cache_line_index] = target_tag_string # store tag information


    # RR replacement policy implementation
    def _follow_replacement_policy(self, target_tag_string, cache_line_start_index, set_index):
        # Determine next cache line to be removed
        index_cache_line_to_be_removed = cache_line_start_index + self.victim_counters[set_index][0]

        # Remove old tag from set
        self.tag_sets[set_index].remove(self.tag_maintainer[index_cache_line_to_be_removed])

        # Increment victim counter using modulo
        self.victim_counters[set_index][0] = (self.victim_counters[set_index][0] + 1) % self.way_associativity

        # Update tags
        self._add_tag_to_cache(target_tag_string, index_cache_line_to_be_removed)

        # Add new tag to set
        self.tag_sets[set_index].add(target_tag_string)

    # Step through trace file
    def step(self, mem_addr_int, mem_op_size):

        # Extract tag from mem_address
        tag_int = int((mem_addr_int >> (self.offset_length + self.index_length)) & ((1 << self.tag_length) - 1))

        if self.index_length == 0: # fully associative cache has only one set
            set_index = 0
        else:
            set_index = int((mem_addr_int >> self.offset_length) & ((1 << self.index_length) - 1))
        
        # Calculate where to start looking in cache (since its a contigous block of memory)
        start_index = (set_index * self.way_associativity)

        if tag_int in self.tag_sets[set_index]:
            # Cache hit
            self.hits = self.hits + 1
            eprint(f"[Debug - Cache {self.name}] Hit with Tag {tag_int}")
            return True
        else:
            # Cache miss
            if len(self.tag_sets[set_index]) == self.way_associativity:
                # cache set is full
                self._follow_replacement_policy(tag_int, start_index, set_index)
            else:
                # next empty space
                next_free_line_index = self.victim_counters[set_index][1]
                self._add_tag_to_cache(tag_int, start_index + next_free_line_index)
                # Update victim counter to point to next cache line (FIFO)
                self.victim_counters[set_index][1] = (next_free_line_index + 1) % self.way_associativity

                # Add new tag to set
                self.tag_sets[set_index].add(tag_int)

            self.misses = self.misses + 1
            eprint(f"[Debug - Cache {self.name}] Miss with Tag {tag_int}")
            return False
                

# Cache for supporting the Least Recently Used replacement policy
class LRUCache(Cache):

    def __init__(self, name, size, line_size, kind, mem_addr_bit_length=64):
        super().__init__(name, size, line_size, kind, mem_addr_bit_length)
        self.reset_simulation()

    # I have decided to use a doubly linked list for tracking the order of accesses (nodes = tag values)
    # because this allows easy retrieval and updating of cache positions without having to record their indices
    # in the cache
    def reset_simulation(self):
        super().reset_simulation()

        self.access_order_tracker = []
        self.tag_sets = []
        for _ in range(self.number_of_sets):
            self.access_order_tracker.append(LinkedList(self.way_associativity))
            self.tag_sets.append(set())


    # Implementation of replacement policy 
    def _follow_replacement_policy(self, target_tag, set_index):
        # Remove Least recently used cache line
        tag = self.access_order_tracker[set_index].pop_cache_line()

        # Update tag set
        self.tag_sets[set_index].remove(tag)
        self.tag_sets[set_index].add(target_tag)

        # Register new cache line in access tracker data structure
        self.access_order_tracker[set_index].push_cache_line(target_tag)
    
    # Step through trace file 
    def step(self, mem_addr_int, mem_op_size):
        
        tag_int = int((mem_addr_int >> (self.offset_length + self.index_length)) & ((1 << self.tag_length) - 1))

        if self.index_length == 0: # fully associative cache
            set_index = 0
        else:
            set_index = int((mem_addr_int >> self.offset_length) & ((1 << self.index_length) - 1))


        if tag_int in self.tag_sets[set_index]:
            # Cache hit
            self.hits = self.hits + 1
            self.access_order_tracker[set_index].update_access_tracker(tag_int) # move tag in list to front (most recently accessed)
            eprint(f"[Debug - Cache {self.name}] Hit with Tag {tag_int}")
            return True

        else:
            # Cache miss
            if len(self.tag_sets[set_index]) == self.way_associativity:
                # cache set is full
                self._follow_replacement_policy(tag_int, set_index)
            else:               
                # Add to access order tracker
                self.access_order_tracker[set_index].push_cache_line(tag_int)

                # Add new tag to set
                self.tag_sets[set_index].add(tag_int)

            self.misses = self.misses + 1
            eprint(f"[Debug - Cache {self.name}] Miss with Tag {tag_int}")
            return False


# Cache for supporting the Least Frequently Used replacement policy
class LFUCache(Cache):

    def __init__(self, name, size, line_size, kind, mem_addr_bit_length=64):
        super().__init__(name, size, line_size, kind, mem_addr_bit_length)
        self.reset_simulation()


    def reset_simulation(self):
        super().reset_simulation()

        # To remember tag order
        self.tag_maintainer = [None] * self.num_cache_lines
        self.frequency_tracker = [0] * self.num_cache_lines # counter for every cache line frequency


        # Set to quickly identify whether miss or hit
        self.tag_sets = []
        self.tag_to_indices = []
        for _ in range(self.number_of_sets):
            self.tag_sets.append(set())
            self.tag_to_indices.append(dict()) # O(1) retrieval for updating the frequency of tag hits


    # Implementation of LFU replacement policy 
    def _follow_replacement_policy(self, target_tag, set_index):

        # Remove Least Frequently used cache line
        start_index = (set_index * self.way_associativity)
        smallest_freq_seen = self.frequency_tracker[start_index]
        index_of_smallest_freq = start_index
        
        # Must loop through all possible cache lines to find it
        for i in range(1, self.way_associativity):
            current_index = start_index + i
            freq = self.frequency_tracker[current_index]
            if(freq < smallest_freq_seen): # not <= to evict line with lowest index
                smallest_freq_seen = freq
                index_of_smallest_freq = current_index

        # Update tag set
        tag_to_remove = self.tag_maintainer[index_of_smallest_freq]
        self.tag_sets[set_index].remove(tag_to_remove)
        self.tag_sets[set_index].add(target_tag)

        # Update tag-to-index
        del self.tag_to_indices[set_index][tag_to_remove]
        self.tag_to_indices[set_index][target_tag] = index_of_smallest_freq

        # Remove and reset frequency tracker
        self.frequency_tracker[index_of_smallest_freq] = 0
        self.tag_maintainer[index_of_smallest_freq] = target_tag


    # Step through trace file 
    def step(self, mem_addr_int, mem_op_size):
        # Extract tag 
        tag_int = int((mem_addr_int >> (self.offset_length + self.index_length)) & ((1 << self.tag_length) - 1))

        if self.index_length == 0: # fully associative cache
            set_index = 0
        else:
            set_index = int((mem_addr_int >> self.offset_length) & ((1 << self.index_length) - 1))

        if tag_int in self.tag_sets[set_index]:
            # Cache hit
            self.hits = self.hits + 1

            # Increment freq_tracker
            self.frequency_tracker[self.tag_to_indices[set_index][tag_int]] += 1 
            # decided to optimise this operation using a dictionary since hits occur more often in caches than misses
 
            eprint(f"[Debug - Cache {self.name}] Hit with Tag {tag_int}")
            return True

        else:
            # Cache miss
            if len(self.tag_sets[set_index]) == self.way_associativity:
                # cache set is full
                self._follow_replacement_policy(tag_int, set_index)
            else:               
                start_index = (set_index * self.way_associativity)

                for i in range(0, self.way_associativity): # linear search when filling up cache set -> only happens when filling up
                    current_index = start_index + i
                    if(self.tag_maintainer[current_index] == None):
                        empty_index = current_index
                        break
        
                # Add to frequency tracker
                self.frequency_tracker[empty_index] = 0

                # Add to tag maintainer
                self.tag_maintainer[empty_index] = tag_int

                # Add new tag to set
                self.tag_sets[set_index].add(tag_int)

                # Add to tag-to-index tracker
                self.tag_to_indices[set_index][tag_int] = empty_index

            self.misses = self.misses + 1
            eprint(f"[Debug - Cache {self.name}] Miss with Tag {tag_int}")
            return False