Learning the Address Code for On-Chip Biochip Decoders

A digital microfluidic biochip moves droplets by switching hundreds of electrodes on and off, and wiring each electrode to its own external pin does not scale. One established fix places a small combinational logic circuit on the chip. The controller sends a short binary address at each time step, and the on-chip logic decodes it into the full electrode pattern, so pin count falls to the logarithm of the number of distinct patterns. That decoder still has to be built, and its size depends heavily on two choices that existing tools make blindly: which time steps share an address, and which binary address each group receives. Every electrode also has many time steps where its state does not matter, and those "don't-care" entries are free material for the logic minimizer.

This note proposes treating the decoder as a small learnable logic network, while relaxing the assignment of time steps to addresses into continuous probabilities. A single annealed optimization then chooses the grouping, the encoding, and the logic together, under a hard requirement that every specified electrode state is reproduced exactly. The claim is that, at the same pin count, this produces decoders that are much smaller after real synthesis and layout than the standard pipeline. That pipeline minimizes the number of groups first and then hands a fixed encoding to a logic minimizer.

Core Claim and What Is New

A logic integrated optimal pin-count design for digital microfluidic biochips supplies the setting and the main point of comparison. It groups time steps by solving a minimum clique partition on a compatibility graph, which reaches $\lceil\log_2 K\rceil$ pins for $K$ groups. It then writes per-electrode Boolean functions for the decoder. That work optimizes $K$ and treats the logic as a consequence. Two facts make this wasteful.

The first is that pin count only changes when $K$ crosses a power of two. Any design with $K \le 2^p$ costs the same $p$ pins. The slack between $K$ and $2^p$, together with the freedom to merge or split compatible steps, can therefore be spent on making the logic simpler. The second is that the address each group gets is an encoding problem. A good encoding lets an electrode's function depend on one or two address bits, while a bad one forces a full product of all bits.

The new element is to optimize grouping and encoding against decoder cost rather than group count. Grouping does not need its own formulation, because it falls out of encoding. If two incompatible time steps receive the same address, no decoder can satisfy both, so the correctness constraint rules that out without any separate compatibility graph.

Concretely, let $T$ be the number of scheduled time steps and $p$ the pin budget. A soft assignment matrix $A \in [0,1]^{T \times 2^p}$ has rows on the probability simplex and gives each step a distribution over addresses. A differentiable logic gate network $f_\theta$ with $p$ inputs and one output per electrode plays the role of the decoder. Let $M_{te}\in\{0,1,X\}$ be the required state of electrode $e$ at step $t$, and let $\Omega$ be the set of non-don't-care entries. We minimize

$$ \mathcal{L}(A,\theta)=\sum_{(t,e)\in\Omega}\ell\Big(\sum_{c} A_{tc}\, f_\theta(c)_e,\; M_{te}\Big)+\lambda\, C(\theta)+\mu\, W(\theta), $$

where $\ell$ is a binary cross-entropy, $C$ is a differentiable logic-cost term, and $W$ is a wirelength proxy. Don't-care entries are simply absent from $\Omega$. For $C$, gates whose relaxed function sits near a constant are pushed toward exact constants, following the unit-tying idea, so that synthesis can propagate them away. For $W$, decoder outputs are charged by the spread of the physical electrode coordinates that share logic. The rows of $A$ are sharpened by an annealed temperature toward one-hot assignments, as in the continuation schedule of HashNet: Deep Learning to Hash by Continuation. At the end, the discrete design is checked exactly and the full required-state matrix is handed to standard synthesis, with don't-cares passed through as don't-care sets.

How This Relates to Prior Work

Three groups of work supply the method. Two-Stage Unit Tying for Simplifying Differentiable Logic Gate Networks shows that forcing chosen gates in a learned logic network to constants triggers cascading constant propagation in Vivado. On CIFAR-10 at a 50% tied ratio it cuts post-synthesis lookup-table use by up to 48.3%. We reuse its observation and its warning: Taylor-style saliency mispredicts which gates are safe to tie, so tying here is driven by the exactness constraint rather than by gradient magnitude. Unlike that work, our network has no accuracy target. It must be exactly correct on $\Omega$, and its inputs are themselves being optimized.

