cache_simulator.py

"""
Cache Simulator - written by Friedjof Noweck
  This program simulates a cache with a given associativity, cache line size, and cache size.

  You can find an example of how to use this program in the main function at the bottom of this file.
  This Example simulates a cache with:
    - 2, 4 or 8-way associativity
    - cache line size of 8 Bytes
    - cache size of 128 Bytes
"""

import math                   # For the mod2 function
from datetime import datetime # For the timestamp
import random                 # For choosing a random cache cell to replace and random address generation

"""
Address class
  This class represents an address in memory.
  It contains the address itself, the cache it belongs to, and the tag, index, and offset bits.
  The tag, index, and offset bits are calculated from the address and the cache's parameters.
"""
class Address:
    """
    Constructor
        :param address: The address in memory
        :param cache: The cache the address belongs to
    """
    def __init__(self, address: int, cache: "Cache") -> None:
        self.address: int = address
        self.cache: "Cache" = cache

        self.offset_bits: int = address & ((1 << self.cache.offset_bits) - 1)
        self.index_bits: int = (address >> self.cache.offset_bits) & ((1 << self.cache.index_bits) - 1)
        self.tag_bits: int = address >> (self.cache.offset_bits + self.cache.index_bits)

    """
    Returns the address as a string
        :return The address and tag bits as a string in the format <Address: 0xADDRESS, Tag: 0xTAG>
    """
    def __str__(self) -> str:
        return f"<Address: {hex(self.address)}, Tag: {hex(self.tag_bits)}>"

    def __repr__(self) -> str:
        return self.__str__()

"""
Cache class
    This class represents a cache.
    It contains the cache's parameters, the cache cells, and the cache's hit and miss counters.
"""
class CacheCell:
    """
    Constructor
        :param cache: The cache the cell belongs to
        :param tag: The tag of the cell (optional)
        :param data: The data of the cell (optional)
    """
    def __init__(self, cache: "Cache", tag: int = None, data: list[int] = None):
        self.cache: "Cache" = cache
        self.tag: int = tag
        self.timestamp: float = 0.0

        if data is not None and len(data) != self.cache.cache_cell_size:
            raise ValueError("Data length must be equal to cache line size")

        self.data: list[int] = data if data is not None else [None] * self.cache.cache_cell_size

    """
    Returns the cell's data as a string
        :return The cell's data as a string in the format <Tag: 0xTAG, Data: 0xDATA>
    """
    def is_empty(self) -> bool:
        return self.tag is None

    """
    Returns whether the cell is full
        :return True if the cell is full, False otherwise
    """
    def is_full(self) -> bool:
        return self.tag is not None

    """
    Returns whether the cell's tag matches the given tag
        :param tag: The tag to compare to
        :return True if the cell's tag matches the given tag, False otherwise
    """
    def tag_hit(self, tag: int) -> bool:
        return self.tag == tag

    """
    Returns whether the cell's data matches the given data
        :param data: The data to compare to
        :return True if the cell's data matches the given data, False otherwise
    """
    def get_data(self, offset: int) -> int:
        self._update_timestamp()
        return self.data[offset]

    """
    Sets the cell's data to the given data
        :param data: The data to set the cell's data to
    """
    def set_data(self, data: int, offset: int) -> None:
        if self.tag is not None:
            self.data[offset] = data
            self._update_timestamp()

    """
    Clears the cell's data
    """
    def clear(self) -> None:
        self.timestamp: float = 0.0
        self.tag: int | None = None
        self.data: list[int | None] = [None] * self.cache.cache_cell_size

    """
    Sets the cell's tag to the given tag
        :param tag: The tag to set the cell's tag to
    """
    def set_tag(self, tag: int) -> None:
        self.tag: int = tag
        self.data = [None] * self.cache.cache_cell_size
        self._update_timestamp()

    """
    Returns the cell's data as a string
        :return The cell's data as a string in the format <Tag: 0xTAG, Data: 0xDATA>
    """
    def _data_to_hex(self) -> int:
        result: int = 0
        for i, d in enumerate(self.data):
            d = d if d is not None else 0
            result += d << (i * 8)

        return result

    """
    Updates the cell's timestamp to the current time
    """
    def _update_timestamp(self) -> None:
        self.timestamp = datetime.now().timestamp()

    """
    Returns the cell's data as a string
        :return The cell's data as a string in the format <Tag: 0xTAG, Data: 0xDATA>
    """
    def __str__(self) -> str:
        return f"({hex(self.tag) if self.tag is not None else '0x0':8}: {hex(self._data_to_hex()):4})"

