ترغب بنشر مسار تعليمي؟ اضغط هنا

Memcomputing for Accelerated Optimization

228   0   0.0 ( 0 )
 نشر من قبل Fabio Lorenzo Traversa Ph.D.
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

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.
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 dyna mical 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.
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.
To continue scaling beyond 2-D CMOS with 3-D integration, any new 3-D IC technology has to be comparable or better than 2-D CMOS in terms of scalability, enhanced functionality, density, power, performance, cost, and reliability. Transistor-level 3-D integration carries the most potential in this regard. Recently, we proposed a stacked horizontal nanowire based transistor-level 3-D integration approach, called SN3D [1][2] that solves scaling challenges and achieves tremendous benefits with respect to 2-D CMOS while keeping manageable thermal profile. In this paper, we present the cost analysis of SN3D and show comparison with 2-D CMOS (2D), conventional TSV based 3-D (T3D) and Monolithic 3-D integrations (M3D). In our cost model, we capture the implications of manufacturing, circuit density, interconnects, bonding and heat in determining die cost, and evaluate how cost scales as transistor count increases. Since SN3D is a new 3-D IC fabric, based on our proposed manufacturing pathway[1] we assumed complexity of fabrication steps as proportionality constants in our cost estimation model. Our analysis revealed 86%, 72% and 74% reduction in area; 55%, 43% and 43% reduction in interconnects distribution and total interconnect length for SN3D, which largely contributed to 70%, 67% and 68% reduction in cost in comparison to 2D, T3D and M3D respectively.
For decades, advances in electronics were directly driven by the scaling of CMOS transistors according to Moores law. However, both the CMOS scaling and the classical computer architecture are approaching fundamental and practical limits, and new com puting architectures based on emerging devices, such as resistive random-access memory (RRAM) devices, are expected to sustain the exponential growth of computing capability. Here we propose a novel memory-centric, reconfigurable, general purpose computing platform that is capable of handling the explosive amount of data in a fast and energy-efficient manner. The proposed computing architecture is based on a uniform, physical, resistive, memory-centric fabric that can be optimally reconfigured and utilized to perform different computing and data storage tasks in a massively parallel approach. The system can be tailored to achieve maximal energy efficiency based on the data flow by dynamically allocating the basic computing fabric for storage, arithmetic, and analog computing including neuromorphic computing tasks.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا