MEDUSA
A 200-variable k-SAT solver achieving 3.5× faster solution times and 3× greater energy efficiency than prior work.
Mixed-signal k-SAT solver. Venue: ISSCC 2026 · JSSC 2026.
MEDUSA is a 200-variable k-SAT solver in TSMC 28nm. SAT is NP-complete and appears throughout AI planning, drug discovery, scheduling, and chip design automation. The chip uses oscillator-based analog dynamics to find solutions in microseconds rather than the milliseconds typical of digital solvers.
Architecture
Two mixed-signal compute tiles, each with 200 oscillator-based spin cells and 508 programmable clause cells, connect to a RISC-V digital supervisor. Each tile accepts arbitrary k-SAT instances directly, with no preprocessing or connectivity restrictions.
How It Works
Each Boolean variable maps to a gated relaxation oscillator. Make/Break feedback injects current to nudge oscillators toward satisfying assignments: when a clause is unsatisfied, current pushes the relevant spins toward a fix; when a clause becomes critically satisfied, the satisfying variable locks in place. This asymmetry allows the system to explore the solution space while converging faster than digital search. Digital inter-macro coupling supports tiling for larger problems.
Results
On 1000 runs of 100-variable, 430-clause problems: 14.92 µs mean time to solution, 19.1 nJ mean energy to solution. 2.59 mm² total area (1.29 mm² per tile).