FM_Partition.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.11.2"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6pfNNa4fqwMy",
        "outputId": "d3b08960-b72f-4b88-8439-a680d10f65ab"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Requirement already satisfied: mip in /usr/local/lib/python3.10/dist-packages (1.15.0)\n",
            "Requirement already satisfied: cffi==1.15.* in /usr/local/lib/python3.10/dist-packages (from mip) (1.15.1)\n",
            "Requirement already satisfied: pycparser in /usr/local/lib/python3.10/dist-packages (from cffi==1.15.*->mip) (2.21)\n"
          ]
        }
      ],
      "source": [
        "!pip install mip"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## LEF DEF Parsing\n",
        "\n",
        "- Install the LEFDEFParser from the the wheel file : [LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl](https://github.com/srini229/EE5333_tutorials/blob/master/parser/LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl)\n",
        "- Download example LEF and DEF files: [Nangate.lef](https://github.com/srini229/EE5333_tutorials/blob/master/parser/Nangate.lef) and [example.def](https://github.com/srini229/EE5333_tutorials/blob/master/parser/example.def)\n",
        "\n",
        "    <img src=\"https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/part/fig/example_cir.png\" width=340 height=195 />\n",
        "\n"
      ],
      "metadata": {
        "id": "9b8l7WIsKTOC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install --break-system-packages https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl\n",
        "!rm -f *.{lef,def}\n",
        "!wget https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/{Nangate.lef,example.def}\n",
        "!wget https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/sample.{lef,def}"
      ],
      "metadata": {
        "id": "yZMKB51YKRme",
        "outputId": "4b291742-6a1d-4e5d-b209-714996a76bc3",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Collecting LEFDEFParser==0.1\n",
            "  Downloading https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/LEFDEFParser-0.1-cp310-cp310-linux_x86_64.whl (563 kB)\n",
            "\u001b[2K     \u001b[90m━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\u001b[0m \u001b[32m563.3/563.3 kB\u001b[0m \u001b[31m8.6 MB/s\u001b[0m eta \u001b[36m0:00:00\u001b[0m\n",
            "\u001b[?25hInstalling collected packages: LEFDEFParser\n",
            "Successfully installed LEFDEFParser-0.1\n",
            "--2024-02-13 04:33:34--  https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/Nangate.lef\n",
            "Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 185.199.108.133, 185.199.109.133, 185.199.110.133, ...\n",
            "Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|185.199.108.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 1083933 (1.0M) [text/plain]\n",
            "Saving to: ‘Nangate.lef’\n",
            "\n",
            "Nangate.lef         100%[===================>]   1.03M  --.-KB/s    in 0.06s   \n",
            "\n",
            "2024-02-13 04:33:35 (18.3 MB/s) - ‘Nangate.lef’ saved [1083933/1083933]\n",
            "\n",
            "--2024-02-13 04:33:35--  https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/example.def\n",
            "Reusing existing connection to raw.githubusercontent.com:443.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 899 [text/plain]\n",
            "Saving to: ‘example.def’\n",
            "\n",
            "example.def         100%[===================>]     899  --.-KB/s    in 0s      \n",
            "\n",
            "2024-02-13 04:33:35 (50.9 MB/s) - ‘example.def’ saved [899/899]\n",
            "\n",
            "FINISHED --2024-02-13 04:33:35--\n",
            "Total wall clock time: 0.4s\n",
            "Downloaded: 2 files, 1.0M in 0.06s (18.3 MB/s)\n",
            "--2024-02-13 04:33:35--  https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/sample.lef\n",
            "Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 185.199.108.133, 185.199.109.133, 185.199.110.133, ...\n",
            "Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|185.199.108.133|:443... connected.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 40034 (39K) [text/plain]\n",
            "Saving to: ‘sample.lef’\n",
            "\n",
            "sample.lef          100%[===================>]  39.10K  --.-KB/s    in 0.003s  \n",
            "\n",
            "2024-02-13 04:33:35 (11.5 MB/s) - ‘sample.lef’ saved [40034/40034]\n",
            "\n",
            "--2024-02-13 04:33:35--  https://raw.githubusercontent.com/srini229/EE5333_tutorials/master/parser/sample.def\n",
            "Reusing existing connection to raw.githubusercontent.com:443.\n",
            "HTTP request sent, awaiting response... 200 OK\n",
            "Length: 2909 (2.8K) [text/plain]\n",
            "Saving to: ‘sample.def’\n",
            "\n",
            "sample.def          100%[===================>]   2.84K  --.-KB/s    in 0s      \n",
            "\n",
            "2024-02-13 04:33:35 (36.6 MB/s) - ‘sample.def’ saved [2909/2909]\n",
            "\n",
            "FINISHED --2024-02-13 04:33:35--\n",
            "Total wall clock time: 0.3s\n",
            "Downloaded: 2 files, 42K in 0.003s (12.1 MB/s)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#vertex class; name is the instance name of the gate; area: area of the module and the;\n",
        "class Vertex:\n",
        "  def __init__(self, name, area):\n",
        "    self._name = name\n",
        "    self._area = area\n",
        "  def __repr__(self):\n",
        "    return self._name + f\" ({round(self._area,2)})\"\n",
        "\n",
        "# Reads input LEF/DEF files and returns a hypergraph with vertex list V and hyperedge list E;\n",
        "# each hyperedge in E is a tuple of vertices of type `Vertex` defined above.\n",
        "def loadNetlist(leffile = None, deffile = None):\n",
        "  import LEFDEFParser as LDP\n",
        "  l = LDP.LEFReader()\n",
        "  areaLookup = dict()\n",
        "  if leffile:\n",
        "    l.readLEF(leffile)\n",
        "    areaLookup = {m.name():(m.xdim()*m.ydim()*1.e-6) for m in l.macros()}\n",
        "  vertices = dict()\n",
        "  edges = dict()\n",
        "  if deffile:\n",
        "    d = LDP.DEFReader()\n",
        "    d.readDEF(deffile)\n",
        "    vertices = {c.name() : Vertex(c.name(), areaLookup.get(c.macro(), None)) for c in d.components()}\n",
        "    edges = {n.name():[vertices[p[0]] for p in n.pins() if p[0] != 'PIN'] for n in d.nets()}\n",
        "  delE = list()\n",
        "  for e in edges:\n",
        "    if len(edges[e]) <= 1:\n",
        "      delE.append(e)\n",
        "  for e in delE: del edges[e]\n",
        "  return vertices, edges"
      ],
      "metadata": {
        "id": "eiYXZ9ybriIn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## $k$-way hypergraph partitioning using ILP\n",
        "+ Hypergraph $H(V,E)$\n",
        "+ $x_{v,i}$ is the indicator variable for $v$ being in partition $V_i$\n",
        "+ $x_{e,i}$ is the indicator variable for $e\\in E$ being contained in $V_i$\n",
        "\n",
        "+ Objective: $\\max\\limits_{x_{e,i}} \\sum\\limits_{e\\in E}\\sum\\limits_{i=1}^k x_{e,i}$\n",
        "+ Subject to constraints:\n",
        "<ul>\n",
        "$\\begin{align}\n",
        "x_{v,i} &\\in \\{0, 1\\}, &\\forall v \\in V, \\forall i \\in \\{1,2,\\ldots, k\\}\\\\\n",
        "x_{e,i} &\\in \\{0, 1\\}, &\\forall e \\in E, \\forall i \\in \\{1,2,\\ldots, k\\}\\\\\n",
        "\\sum\\limits_{i=1}^k x_{v,i} &=1 , &\\forall v \\in V\\\\\n",
        "\\sum_{v\\in V} area(v)\\cdot x_{v,i}&\\leq Area_{max} &\\forall v \\in V\\\\\n",
        "\\sum_{v\\in V} area(v)\\cdot x_{v,i}&\\geq Area_{min} &\\forall v \\in V\\\\\n",
        "x_{e,i} &\\leq x_{v,i}, &\\forall e \\in E, \\forall v~\\text{connected by}~e\\\\\n",
        "\\end{align}$\n",
        "</ul>"
      ],
      "metadata": {
        "id": "i7U9GT-Wq1mP"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# V - vertices; each vertex is one of the gates in the netlist; Each vertex is of type\n",
        "# E - hyperedges; each edge/hyperedge is a tuple of vertices\n",
        "# k - is the number of partitions\n",
        "# (Amin, Amax) - minimum/maximum area for balance criterion\n",
        "def partition(V, E, Amin, Amax, k = 2):\n",
        "  import mip\n",
        "  model = mip.Model(f\"{k}-way partition\")\n",
        "  x = {u:[model.add_var(f\"x_{u}_{i}\", var_type = mip.BINARY) for i in range(k)] for u in V}\n",
        "  x_e = {e:[model.add_var(f\"x_{e}_{i}\", var_type = mip.BINARY) for i in range(k)] for e in E}\n",
        "  model.verbose = 0\n",
        "  model.objective = mip.maximize(mip.xsum(x_e[e][i] for e in E for i in range(k)))\n",
        "\n",
        "  for u in V:\n",
        "    model += mip.xsum(x[u]) == 1\n",
        "\n",
        "  for i in range(k):\n",
        "    model += mip.xsum(V[u]._area*x[u][i] for u in V) >= Amin\n",
        "    model += mip.xsum(V[u]._area*x[u][i] for u in V) <= Amax\n",
        "\n",
        "  for e in E:\n",
        "    for i in range(k):\n",
        "      for v in E[e]:\n",
        "        model += x_e[e][i] <= x[v._name][i]\n",
        "\n",
        "  model.write(f\"partition{k}.lp\")\n",
        "  model.optimize()\n",
        "  sol = [list() for i in range(k)]\n",
        "\n",
        "  if model.status == mip.OptimizationStatus.OPTIMAL:\n",
        "    for u in V:\n",
        "      for i in range(k):\n",
        "        if round(x[u][i].x) == 1: sol[i].append(V[u])\n",
        "\n",
        "    return (sol, len(E)- model.objective.x)\n",
        "  return None, None\n"
      ],
      "metadata": {
        "id": "owS9xJ2iq5ma"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def reset(A, B, nbrs, V):\n",
        "  part = {}\n",
        "  fs = {}\n",
        "  td = {}\n",
        "  for vertex in V.keys():\n",
        "    part[vertex] = 0\n",
        "    fs[vertex] = 0\n",
        "    td[vertex] = 0\n",
        "  for j in range(2):\n",
        "    partition = A if (0 == j) else B\n",
        "    for i in partition:\n",
        "      part[i._name] = j\n",
        "  for vertex in V.values():\n",
        "    vertex_part = part[vertex._name]\n",
        "    for nbr_list in nbrs[vertex._name]:\n",
        "      if(len(nbr_list) == 1):\n",
        "        if(part[nbr_list[0]._name] == vertex_part):\n",
        "          td[vertex._name] += 1\n",
        "        else:\n",
        "          fs[vertex._name] += 1\n",
        "      else:\n",
        "        for j in nbr_list:\n",
        "          if(part[j._name] != vertex_part):\n",
        "            break\n",
        "        else:\n",
        "          td[vertex._name] += 1\n",
        "        for j in nbr_list:\n",
        "          if(part[j._name] == vertex_part):\n",
        "            break\n",
        "        else:\n",
        "          fs[vertex._name] += 1\n",
        "\n",
        "  return part, fs, td\n",
        "\n",
        "def findMaxGainWithBal(V, Ap, Bp, fs, td, Amin, Amax, e_len):\n",
        "  gmax = -10000000\n",
        "  sum_Ap = 0\n",
        "  sum_Bp = 0\n",
        "  res_vertex = None\n",
        "  for vertex in Ap:\n",
        "    sum_Ap += vertex._area\n",
        "  for vertex in Bp:\n",
        "    sum_Bp += vertex._area\n",
        "  for vertex in Ap:\n",
        "    gain = fs[vertex._name] - td[vertex._name]\n",
        "    if((sum_Bp + vertex._area) <= Amax):\n",
        "      if(gain > gmax):\n",
        "        res_vertex = vertex\n",
        "        gmax = gain\n",
        "  for vertex in Bp:\n",
        "    gain = fs[vertex._name] - td[vertex._name]\n",
        "    if((sum_Ap + vertex._area) <= Amax):\n",
        "      if(gain > gmax):\n",
        "        res_vertex = vertex\n",
        "        gmax = gain\n",
        "  return res_vertex, gmax\n",
        "\n",
        "def updateFsTd(V, fs, td, res_vertex, nbrs, part):\n",
        "  vertex_part = part[res_vertex._name]\n",
        "  for nbr_list in nbrs[res_vertex._name]:\n",
        "    if(len(nbr_list) == 1):\n",
        "      if(part[nbr_list[0]._name] == vertex_part):\n",
        "        fs[nbr_list[0]._name] += 1\n",
        "      else:\n",
        "        td[nbr_list[0]._name] += 1\n",
        "    else:\n",
        "      for j in nbr_list:\n",
        "        if(part[j._name] == vertex_part):\n",
        "          break\n",
        "      else:\n",
        "        for j in nbr_list:\n",
        "          td[j._name] += 1\n",
        "      for j in nbr_list:\n",
        "        temp_nbr_list = nbr_list.copy()\n",
        "        temp_nbr_list.remove(j)\n",
        "        for z in temp_nbr_list:\n",
        "          if(part[z._name] == part[j._name]):\n",
        "            break\n",
        "        else:\n",
        "          fs[j._name] += 1\n",
        "\n",
        "  return fs,td\n",
        "\n",
        "\n",
        "\n",
        "# bi-partition the input hypergraph using Fiduccia-Matheyses algorithm\n",
        "# argument list is the same as the ILP version described above\n",
        "# return value is a list of two lists and the number of cut hyperedges;\n",
        "# each list is a partition comprising contained gates(vertices)\n",
        "def partitionFM(V, E, Amin, Amax):\n",
        "  nbrs = {}\n",
        "  part = {}\n",
        "  fs = {}\n",
        "  td = {}\n",
        "  for vertex in V.keys():\n",
        "    nbrs[vertex] = []\n",
        "    part[vertex] = 0\n",
        "    fs[vertex] = 0\n",
        "    td[vertex] = 0\n",
        "  for e in E.values():\n",
        "    for vertex in e:\n",
        "      temp = e.copy()\n",
        "      temp.remove(vertex)\n",
        "      nbrs[vertex._name].append(temp)\n",
        "  print(nbrs)\n",
        "  A = []\n",
        "  B = []\n",
        "  temp_sum_a = 0\n",
        "  temp_sum_b = 0\n",
        "  for vertex in V.values():\n",
        "    if(temp_sum_a < Amin):\n",
        "      A.append(vertex)\n",
        "      temp_sum_a += vertex._area\n",
        "  for vertex in V.values():\n",
        "    if(vertex not in A and temp_sum_b < Amin):\n",
        "      B.append(vertex)\n",
        "      temp_sum_b += vertex._area\n",
        "  for vertex in V.values():\n",
        "    if(vertex not in A and vertex not in B and temp_sum_a + vertex._area <= Amax):\n",
        "      A.append(vertex)\n",
        "      temp_sum_a += vertex._area\n",
        "  for vertex in V.values():\n",
        "    if(vertex not in A and vertex not in B and temp_sum_b + vertex._area <= Amax):\n",
        "      B.append(vertex)\n",
        "      temp_sum_b += vertex._area\n",
        "  maxGain = 1\n",
        "  while maxGain > 0:\n",
        "    Ap, Bp = A.copy(), B.copy()\n",
        "    G, S = [], []\n",
        "    part, fs, td = reset(A, B, nbrs, V)\n",
        "    while(len(S) <= len(V.items())):\n",
        "      res_vertex, g = findMaxGainWithBal(V, Ap, Bp, fs, td, Amin, Amax, len(E.items()))\n",
        "      if not(res_vertex):\n",
        "        break\n",
        "      fs, td = updateFsTd(V, fs, td, res_vertex, nbrs, part)\n",
        "      if(res_vertex in Ap):\n",
        "        Ap.remove(res_vertex)\n",
        "      else:\n",
        "        Bp.remove(res_vertex)\n",
        "      G.append(g)\n",
        "      S.append(res_vertex)\n",
        "    for i in range(1, len(G)):\n",
        "      G[i] += G[i-1]\n",
        "    maxGain = max(G)\n",
        "    maxIndex = G.index(maxGain)\n",
        "    if maxGain > 0:\n",
        "      for vertex in S[0:maxIndex+1]:\n",
        "        if(vertex in A):\n",
        "          A.remove(vertex)\n",
        "          B.append(vertex)\n",
        "          part[vertex._name] = 1\n",
        "        else:\n",
        "          B.remove(vertex)\n",
        "          A.append(vertex)\n",
        "          part[vertex._name] = 0\n",
        "    else:\n",
        "      break\n",
        "  cuts = 0\n",
        "  for edge in E.values():\n",
        "    comp_part = part[edge[0]._name]\n",
        "    for item in edge[1:]:\n",
        "      if part[item._name] != comp_part:\n",
        "        cuts += 1\n",
        "        break\n",
        "  return [A,B], cuts"
      ],
      "metadata": {
        "id": "4-OyoMlMrG7s"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import time\n",
        "for (lf,df) in [('sample.lef', 'sample.def'), ('Nangate.lef', 'example.def')]:\n",
        "  V,E = loadNetlist(lf, df)\n",
        "  Atotal = sum(V[u]._area for u in V)\n",
        "  maxCellArea = max(V[u]._area for u in V)\n",
        "  print(\"Total area :\", Atotal, \"delArea :\", round(maxCellArea,2))\n",
        "  for partfn in [partition, partitionFM]:\n",
        "    t = time.time()\n",
        "    sol, numcuts = partfn(V, E, Atotal/2 - maxCellArea, Atotal/2 + maxCellArea)\n",
        "    print(f\"{partfn.__name__} runtime : {time.time() - t}\")\n",
        "    if sol:\n",
        "      print(\"number of cuts :\", round(numcuts))\n",
        "      for part in sol:\n",
        "        print(\"area :\", round(sum([x._area for x in part]),2), part)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lb5iCFC0q8SQ",
        "outputId": "d775c3a8-52bb-4743-fbbe-656783d4ea20"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Total area : 250.344 delArea : 25.99\n",
            "partition runtime : 1.878967523574829\n",
            "number of cuts : 0\n",
            "area : 142.27 [inst2591 (15.05), inst2908 (9.58), inst3428 (8.21), inst3444 (8.21), inst4062 (12.31), inst4678 (5.47), inst4189 (15.05), inst4382 (8.21), inst5638 (12.31), inst5275 (9.58), inst5821 (6.84), inst6050 (8.21), inst5195 (12.31), inst7234 (10.94)]\n",
            "area : 108.07 [inst2015 (10.94), inst3502 (13.68), inst4132 (8.21), inst4183 (25.99), inst4597 (8.21), inst5333 (12.31), inst6286 (10.94), inst6458 (17.78)]\n",
            "partitionFM runtime : 7.152557373046875e-06\n",
            "Total area : 18.088 delArea : 3.19\n",
            "partition runtime : 0.0233917236328125\n",
            "number of cuts : 2\n",
            "area : 9.58 [a (3.19), c (3.19), e (3.19)]\n",
            "area : 8.51 [b (3.19), d (3.19), f (2.13)]\n",
            "partitionFM runtime : 5.4836273193359375e-06\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "2eCXDSEptnbB"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}