"""
Cache class
    This class represents a cache.
    It contains the cache's parameters, the cache cells, and the cache's hit and miss counters.
"""
class Cache:
    """
    Constructor
        :param associativity: The cache's associativity
        :param cache_line_size: The cache's cache line size
        :param cache_size: The cache's size
        :param address_bits: The number of bits in an address (default: 32)
    """
    def __init__(self, associativity: int, cache_line_size: int, cache_size: int, address_bits: int = 32):
        self.associativity: int = associativity     # Number of cache cells per index
        self.cache_cell_size: int = cache_line_size # Number of bytes per cache cell
        self.cache_size: int = cache_size           # Number of bytes in the cache
        self.address_bits: int = address_bits       # Number of bits in an address

        self.offset_bits: int = int(math.log2(cache_line_size))                               # Number of bits in an offset
        self.index_bits: int = int(math.log2(cache_size // cache_line_size // associativity)) # Number of bits in an index
        self.tag_bits: int = address_bits - self.index_bits - self.offset_bits                # Number of bits in a tag

        # Initialize the cache as a 2D array of zeros
        self.cache: list[list[CacheCell]] = [[CacheCell(self) for _ in range(associativity)] for _ in range(2 ** self.index_bits)]

    """
    Returns the offset of the given address
        :param address: The address to get the offset of
        :return The offset of the given address
    """
    def get_offset(self, address: int) -> int:
        return address & ((1 << self.offset_bits) - 1)

    """
    Returns the address's index
        :param address: The address to get the index of
        :return The address's index
    """
    def get_index(self, address: int) -> int:
        return (address >> self.offset_bits) & ((1 << self.index_bits) - 1)

    """
    Returns the tag of the given address
        :param address: The address to get the tag of
        :return The tag of the given address
    """
    def get_tag(self, address: int) -> int:
        return address >> (self.offset_bits + self.index_bits)

    """
    Returns the cache cell at the given address
        :param address: The address to get the cache cell at
        :return The cache cell at the given address
    """
    def get_data(self, address: Address) -> int | None:
        for cell in self.cache[address.index_bits]:
            if cell.tag_hit(address.tag_bits):
                return cell.get_data(address.offset_bits)

        return None

    """
    Returns the cell's in the given address's set
        :param address: The address to get the set of
        :return The cell's in the given address's set
    """
    def get_set(self, address: Address) -> list[CacheCell]:
        return self.cache[address.index_bits]

    """
    Returns whether or not the given address's set is full
        :param address: The address to check if the set is full
        :return Whether or not the given address's set is full
    """
    def set_is_full(self, address: Address) -> bool:
        return all([cell.is_full() for cell in self.get_set(address)])

    """
    Returns the first empty cell in the given address's set
        :param address: The address to get the first empty cell of
        :return The first empty cell in the given address's set
    """
    def get_empty_cell(self, address: Address) -> CacheCell | None:
        for cell in self.get_set(address):
            if cell.is_empty():
                return cell
        return None

    """
    Returns the index of the cell in the given address's set that has the given tag
        :param address: The address to get the tag hit of
        :return The index of the cell in the given address's set that has the given tag
    """
    def tag_hit(self, address: Address) -> int | None:
        for i, cell in enumerate(self.get_set(address)):
            if cell.tag_hit(address.tag_bits):
                return i
        return None

    """
    Returns the cell in the given address's set that has the oldest timestamp
        :param address: The address to get the oldest cell of
        :return The cell in the given address's set that has the oldest timestamp
    """
    def set_data(self, address: Address, data: int = 0x00) -> None:
        tag_hit: int | None = self.tag_hit(address)

        if tag_hit is not None:
            self.get_set(address)[tag_hit].set_data(data=data, offset=address.offset_bits)
        else:
            if not self.set_is_full(address):
                empty_cell: CacheCell | None = self.get_empty_cell(address)
                if empty_cell is not None:
                    empty_cell.set_tag(address.tag_bits)
                    empty_cell.set_data(data=data, offset=address.offset_bits)
            else:
                oldest_cell: CacheCell = self._get_oldest_cell_from_set(address)
                oldest_cell.set_tag(address.tag_bits)
                oldest_cell.set_data(data=data, offset=address.offset_bits)

    """
    Sets the cache to the given cells; useful if you have given cells at the start of the program
        :param cells: The cells to set the cache to
    """
    def set_cells(self, cells: list[list[CacheCell]]) -> None:
        for i, cell_set in enumerate(cells):
            for j, cell in enumerate(cell_set):
                self.cache[i][j] = cell

    """
    Returns the cell in the given address's set that has the oldest timestamp
        :param address: The address to get the oldest cell of
        :return The cell in the given address's set that has the oldest timestamp
    """
    def _get_oldest_cell_from_set(self, address: Address) -> CacheCell:
        return min(self.get_set(address), key=lambda cell: cell.timestamp)

    """
    Returns the solution to the cache
        :return The solution to the cache in a specific format
    """
    def solution(self) -> str:
        line_separator: str = "           |" + "----------|" * self.associativity + "\n"
        solution: str = line_separator

        for i, cell_set in enumerate(self.cache):
            solution += f"Set {i:0>3} => |"
            for cell in cell_set:
                solution += f"{hex(cell.tag) if cell.tag is not None else '':10}|"
            solution += "\n" + line_separator

        return solution

    """
    Returns the cache as a string
        :return The cache as a string in a readable format for debugging
    """
    def __str__(self):
        return f"<Cache Size: {self.cache_size}, associative: {self.associativity}, Cell Size: {self.cache_cell_size}\n" + "\n".join(
            ["Set {} => {}".format(
                i, ', '.join(
                    [f'{str(cell):16}' for cell in b]
                )
            ) for i, b in enumerate(self.cache)]
        ) + ">"

    def __repr__(self):
        return self.__str__()


if __name__ == '__main__':
    # Initialize the cache
    c: Cache = Cache(
        associativity=random.choice([2, 4, 8]), # Choose a random associativity
        cache_line_size=8,                      # 8 bytes (The size of a Cell)
        cache_size=128,                         # 128 bytes (The size of the Cache)
        address_bits=16                         # 16 bits (The size of the address) **optional**
    )

    # Random address Data
    addr: list[int] = [
        random.randint(0, 2 ** 32 - 1) for _ in range(random.randint(5, 15))
    ]

    # Set the addresses
    for a in addr:
        c.set_data(Address(a, c))

    # Print the solution
    print(c.solution())