# Partitioning a boolean circuit for automatic parallelization

tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm trying to optimize the implementation.

Going into detail, the input is a combinatorial Boolean circuit (so no loops, state, etc.). I'm implementing it in software with a rather unusual set of primitives, such that:

• logic gates must be computed one at a time, as the "engine" is single-threaded
• NOT gates are free
• AND, OR, XOR have a cost of 1 (eg. 1 second)
• N identical gates can be evaluated at the same time for a cost of 10 plus some tiny proportional term (eg. a batch of 20 distinct AND gates can be evaluated in 10 seconds, 50 distinct XOR gates in ~10 seconds, etc.)

The objective is to implement the circuit with the given primitives while minimizing the cost.

### What I tried

This problem looks vaguely related to the bin packing problem, but the differences - constraints on the order of the items and different cost for each "bin" depending on the number of items - make me think it's not particularly applicable.

I was suggested to use integer linear programming, which sounds like the best fit so far, but I'm not sure how to represent the problem. Specifically, I'd use binary variables to represent whether the implementation gate/batch M is used in place of the circuit gate N, but then I don't know how to express the objectives to be maximized/minimized.

One approach for formulating this as an ILP problem could be to have zero-or-one variables $$x_{i,t},y_{i,t},z_t$$, with the intended meaning that $$x_{i,t}=1$$ if the $$i$$th gate is evaluated in the $$t$$th instruction (not as part of a batch), or $$x_{i,t}=0$$ otherwise; and $$y_{i,t}=1$$ if the $$i$$th gate is evaluated in a batch in the $$t$$th instruction, or $$y_{i,t}=0$$ otherwise; and $$z_t=1$$ if the $$t$$th instruction is a batch instruction, or $$z_t=0$$ otherwise.

Your problem can then be represented as an integer linear program, with some constraints to enforce consistency of these boolean variables:

• Each gate is assigned to a single instruction: $$\sum_t x_{i,t} + y_{i,t}=1$$.

• Non-batch instructions are assigned a single gate: $$\sum_i x_{i,t} = 1-z_t$$.

• Non-batch instructions don't set any $$y$$ values: $$\sum_i y_{i,t} \le C z_t$$, where $$C$$ is a large constant equal to the maximum batch size (or the number of gates, if there is no limit).

• Gates can only be batched together if they compute the same logic function: $$y_{i,t} + y_{j,t} \le 1$$ for each pair of gates $$i,j$$ that have a different logic function.

• A gate can only be evaluated once all of its inputs are ready: $$x_{i,t} + y_{i,t} \ge x_{j,u} + y_{j,u}$$ for each pair of gates $$i,j$$ such that the output of $$i$$ is an input to $$j$$, and for each pair $$t,u$$ with $$t.

(I'll assume you treat NOT gates as free and don't try to assign them to any instruction; they just happen automatically.)

Now any consistent assignment to the $$x$$'s and $$y$$'s will correspond to a valid way to implement the circuit. The cost of this assignment will be $$9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$$, where $$c$$ is the tiny proportional term and $$k$$ is the total number of instructions in the schedule (both $$c$$ and $$k$$ are constants). If you pick a value for $$k$$, the maximum number of instructions allowed, you can use an ILP solver to minimize $$9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$$ subject to the inequalities above, and this will give you the best way to schedule your boolean circuit using $$k$$ instructions. Then, I suggest you search over different values of $$k$$, solving an ILP for each one, to find the best boolean circuit.

Be prepared: ILP is NP-hard, so finding the optimal solution might take a very long time if the circuit is large and you're aren't very lucky. Some ILP solvers have the ability to terminate their search after a fixed time limit and return the best solution they've found so far, which might be useful if that happens.