Fully parallel implementation of digital memcomputing on FPGA

Abstract

We present a fully parallel digital memcomputing solver implemented on a field-programmable gate array (FPGA) board. For this purpose, we have designed an FPGA code that solves the ordinary differential equations associated with digital memcomputing in parallel. A feature of the code is the use of only integer-type variables and integer constants to enhance optimization. Consequently, each integration step in our solver is executed in 96~ns. This method was utilized for difficult instances of the Boolean satisfiability (SAT) problem close to a phase transition, involving up to about 150 variables. Our results demonstrate that the parallel implementation reduces the scaling exponent by about 1 compared to a sequential C++ code on a standard computer. Additionally, compared to C++ code, we observed a time-to-solution advantage of about three orders of magnitude. Given the limitations of FPGA resources, the current implementation of digital memcomputing will be especially useful for solving compact but challenging problems.

References in corpus (7)

• Memcomputing: a computing paradigm to store and process information on the same physical platform
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
• Hardware implementation of digital memcomputing on small-size FPGAs
• SPICE Modeling of Memcomputing Logic Gates

Cited by in corpus (1)

• Acceleration of digital memcomputing by jumps