LUTNet: Learning FPGA Configurations for Highly Efficient Neural Network Inference shows that truth tables can be trained by backpropagation. High-Throughput DNN Inference with LogicNets shows that synthesis tools can shrink truth-table logic up to 39× below naive estimates. That is a reason to evaluate only after real synthesis and never on our proxy. LogicNets' limit of at most 15 input bits per truth table is harmless here, because a decoder with $p\le 10$ pins has small fan-in by construction.

BIPNN: Learning to Solve Binary Integer Programming via Hypergraph Neural Networks motivates the use of continuous relaxation with annealing. Within a one-hour limit on degree-4 polynomial problems with more than 2,500 variables, it beats SCIP. It also flags the weakness we must handle: penalty-based relaxations do not guarantee hard constraints. We therefore add an exact verification-and-repair step instead of trusting the penalty.

Two works motivate the physical side of the objective. Physically Aware Synthesis Revisited: Guiding Technology Mapping with Primitive Logic Gate Placement shows that gate-count-optimal netlists are not layout-optimal: early placement guidance cut post-routing delay by an average of 14% on ASAP7. DAG-aware Synthesis Orchestration shows that structural simplification can increase post-mapping area. Both justify measuring after placement and routing and including $W$. Our physical model is deliberately crude, because decoder outputs must reach electrodes at fixed array positions. We claim no advance in physical synthesis itself.

Two works define the regime and bound the claim. Control synthesis for the flow-based microfluidic large-scale integration biochips documents how common don't-care valve states are in scheduled assays, and resolves them through graph coloring for pin sharing rather than for logic cost. Columba S: a scalable co-layout design automation tool for microfluidic large-scale integration uses pneumatic multiplexers needing $2\lceil\log_2 n\rceil+1$ inlets, but these can actuate at most two independent valves at once. An electronic decoder is the generalization of that multiplexer that allows arbitrary simultaneous patterns, and this is exactly the case where decoder size becomes the cost that matters. Our scope is therefore electronically addressed chips: digital microfluidics, and continuous-flow chips with electronic valve drivers. We do not claim results for purely pneumatic logic.

Research Program

The first deliverable is a benchmark set of actuation matrices with explicit don't-cares and electrode coordinates. We will regenerate these from the assays used by Dinh et al.: PCR, multiplexed in-vitro diagnostics, DNA sample preparation, the multifunctional chip, n-plex immunoassay, and random01 through random07. We will add the PCR, in-vitro diagnostics, and 10/30/50-node synthetic schedules of Tseng et al. Because the original matrices may not be public, we will release our regenerated versions and report the pin counts we obtain under Dinh's own method as a sanity check against its stated average reduction of 80%.

The second deliverable is the optimizer. It has five parts: the relaxed address assignment, a differentiable gate network decoder with depth and width chosen per pin budget, the annealing schedule, and a discretization step. The fifth part is a repair stage. Any violated entry in $\Omega$ is fixed by a small exact solver restricted to the conflicting steps, which re-addresses them into unused codes or, in the worst case, adds a pin. That fallback is reported whenever it fires.

The third deliverable is the evaluation flow. Decoder logic goes through Yosys and ABC with don't-care sets enabled, then OpenROAD on the ASAP7 kit following the PigMAP setup. We report cell area, gate count, total wirelength, and post-route power, all at equal pin count.

The analysis question is where the gain comes from. Candidate sources are encoding alone, the use of slack codes, constant tying, or the wirelength term. We also want to know whether gains grow with the fraction of don't-cares, which we can vary on synthetic schedules.

Baselines

The naive reference is Dinh-style grouping, meaning minimum clique partition where it finishes and its bounded heuristic otherwise, followed by a random or sequential binary encoding and ABC with don't-cares enabled. It shows what current practice delivers. Pin counts are reported for it, but no decoder area or wirelength figure is reported on Lacuna for any of these benchmarks, so our first table will establish that reference point.

