Cache-Simulator.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyMNFByHI+nSUF0fukrcPzR0",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/TylerFlar/Cache-Simulator/blob/main/Cache-Simulator.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Import Libraries"
      ],
      "metadata": {
        "id": "PzsNVlGBrIoN"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math\n",
        "from datetime import datetime\n",
        "import csv"
      ],
      "metadata": {
        "id": "AZ8aHpRKrMcc"
      },
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Define Your Achitecture\n",
        "\n",
        "Remember the formula: $\\text{Cache Size} = \\text{Associativity} \\times \\text{Block Size} \\times \\text{Sets}$\n",
        "\n",
        "\n",
        "\n",
        "* **Address Size:** Number of bits in an address (usually 32bit or 64bit)\n",
        "* **Cache Size:** Total size of cache in bytes.\n",
        "* **Block Size:** Number of bytes per line.\n",
        "* **Associativity:** (a.k.a Way-Associativity): Number of parallel cache lines.  \n",
        "* **Sets:** Number of lines in cache per \"way.\""
      ],
      "metadata": {
        "id": "OeuSqfgHom9y"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "EDIT THE PARAMATERS OR LEAVE AS DEFAULT\n",
        "\"\"\"\n",
        "\n",
        "ADDRESS_SIZE = 64\n",
        "CACHE_SIZE = 32 * 1024\n",
        "BLOCK_SIZE = 64\n",
        "ASSOCIATIVITY = 8\n",
        "SETS = int(CACHE_SIZE / (BLOCK_SIZE * ASSOCIATIVITY))"
      ],
      "metadata": {
        "id": "K_voLWL7okZS"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Setup Cache Simulator\n",
        "\n",
        "### Cache Memory Structure:\n",
        "1. **OFFSET_BITS:**\n",
        "This calculates the number of bits needed to represent an offset within a block of the cache. This is done by taking the base-2 logarithm of the block size.\n",
        "1. **INDEX_BITS:**\n",
        "This calculates the number of bits needed to represent the index of a set within the cache. The number of sets is determined by the total cache size divided by the size of each set (BLOCK_SIZE * ASSOCIATIVITY). The base-2 logarithm of this value gives the number of bits needed.\n",
        "1. **TAG_BITS:**\n",
        "The remaining bits in the address after accounting for offset and index bits are used for the tag. This ensures that each memory address can be broken down into a tag, an index, and an offset.\n",
        "\n",
        "### Cache Access Counters:\n",
        "1. **total_accesses, total_hits, total_misses:**\n",
        "These are counters to keep track of the total number of cache accesses, hits (successful finds in the cache), and misses (unsuccessful finds) respectively.\n",
        "1. **compulsory_misses, capacity_misses, conflict_misses:** These counters segregate the types of misses:\n",
        "  * **Compulsory Miss:** The first time a particular piece of data is accessed and isn't in the cache.\n",
        "  * **Capacity Miss:** Occurs because the cache cannot contain all the blocks needed during execution due to its limited size.\n",
        "  * **Conflict Miss:** Occurs if multiple locations in the main memory map to the same location in the cache.\n",
        "\n",
        "### Cache Data Structure:\n",
        "1. **class Entry:**\n",
        "Represents a single entry in the cache, containing the tag of the memory address, the index (which set it belongs to), and a time timestamp to determine when it was last accessed. This timestamp can be used for cache replacement policies like LRU (Least Recently Used).\n",
        "1. **cache:**\n",
        "Represents the cache itself. It's a list of lists, where each inner list is a \"set\" in a set-associative cache. The number of sets is determined by the SETS value.\n",
        "1. **conflict_archive, capacity_archive:**\n",
        "Lists that store cache entries which were evicted due to conflict misses and capacity misses, respectively.\n",
        "\n",
        "### Data Recording:\n",
        "1. **create_csv:**\n",
        "A function that accepts a filename and a list of data to create a CSV file. This CSV file will contain information about each cache access, whether it was a hit or a miss, and the type of miss if applicable.\n",
        "1. **csv_data:**\n",
        "A list to store information about each cache access for later writing to the CSV.\n",
        "\n",
        "### Cache Access Function:\n",
        "1. **handle_address:**\n",
        "This function simulates accessing the cache with a given memory address. It breaks down the address into its tag, index, and offset using the previously calculated bit values. Then it checks if the address is in the cache (a hit) or not (a miss).\n",
        "  * If it's a hit, the hit counter is incremented.\n",
        "  * If it's a miss, it determines the type of miss, updates the appropriate counters, and manages adding/removing entries in/from the cache based on the cache's set associativity and potential full sets.\n",
        "  \n",
        "For each cache access (hit or miss), information about the access is appended to the csv_data list for future recording in a CSV file."
      ],
      "metadata": {
        "id": "KZAzsx56q1ok"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "DO NOT TOUCH\n",
        "\"\"\"\n",
        "\n",
        "OFFSET_BITS = int(math.log2(BLOCK_SIZE))\n",
        "INDEX_BITS = int(math.log2(CACHE_SIZE / (BLOCK_SIZE * ASSOCIATIVITY)))\n",
        "TAG_BITS = ADDRESS_SIZE - OFFSET_BITS - INDEX_BITS\n",
        "\n",
        "total_accesses = 0\n",
        "total_hits = 0\n",
        "total_misses = 0\n",
        "compulsory_misses = 0\n",
        "capacity_misses = 0\n",
        "conflict_misses = 0\n",
        "\n",
        "class Entry:\n",
        "    def __init__(self, tag, index, time):\n",
        "        self.tag = tag\n",
        "        self.index = index\n",
        "        self.time = time\n",
        "\n",
        "cache = [[] for i in range(SETS)]\n",
        "conflict_archive = []\n",
        "capacity_archive = []\n",
        "\n",
        "def create_csv(filename, data):\n",
        "    with open(filename, 'w', newline='') as csvfile:\n",
        "        fieldnames = ['array element', 'memory address', 'tag', 'index', 'hit/miss', 'miss type']\n",
        "        writer = csv.DictWriter(csvfile, fieldnames=fieldnames)\n",
        "        writer.writeheader()\n",
        "        for row in data:\n",
        "            writer.writerow(row)\n",
        "\n",
        "csv_data = []\n",
        "\n",
        "def handle_address(address, array_name, array_index):\n",
        "    global total_accesses\n",
        "    global total_hits\n",
        "    global total_misses\n",
        "    global compulsory_misses\n",
        "    global capacity_misses\n",
        "    global conflict_misses\n",
        "\n",
        "    total_accesses += 1  # Incrementing the total accesses\n",
        "\n",
        "    address_bin = bin(address)[2:].zfill(ADDRESS_SIZE)\n",
        "    tag = int(address_bin[:-OFFSET_BITS - INDEX_BITS], 2)\n",
        "    index = int(address_bin[-OFFSET_BITS - INDEX_BITS:-OFFSET_BITS], 2)\n",
        "    offset = int(address_bin[-OFFSET_BITS:], 2)\n",
        "\n",
        "    hit_or_miss = \"miss\"\n",
        "    miss_type = \"N/A\"\n",
        "\n",
        "    # Check for hit\n",
        "    for table in cache:\n",
        "        for entry in table:\n",
        "            if entry.index == index and entry.tag == tag:\n",
        "                total_hits += 1\n",
        "                entry.time = datetime.now()\n",
        "                hit_or_miss = \"hit\"\n",
        "                break\n",
        "        if hit_or_miss == \"hit\":\n",
        "            break\n",
        "\n",
        "    if hit_or_miss == \"miss\":\n",
        "        total_misses += 1\n",
        "        table = cache[index]\n",
        "        # Check if the set is not full\n",
        "        if len(table) < ASSOCIATIVITY:\n",
        "            table.append(Entry(tag, index, datetime.now()))\n",
        "            if any(entry.index == index and entry.tag == tag for entry in capacity_archive):\n",
        "                capacity_misses += 1\n",
        "                miss_type = \"capacity\"\n",
        "            elif any(entry.index == index and entry.tag == tag for entry in conflict_archive):\n",
        "                conflict_misses += 1\n",
        "                miss_type = \"conflict\"\n",
        "            else:\n",
        "                compulsory_misses += 1\n",
        "                miss_type = \"compulsory\"\n",
        "        else:\n",
        "            oldest_entry = min(table, key=lambda x: x.time)\n",
        "            table.remove(oldest_entry)\n",
        "            conflict_archive.append(oldest_entry)\n",
        "            table.append(Entry(tag, index, datetime.now()))\n",
        "            if any(entry.index == index and entry.tag == tag for entry in capacity_archive):\n",
        "                capacity_misses += 1\n",
        "                miss_type = \"capacity\"\n",
        "            elif any(entry.index == index and entry.tag == tag for entry in conflict_archive):\n",
        "                conflict_misses += 1\n",
        "                miss_type = \"conflict\"\n",
        "            else:\n",
        "                compulsory_misses += 1\n",
        "                miss_type = \"compulsory\"\n",
        "\n",
        "    # Append data for CSV\n",
        "    csv_data.append({\n",
        "        'array element': f\"{array_name}[{array_index}]\",\n",
        "        'memory address': hex(address),\n",
        "        'tag': hex(tag),\n",
        "        'index': hex(index),\n",
        "        'hit/miss': hit_or_miss,\n",
        "        'miss type': miss_type\n",
        "    })"
      ],
      "metadata": {
        "id": "IELtJ2jSreF1"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Define Code to Simulate\n",
        "\n",
        "handle_address(uint64_t, string, int): Takes in a memory address, a label (for the CSV file) and a index (for the CSV file)."
      ],
      "metadata": {
        "id": "ZDIUuiBztn3Y"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "ADD CUSTOM CODE TO SIMULATE\n",
        "\n",
        "Example C Code:\n",
        "double a[16384], b[16384], c[16384], d[16384], e[16384];\n",
        "/* a = 0x10000, b = 0x20000, c = 0x30000, d = 0x40000, e = 0x50000 */\n",
        "for (i = 0; i < 512; i++) {\n",
        "  e[i] = (a[i] * b[i] + c[i])/d[i];\n",
        "  // load a[i], b[i], c[i], d[i] and then store to e[i]\n",
        "}\n",
        "\n",
        "\"\"\"\n",
        "# Starting Addresses\n",
        "A_START = 0x10000\n",
        "B_START = 0x20000\n",
        "C_START = 0x30000\n",
        "D_START = 0x40000\n",
        "E_START = 0x50000\n",
        "\n",
        "for i in range(512):\n",
        "      handle_address(A_START + (i * 8), \"A\", i) # i * 8 because there are 8 bytes in a double and A, B, C, D, and E are arrays of doubles.\n",
        "      handle_address(B_START + (i * 8), \"B\", i)\n",
        "      handle_address(C_START + (i * 8), \"C\", i)\n",
        "      handle_address(D_START + (i * 8), \"D\", i)\n",
        "      handle_address(E_START + (i * 8), \"E\", i)"
      ],
      "metadata": {
        "id": "6d0kz8h7rwqT"
      },
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Print and Save Results"
      ],
      "metadata": {
        "id": "7Y4JVhq0v1He"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\"\"\"\n",
        "DO NOT TOUCH\n",
        "\"\"\"\n",
        "\n",
        "print(\"Total accesses: \" + str(total_accesses))\n",
        "print(\"Total hits: \" + str(total_hits))\n",
        "print(\"Total misses: \" + str(total_misses))\n",
        "print(\"Miss rate: \" + str(total_misses / total_accesses))\n",
        "print(\"Compulsory misses: \" + str(compulsory_misses))\n",
        "print(\"Capacity misses: \" + str(capacity_misses))\n",
        "print(\"Conflict misses: \" + str(conflict_misses))\n",
        "\n",
        "\n",
        "csv_filename = \"cache_simulation.csv\"\n",
        "create_csv(csv_filename, csv_data)"
      ],
      "metadata": {
        "id": "YS-gZu59ujXZ"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}