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.