Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDigital Memcomputing: from Logic to Dynamics to Topology
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Digital memcomputing machines (DMMs) are a class of computational machines designed to solve combinatorial optimization problems. A practical realization of DMMs can be accomplished via electrical circuits of highly non-linear, point-dissipative dynamical systems engineered so that periodic orbits and chaos can be avoided. A given logic problem is first mapped into this type of dynamical system whose point attractors represent the solutions of the original problem. A DMM then finds the solution via a succession of elementary instantons whose role is to eliminate solitonic configurations of logical inconsistency (logical defects) from the circuit. By employing a supersymmetric theory of dynamics, a DMM can be described by a cohomological field theory that allows for computation of certain topological matrix elements on instantons that have the mathematical meaning of intersection numbers on instantons. We discuss the dynamical meaning of these matrix elements, and argue that the number of elementary instantons needed to reach the solution cannot exceed the number of state variables of DMMs, which in turn can only grow at most polynomially with the size of the problem. These results shed further light on the relation between logic, dynamics and topology in digital memcomputing.
rate research
Read More
The original Pascaline was a mechanical calculator able to sum and subtract integers. It encodes information in the angles of mechanical wheels and through a set of gears, and aided by gravity, could perform the calculations. Here, we show that such a concept can be realized in electronics using memory elements such as memristive systems. By using memristive emulators we have demonstrated experimentally the memcomputing version of the mechanical Pascaline, capable of processing and storing the numerical results in the multiple levels of each memristive element. Our result is the first experimental demonstration of multidigit arithmetics with multi-level memory devices that further emphasizes the versatility and potential of memristive systems for future massively-parallel high-density computing architectures.
Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving hard planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.
In this work, we introduce the concept of an entirely new circuit architecture based on the novel, physics-inspired computing paradigm: Memcomputing. In particular, we focus on digital memcomputing machines (DMMs) that can be designed leveraging properties of non-linear dynamical systems; ultimate descriptors of electronic circuits. The working principle of these systems relies on the ability of currents and voltages of the circuit to self-organize in order to satisfy mathematical relations. In particular for this work, we discuss self-organizing gates, namely Self-Organizing Algebraic Gates (SOAGs), aimed to solve linear inequalities and therefore used to solve optimization problems in Integer Linear Programming (ILP) format. Unlike conventional IO gates, SOAGs are terminal-agnostic, meaning each terminal handles a superposition of input and output signals. When appropriately assembled to represent a given ILP problem, the corresponding self-organizing circuit converges to the equilibria that express the solutions to the problem at hand. Because DMMs components are non-quantum, the ordinary differential equations describing it can be efficiently simulated on our modern computers in software, as well as be built in hardware with off-of-the-shelf technology. As an example, we show the performance of this novel approach implemented as Software as a Service (MemCPU XPC) to address an ILP problem. Compared to todays best solution found using a world renowned commercial solver, MemCPU XPC brings the time to solution down from 23 hours to less than 2 minutes.
Monolithic three-dimensional integration of memory and logic circuits could dramatically improve performance and energy efficiency of computing systems. Some conventional and emerging memories are suitable for vertical integration, including highly scalable metal-oxide resistive switching devices (memristors), yet integration of logic circuits proves to be much more challenging. Here we demonstrate memory and logic functionality in a monolithic three-dimensional circuit by adapting recently proposed memristor-based stateful material implication logic. Though such logic has been already implemented with a variety of memory devices, prohibitively large device variability in the most prospective memristor-based circuits has limited experimental demonstrations to simple gates and just a few cycles of operations. By developing a low-temperature, low-variability fabrication process, and modifying the original circuit to increase its robustness to device imperfections, we experimentally show, for the first time, reliable multi-cycle multi-gate material implication logic operation within a three-dimensional stack of monolithically integrated memristors. The direct data manipulation in three dimensions enables extremely compact and high-throughput logic-in-memory computing and, remarkably, presents a viable solution for the Feynman grand challenge of implementing an 8-bit adder at the nanoscale.
The recent demonstration of current-driven magnetic domain wall logic [Z. Luo et al., Nature 579:214] was based on a three-input logic gate that was identified as a reconfigurable NAND/NOR function. We reinterpret this logic gate as a minority gate within the context of threshold logic, enabling a domain wall threshold logic paradigm in which the device count can be reduced by 80%. Furthermore, by extending the logic gate to more than three inputs of non-equal weight, an 87% reduction in device count can be achieved.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
