Permutation Circuit Synthesis via Embedded Languages and Recursion
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.
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.
Embedded Language for Synthesizing Circuits
This article leverages the circuit and circuitry libraries, which constitute an embedded domain-specific language (with Python acting as the host language) for representing, building, and evaluating circuits description.
from parts import parts
from circuit import *
from circuitry import *Testing a Synthesis Approach
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.
from itertools import product
from random import shuffle
from tqdm import tqdm
def test(synthesis):
# Create a permutation of all 8-bit vectors.
vs_original = list(product(*[[0,1]]*8))
vs_permuted = list(product(*[[0,1]]*8))
shuffle(vs_permuted, lambda: 0.5)
# Execute the synthesis function that is being tested.
# A synthesis function must accept as it inputs an
# initial vector to evaluate while constructing the
# circuit (as necessitated by the `circuitry` library),
# the original list of vectors, and a permuted list of
# vectors.
bit.circuit(circuit())
bs = synthesis(
bits([input(i) for i in ([0]*8)]),
vs_original,
vs_permuted
)
# Display some statistics and whether the circuit
# correctly implements the permutation.
c = bit.circuit()
checks = ([
(vo == tuple(c.evaluate(list(vi))))
for (vi, vo) in tqdm(
list(zip(vs_original, vs_permuted)),
position=0, leave=True
)
])
print(all(checks))
print({
o: c.count(lambda g: g.operation == o)
for o in [op.and_, op.or_, op.not_]
})Naive Synthesis Approach
A naive synthesis approach that utilizes logical formulas can act as a starting point. First, split the permutation f: {0, 1}ⁿ → {0, 1}ⁿ into n separate component functions {f ∈ {0, 1}ⁿ → {0, 1}ⁿ | i ∈ {0, …, n}} such that each component function computes one bit of the output bit vector. For each function fᵢ, convert every input vector v ∈ {0, 1}ⁿ that maps to 1 into a corresponding formula ψᵥ that is true for exactly that vector. For example, given v = (0, 1, 1, 0), the formula would be ψᵥ(a, b, c, d) = (¬a) ∧ b ∧ c ∧ (¬d).
Then, it is just a matter of taking the disjunction of all such formulas to obtain the formula φᵢ for the component function fᵢ. Finally, the output f(v) ∈ {0, 1}ⁿ of the overall function f on an input vector v ∈ {0, 1}ⁿ can be computed by evaluating each of the n formulas φᵢ on the same input vector v. This approach can be implemented in a very concise manner, as demonstrated below.
from functools import reduce
def naive(xs, vs_ins, vs_outs):
"""
Synthesize a circuit for the given permutation.
"""
def clause(xs, kcs):
if len(kcs) == 1:
(k, c) = kcs[0]
return xs[k] if c == 1 else ~xs[k]
else:
(kcs0, kcs1) = parts(kcs, 2)
return clause(xs, kcs0) & clause(xs, kcs1)
# The set of all clauses, one for each input vector.
cs = [clause(xs, tuple(enumerate(vi))) for vi in vs_ins]
# Index sets of input vectors that should be included
# for each output bit.
ps = [
reduce(
(lambda p, q: p | q),
[
clause(xs, tuple(enumerate(vs_ins[r])))
for (r, vo) in enumerate(vs_outs) if vo[c] == 1
]
)
for c in range(8)
]
return outputs(ps)The naive approach can be evaluated and tested. The circuit generated using the approach is correct, but has a relatively large number of gates.
>>> test(naive)
100%|█████████████████████████| 256/256 [00:19<00:00, 13.43it/s]
True
{(0, 0, 0, 1): 7168, (0, 1, 1, 1): 1016, (1, 0): 3711}Optimized Synthesis Approach
The naive approach described and implemented above creates a circuit that performs a large amount of redundant work. For any pair of input variables a and b, the circuit may have many instances of a gate such as a ∧ b. The optimized approach below attempts to take advantage of the fact that a circuit is a directed acyclic graph, finding opportunities to reuse gates where possible.
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).
Most Frequent Pairs
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 class found in the built-in collections library. Note that in addition to identifying a pair, the functions performs a few additional operations that will be useful within the synthesis algorithm.
from collections import Counter
def pair(ss, ds):
"""
Add to `ds` the pair of elements that appears most
frequently across all sets in `ss`.
"""
# Collect all pairs of elements found in every set in `ss`.
ps = [
p
for s in ss
for p in [(x, y) for x in s for y in s if x < y]
]
if len(ps) == 0:
return (ss, ds, False)
else:
# Find the most common pair.
(p, i) = (Counter(ps).most_common(1)[0][0], len(ds))
ds.append(p)
# Replace these pairs of elements with an index into
# the corresponding pair in `ds`.
ss = [
((s - set(p)) | {i}) if set(p).issubset(s) else s
for s in ss
]
return (ss, ds, True)Synthesis with Reuse
The synthesis approach below modifies the naive synthesis approach by introducing two kinds of reuse:
- subformulas ψᵥ built for individual conjunction clauses are cached and reused (across all conjunctions) whenever possible and
- clauses ψᵥ and their disjunctions are reused across the formulas constructed for the component functions fᵢ (via the heuristic above that looks for disjunctions of pairs of subformulas that occur most frequently at any given stage in the process).
def optimized(xs, vs_ins, vs_outs):
"""
Synthesize a circuit for the given permutation.
"""
cache = {}
def clause(xs, kcs):
if kcs in cache:
return cache[kcs]
elif len(kcs) == 1:
(k, c) = kcs[0]
cache[(k, c)] = xs[k] if c == 1 else ~xs[k]
return cache[(k, c)]
else:
(kcs0, kcs1) = parts(kcs, 2)
cache[kcs] = clause(xs, kcs0) & clause(xs, kcs1)
return cache[kcs]
# Construct an initial collection of sets
ss = [
set(r for (r, vo) in enumerate(vs_outs) if vo[c] == 1)
for c in range(8)
]
# Keep merging the most frequent pair across all sets
# until there are no pairs left.
(ds, updated) = (list(range(len(vs_ins))), True)
while updated:
(ss, ds, updated) = pair(ss, ds)
# Take the disjunction of every formula that corresponds
# to an input vector that maps to `1`.
cs = [clause(xs, tuple(enumerate(vi))) for vi in vs_ins]
for (k, (i, j)) in enumerate(ds[len(vs_ins):]):
cs.append(cs[i] | cs[j])
return outputs([cs[k] for [k] in ss])A test of the optimized approach demonstrates a significant reduction in the number of gates.
>>> test(optimized)
100%|█████████████████████████| 256/256 [00:01<00:00, 189.33it/s]
True
{(0, 0, 0, 1): 303, (0, 1, 1, 1): 494, (1, 0): 16}This article is also available as a Jupyter Notebook on GitHub.