The strongest existing competitor is the same Dinh grouping paired with the best encoding we can find by search. That search is simulated annealing over address permutations, with ABC called in the loop to score each candidate, and it is run with the same wall-clock budget as our method on the same machine. This is the strongest competitor because it uses the real minimizer as its objective rather than a proxy. Beating it means at least 15% lower post-synthesis area at identical pin count, averaged across benchmarks with no benchmark worse by more than 5%. We pick this threshold because it exceeds the run-to-run variation we expect from search seeds, and we will measure that variation directly.

On the smaller cases, an exact formulation gives the optimality gap. It is a satisfiability encoding that jointly chooses addresses and a two-level cover, minimizing literal count. It shows how far the relaxation sits from true optima where those optima can be computed.

Four ablations isolate the key ingredient, which is joint optimization of grouping and encoding against logic cost. The first fixes the grouping from the clique partition and learns only the encoding. The second forbids slack codes by requiring $K$ to stay minimal. The third removes the tying pressure in $C$. The fourth sets $\mu=0$. A fifth applies the two-stage tying of Lee et al. after the fact to a decoder trained without it. All variants receive the same tuning budget of a fixed number of annealing-schedule trials per benchmark family.

Why not just…?

Why not just give the don't-cares to ABC or Espresso and let the minimizer use them? We do this in every baseline, and it is a real competitor. Two-level and multilevel minimizers exploit don't-cares well, but only for a fixed input encoding. They cannot move a time step to a different address or exploit unused codes, and that is where we expect most of the gain. The first ablation, which fixes grouping and learns only the encoding, together with the strong search baseline, will show directly whether encoding and grouping freedom adds anything beyond what a don't-care-aware minimizer already captures. If ABC with a searched encoding matches us, the differentiable component is unnecessary and we will say so.

Why not just solve the joint problem exactly with an integer program or satisfiability solver? Dinh et al. report that the clique partition alone becomes "prohibitively long" on their largest random cases. Columba 2.0's mixed-integer layout timed out on the 257-unit ChIP128 chip, per Columba S: a scalable co-layout design automation tool for microfluidic large-scale integration. Our joint problem contains that partition as a subproblem and adds encoding. We will still run the exact formulation wherever it finishes, both to measure our optimality gap and to locate the size at which it stops being usable.

Why not just run a classical state-assignment heuristic or simulated annealing with synthesis in the loop? This is the threat most likely to match us on small chips, which is why the in-loop search is our primary baseline under equal wall-clock time. Each in-loop evaluation is a full synthesis run, which caps how many encodings it can try, while gradient steps on the relaxation are cheap. The test is a plot of quality against time as the number of time steps grows. If search stays competitive at the largest scale, the claim narrows to faster convergence, not better optima.

Proposed Experiments and Decisive Checks

The main experiment compares post-route decoder area, wirelength, and power at equal pin count across the Dinh and Tseng benchmarks against the baselines above. All 20 random and practical instances are run with five seeds each, and paired per-benchmark differences are reported.

The first decisive check is the slack-code ablation. If allowing $K<2^p$ to grow toward $2^p$ gives no area reduction, the central intuition is wrong.

The second decisive check is proxy fidelity. We will compute the rank correlation between our relaxed cost $C$ and the area ABC reports across a few hundred sampled discrete designs. PigMAP and LogicNets both warn that abstract cost and synthesized cost diverge, so a correlation below about 0.6 would mean the relaxation is optimizing the wrong thing.

The third check is a constraint-safety audit. We will measure how often repair fires and how many pins it adds. The method is only useful if repair rarely changes pin count, and we will report the rate rather than hide it.

A scaling study on synthetic schedules will vary the don't-care fraction between 20% and 80% and the number of time steps up to the sizes where the clique partition fails. It tests the prediction that gains rise with don't-care density, because more unconstrained entries give the encoding more room to make functions depend on few bits.