article-permutation-circuit-synthesis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Permutation Circuit Synthesis via Embedded Languages and Recursion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The ability to synthesize logical circuits as data structures (without any intention of implementing such circuits as hardware) is becoming increasingly relevant as technologies such as garbled circuit protocols and quantum computing platforms begin to mature. Consequently, there is a growing population working in research, prototyping, and even in software application development settings that may find it convenient to have the ability to synthesize circuits dynamically in popular languages such as Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This article describes how an embedded language approach coupled with recursion can be used to create a framework that can synthesize a relatively efficient logical circuit for any chosen permutation of the set of all bit vectors of some fixed length. The described approach can actually be applied to the synthesis of a circuit for any function over bit vectors of a fixed length. This article focuses on the case of permutations because it is more challenging to know in advance whether and how circuits that represent a permutation of a space of bit vectors can be optimized, thus motivating a general approach that can produce circuits that may be used directly or as an input to a more specialized circuit optimization process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Embedded Language for Synthesizing Circuits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "This article leverages the circuit and circuitry libraries, which constitute an embedded domain-specific language (with Python acting as the host language) for representing, builing, and evaluating circuits description."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from parts import parts\n",
    "from circuit import *\n",
    "from circuitry import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Testing a Synthesis Approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Before exploring and comparing synthesis techniques, it is useful to establish a standard approach for testing that the synthesis technique produces a circuit that is functionally correct. The function below performs such a test given a synthesis technique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "from random import shuffle\n",
    "from tqdm import tqdm\n",
    "\n",
    "def test(synthesis):\n",
    "    # Create a permutation of all 8-bit vectors.\n",
    "    vs_original = list(product(*[[0,1]]*8))\n",
    "    vs_permuted = list(product(*[[0,1]]*8))\n",
    "    shuffle(vs_permuted, lambda: 0.5)\n",
    "\n",
    "    # Execute the synthesis function that is being tested.\n",
    "    # A synthesis function must accept as it inputs an\n",
    "    # initial vector to evaluate while constructing the\n",
    "    # circuit (as necessatied by the `circuitry` library),\n",
    "    # the original list of vectors, and a permuted list of\n",
    "    # vectors.\n",
    "    bit.circuit(circuit())\n",
    "    bs = synthesis(\n",
    "        bits([input(i) for i in ([0]*8)]),\n",
    "        vs_original,\n",
    "        vs_permuted\n",
    "    )\n",
    "\n",
    "    # Display some statistics and whether the circuit\n",
    "    # correctly implements the permutation.\n",
    "    c = bit.circuit()\n",
    "    checks = ([\n",
    "        (vo == tuple(c.evaluate(list(vi))))\n",
    "        for (vi, vo) in tqdm(\n",
    "            list(zip(vs_original, vs_permuted)),\n",
    "            position=0, leave=True\n",
    "        )\n",
    "    ])\n",
    "    print(all(checks))\n",
    "    print({o: c.count(lambda g: g.operation == o) for o in [op.and_, op.or_, op.not_]})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Naive Synthesis Approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A naive synthesis approach that utilizes logical formualas can act as a starting point. First, split the permutation $f:\\{0,1\\}^n \\to \\{0,1\\}^n$ into $n$ separate component functions $\\{f_i \\in \\{0,1\\}^n \\to \\{0,1\\} \\ | \\ i \\in \\{0,\\ldots,n\\}\\}$ such that each component function computes one bit of the output bit vector. For each function $f_i$, convert every input vector $v \\in \\{0,1\\}^n$ that maps to $1$ into a corresponding formula $\\varphi_v$  that is true for exactly that vector. For example, given $(0, 1, 1, 0)$, the formula would be:\n",
    "\n",
    "$$\\varphi_{(1,0,0,1)} = (\\neg x_0) \\wedge x_1 \\wedge x_2 \\wedge (\\neg x_3).$$\n",
    "\n",
    "Then, it is just a matter of taking the disjunction of all such formulas to obtain the formula $\\varphi_{f_i}$ for the component function $f_i$. Finally, the output $f(v) \\in \\{0,1\\}^n$ of the overall function $f$ on an input vector $v \\in \\{0,1\\}^n$ can be computed by evaluating each of the $n$ formulas on the same input vector:\n",
    "\n",
    "$$f(v) = (\\varphi_{f_0}(v), \\ldots, \\varphi_{f_n}(v)).$$\n",
    "\n",
    "This approach can be implemented in a very concise manner, as demonstrated below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "\n",
    "def naive(xs, vs_ins, vs_outs):\n",
    "    \"\"\"\n",
    "    Synthesize a circuit for the given permutation.\n",
    "    \"\"\"\n",
    "    def clause(xs, kcs):\n",
    "        if len(kcs) == 1:\n",
    "            (k, c) = kcs[0]\n",
    "            return xs[k] if c == 1 else ~xs[k]\n",
    "        else:\n",
    "            (kcs0, kcs1) = parts(kcs, 2)\n",
    "            return clause(xs, kcs0) & clause(xs, kcs1)\n",
    "\n",
    "    # The set of all clauses, one for each input vector.\n",
    "    cs = [clause(xs, tuple(enumerate(vi))) for vi in vs_ins]\n",
    "\n",
    "    # Index sets of input vectors that should be included\n",
    "    # for each output bit.\n",
    "    ps = [\n",
    "        reduce(\n",
    "            (lambda p, q: p | q),\n",
    "            [\n",
    "                clause(xs, tuple(enumerate(vs_ins[r])))\n",
    "                for (r, vo) in enumerate(vs_outs) if vo[c] == 1\n",
    "            ]\n",
    "        )\n",
    "        for c in range(8)\n",
    "    ]\n",
    "\n",
    "    return outputs(ps)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The naive approach can be evaluated and tested. The circuit generated using the approach is correct, but has a relatively large number of gates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|█████████████████████████| 256/256 [00:19<00:00, 13.43it/s]\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "{(0, 0, 0, 1): 7168, (0, 1, 1, 1): 1016, (1, 0): 3711}\n"
     ]
    }
   ],
   "source": [
    "test(naive)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Optimized Synthesis Approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The naive approach described and implemented above creates a circuit that performs a large amount of redundant work. For any pair of input variables $x_i$ and $x_j$, the circuit may have many instances of a gate such as $x_i \\wedge x_j$. The optimized approach below attempts to take advantage of the fact that a circuit is a directed acycic graph, finding opportunities to reuse gates where possible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Note that the overall goal is *not* to implement an algorithm that can take a permutation as an input and find the optimal circuit with the minimal number of gates. Instead, the goal is to demonstrate that it is possible to leverage the embedded language for circuits to implement in a *concise* way a general-purpose *greedy* circuit synthesis algorithm that is a significant improvement over the naive approach (in terms of the size of the circuits it synthesizes for a given permutation)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Most Frequent Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The optimized synthesis approach relies on the ability to identify a *pair* of elements (*e.g.*, logical variables) that appears *most frequently* across a collection of sets. A function for identifying such a pair given a collection of sets `ss` is presented below. This function takes advantage of the [`Counter`](https://docs.python.org/3/library/collections.html#collections.Counter) class found in the built-in [collections](https://docs.python.org/3/library/collections.html) library. Note that in addition to identifying a pair, the functions performs a few additional operations that will be useful within the synthesis algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def pair(ss, ds):\n",
    "    \"\"\"\n",
    "    Add to `ds` the pair of elements that appears most\n",
    "    frequently across all sets in `ss`.\n",
    "    \"\"\"\n",
    "    # Collect all pairs of elements found in every set in `ss`.\n",
    "    ps = [p for s in ss for p in [(x, y) for x in s for y in s if x < y]]\n",
    "\n",
    "    if len(ps) == 0:\n",
    "        return (ss, ds, False)\n",
    "    else:\n",
    "        # Find the most common pair.\n",
    "        (p, i) = (Counter(ps).most_common(1)[0][0], len(ds))\n",
    "        ds.append(p)\n",
    "        \n",
    "        # Replace these pairs of elements with an index into\n",
    "        # the corresponding pair in `ds`.\n",
    "        ss = [((s - set(p)) | {i}) if set(p).issubset(s) else s for s in ss]\n",
    "\n",
    "        return (ss, ds, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Synthesis with Reuse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "The synthesis approach below modifies the naive synthesis approach by introducing two kinds of reuse:\n",
    "* subformulas built for individual conjunction clauses $\\varphi_v$ are cached and reused (across *all* conjunctions) whenever possible and\n",
    "* clauses $\\varphi_v$ and their disjunctions are reused across the formulas constructed for the component functions $f_i$ (via the heuristic above that looks for disjunctions of pairs of subformulas that occur most frequently at any given stage in the process)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "def optimized(xs, vs_ins, vs_outs):\n",
    "    \"\"\"\n",
    "    Synthesize a circuit for the given permutation.\n",
    "    \"\"\"\n",
    "    cache = {}\n",
    "    def clause(xs, kcs):\n",
    "        if kcs in cache:\n",
    "            return cache[kcs]\n",
    "        elif len(kcs) == 1:\n",
    "            (k, c) = kcs[0]\n",
    "            cache[(k, c)] = xs[k] if c == 1 else ~xs[k]\n",
    "            return cache[(k, c)]\n",
    "        else:\n",
    "            (kcs0, kcs1) = parts(kcs, 2)\n",
    "            cache[kcs] = clause(xs, kcs0) & clause(xs, kcs1)\n",
    "            return cache[kcs]\n",
    "\n",
    "    # Construct an initial collection of sets \n",
    "    ss = [\n",
    "        set(r for (r, vo) in enumerate(vs_outs) if vo[c] == 1)\n",
    "        for c in range(8)\n",
    "    ]\n",
    "\n",
    "    # Keep merging the most frequent pair across all sets\n",
    "    # until there are no pairs left.\n",
    "    (ds, updated) = (list(range(len(vs_ins))), True)\n",
    "    while updated:\n",
    "        (ss, ds, updated) = pair(ss, ds)\n",
    "\n",
    "    # Take the disjunction of every formula that corresponds\n",
    "    # to an input vector that maps to `1`.\n",
    "    cs = [clause(xs, tuple(enumerate(vi))) for vi in vs_ins]\n",
    "    for (k, (i, j)) in enumerate(ds[len(vs_ins):]):\n",
    "        cs.append(cs[i] | cs[j])\n",
    "\n",
    "    return outputs([cs[k] for [k] in ss])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A test of the optimized approach demonstrates a significant reduction in the number of gates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|█████████████████████████| 256/256 [00:01<00:00, 189.33it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "{(0, 0, 0, 1): 303, (0, 1, 1, 1): 494, (1, 0): 16}\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "test(optimized)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}