venkat_hw2problem1.ipynb

hw2problem1.ipynb

{
  "cells": [
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "from collections import defaultdict",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "history = [\n    (0x1c6, 1),\n    (0x21f, 0),\n    (0x309, 0),\n    (0x21f, 0),\n    (0x309, 0),\n    (0x1c6, 1),\n    (0x309, 0),\n    (0x1c6, 1),\n    (0x21f, 1)\n]",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Helper Functions"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def xor(a,b):\n    if isinstance(a, tuple) and isinstance(b, tuple):\n        return tuple(map(lambda x: x[0]^x[1], zip(a,b)))\n    else:\n        return a^b",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def update_branch_history_adaptive(branch_history, is_taken):\n    if branch_history[0] != branch_history[1]: # one of the two \"conflicted\" states;\n            return (is_taken, is_taken)\n    else:\n        if branch_history[0] == is_taken:\n            # already at correct prediction\n            return branch_history\n        else:\n            # set second bit to indicate that the prediction should change on next miss\n            return (branch_history[0], is_taken)",
      "execution_count": 4,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def update_branch_history_saturating(branch_history, is_taken):\n    n = branch_history[0] * 2 + branch_history[1]\n    diff = is_taken*2- 1\n    n += diff\n    n = max(n, 0)\n    n = min(n,3)\n    update = (n//2, n % 2)\n    return update",
      "execution_count": 5,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# which history updating scheme seems to make no difference\nupdate_branch_history = update_branch_history_saturating",
      "execution_count": 6,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Defining the branch predictors"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "class TwoLevelLocal():\n    pattern_history_table = {\n        (0,0): (0,0),\n        (0,1): (0,0),\n        (1,0): (0,0),\n        (1,1): (0,0)\n    }\n    \n    branch_history_table = {\n        (0,0): (0,0),\n        (0,1): (0,0),\n        (1,0): (0,0),\n        (1,1): (0,0),\n    }\n\n    def predict(self, pc):\n        short_pc = ((pc//2)%2, pc%2)\n        \n        # pc indexes into pattern history table\n        ph = self.pattern_history_table[short_pc] # \n        \n        # pattern history indexes into branch history table\n        bh = self.branch_history_table[ph]\n        \n        return bh[1] # 2-bit adaptive predictor\n        \n    \n    def update(self, pc, is_taken):\n        \n        short_pc = (pc//2%2, pc%2)\n        \n        # update branch history\n        ph = self.pattern_history_table[short_pc]\n        \n        bh_old = self.branch_history_table[ph]\n        \n        self.branch_history_table[ph] = update_branch_history(bh_old, is_taken)\n                \n        \n        # update pattern history\n        self.pattern_history_table[short_pc] = ph[1:] + (is_taken,)",
      "execution_count": 7,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "class ThreeBitGlobal():\n    pattern_history_register = (0,0,0)\n    branch_history_table = defaultdict(lambda: (0,0))\n    \n    def predict(self, pc):\n        bht_state = self.branch_history_table[self.pattern_history_register]\n        return bht_state[0] # 2-bit adaptive predictor\n    \n    def update(self, pc, is_taken):\n        bht_state = self.branch_history_table[self.pattern_history_register]\n        \n        # update bht\n        self.branch_history_table[self.pattern_history_register] = update_branch_history(bht_state, is_taken)\n        \n        # update pattern history register\n        self.pattern_history_register = self.pattern_history_register[1:] + (is_taken,)",
      "execution_count": 8,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "class GShare():\n    pattern_history_register = (0,0,0)\n    branch_history_table = defaultdict(lambda: (0,0))\n    \n    def predict(self, pc):\n        pc_short = ( ( pc // 4) % 2, (pc //2)%2, pc%2)\n        \n        ix = xor(pc_short, self.pattern_history_register)\n        \n        bht_state = self.branch_history_table[ix]\n        \n        return bht_state[0] # 2-bit adaptive predictor\n    def update(self, pc, is_taken):\n        pc_short = ( ( pc // 4) % 2, (pc //2)%2, pc%2)\n        \n        ix = xor(pc_short, self.pattern_history_register)\n        \n        bht_state = self.branch_history_table[ix]\n        \n        # update bht\n        self.branch_history_table[ix] = update_branch_history(bht_state, is_taken)\n        \n        # update pattern history register\n        self.pattern_history_register = self.pattern_history_register[1:] + (is_taken,)",
      "execution_count": 9,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p = TwoLevelLocal()",
      "execution_count": 10,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Test runners"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def run_till_steady(p):\n    for i in range(100):\n        for pc, taken in history:\n            p.predict(pc), taken\n            p.update(pc, taken)\n\n    prediction_history1 = []\n    \n    for pc, taken in history:\n        prediction = p.predict(pc), taken\n        prediction_history1.append(prediction)\n        p.update(pc, taken)\n        \n    prediction_history2 = []\n    \n    for pc, taken in history:\n        prediction = p.predict(pc), taken\n        prediction_history2.append(prediction)\n        p.update(pc, taken)\n        \n    assert prediction_history1 == prediction_history2\n    \n    return p",
      "execution_count": 11,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def test(p):\n    p = run_till_steady(p)\n\n    for i in range(100):\n        for pc, taken in history:\n            p.predict(pc), taken\n            p.update(pc, taken)\n    for pc, taken in history:\n        print(p.predict(pc), taken)\n        p.update(pc, taken)\n    print(\"-\"*10)\n    \n    pred = []\n    actu = []\n    \n    for pc, taken in history:\n        pred.append(p.predict(pc))\n        actu.append(taken)\n        p.update(pc, taken)\n        \n    acc = sum(x == y for x,y in zip(pred, actu)) / len(pred)\n    print(acc)\n    return p",
      "execution_count": 12,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Run Tests and Get State"
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Two level local"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p = test(TwoLevelLocal())",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1 1\n0 0\n1 0\n0 0\n0 0\n1 1\n0 0\n1 1\n0 1\n----------\n0.7777777777777778\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.branch_history_table",
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 14,
          "data": {
            "text/plain": "{(0, 0): (0, 1), (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 1)}"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.branch_history_table",
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 15,
          "data": {
            "text/plain": "{(0, 0): (0, 1), (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 1)}"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## Three Bit Global"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p = test(ThreeBitGlobal())",
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1 1\n0 0\n0 0\n0 0\n0 0\n0 1\n0 0\n1 1\n1 1\n----------\n0.8888888888888888\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.branch_history_table",
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 17,
          "data": {
            "text/plain": "defaultdict(<function __main__.ThreeBitGlobal.<lambda>()>,\n            {(0, 0, 0): (0, 1),\n             (0, 0, 1): (0, 0),\n             (0, 1, 0): (1, 1),\n             (1, 0, 0): (0, 0),\n             (1, 0, 1): (1, 1),\n             (0, 1, 1): (1, 1),\n             (1, 1, 1): (0, 0),\n             (1, 1, 0): (0, 0)})"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.pattern_history_register",
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 18,
          "data": {
            "text/plain": "(0, 1, 1)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "## GShare"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p = test(GShare())",
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": "1 1\n0 0\n0 0\n0 0\n0 0\n1 1\n0 0\n1 1\n1 1\n----------\n1.0\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.pattern_history_register",
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 20,
          "data": {
            "text/plain": "(0, 1, 1)"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "p.branch_history_table",
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 21,
          "data": {
            "text/plain": "defaultdict(<function __main__.GShare.<lambda>()>,\n            {(1, 1, 0): (1, 1),\n             (0, 1, 1): (0, 0),\n             (0, 0, 1): (0, 0),\n             (0, 0, 0): (0, 0),\n             (1, 0, 0): (1, 1),\n             (0, 1, 0): (1, 1),\n             (1, 0, 1): (1, 1),\n             (1, 1, 1): (0, 0)})"
          },
          "metadata": {}
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "language_info": {
      "name": "python",
      "version": "3.7.3",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "toc": {
      "nav_menu": {},
      "number_sections": true,
      "sideBar": true,
      "skip_h1_title": false,
      "base_numbering": 1,
      "title_cell": "Table of Contents",
      "title_sidebar": "Contents",
      "toc_cell": false,
      "toc_position": {},
      "toc_section_display": true,
      "toc_window_display": false
    },
    "gist": {
      "id": "bb802ca4c91efa62ee11f6a796ab87bb",
      "data": {
        "description": "venkat_hw2problem1.ipynb",
        "public": true
      }
    },
    "_draft": {
      "nbviewer_url": "https://gist.github.com/bb802ca4c91efa62ee11f6a796ab87bb"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}