Memristors

Forthcoming
A. Velasquez and S. K. Jha, “ 3D Crosspoint Memory as a Parallel Architecture for Computing Network Reachability ,” in IEEE International Conference on Computer Design (ICCD), Forthcoming.Abstract

We introduce a new in-memory computing design that can compute single-source reachability and transitive closure of graphs by using the natural parallel flow of information in three-dimensional crosspoint memories. The proposed design can be implemented using 3D crosspoint architectures with two layers of 1-diode 1-resistor (1D1R) interconnects. Our logic-in-memory design mitigates the infamous memory-processor bottleneck characteristic of John von Neumann architectures and has a runtime complexity of $\mathcal{O}(n)$ using $\mathcal{O}(n^2)$ devices for a graph with $n$ nodes. This compares favorably to efficient algorithms on John von Neumann architectures with a time complexity of $\mathcal{O}(n^3/p + n^2 \log p)$ on $p$ processors and a competing in-memory approach with runtime $\mathcal{O}(n^2)$ using $\mathcal{O}(n^3)$ components.

2018
A. Velasquez and S. K. Jha, “ Parallel Transitive Closure Within 3D Crosspoint Memory ,” in ACM Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria, 2018.
A. U. Hassen and S. K. Jha, “ Free Binary Decision Diagram Based Synthesis of Compact Crossbars for in-Memory Computing of Boolean Functions ,” in International Symposium on Circuits and Systems (ISCAS), Florence, Italy, 2018.Abstract

We introduce a new computer-aided design  approach based on Free Binary Decision Diagrams (FBDDs) for  implementing Boolean functions on crossbars using flow-based computing. Our crossbar synthesis procedure uses generalized FBDDs to design crossbars for a Boolean formula such that there is a flow of current from an input nanowire to an output nanowire through the sneak paths in the crossbar if and only if the Boolean formula evaluates to true.  Generalized FBDDs are more succinct representations of Boolean formula that traditional Reduced Ordered Binary Decision Diagrams (ROBDDs) because they do not require the same variable ordering along all paths of the decision diagram.   Our experimental results with the middle bit of a multiplier show that our designs are 69.9% more succinct than flow-based crossbar computing approaches designed using ROBDDs. 

iscas2018.pdf
A. Velasquez and S. K. Jha, “ Fault-Tolerant In-Memory Computing Using Paths-Based Logic and Heterogeneous Components ,” in Design, Automation, and Test in Europe (DATE), Dresden, Germany, 2018.Abstract

 

The memory-processor bottleneck and scaling difficulties of the CMOS transistor have given rise to a plethora of research initiatives to overcome these challenges. Popular among these is in-memory crossbar computing. In this paper, we propose a framework for synthesizing fault-tolerant computation- in-memory circuits based on bounded model checking. The resulting designs can be used to compute Boolean formulas using a constant number of read and write cycles. We demonstrate the effectiveness of the approach by generating addition and comparator circuits in the presence of common crossbar faults. 

 

2017
D. Chakraborty, S. Raj, J. C. Gutierrez, T. Thomas, and S. K. Jha, “ In-Memory Execution of Compute Kernels using Flow-based Memristive Crossbar Computing ,” in IEEE International Conference on Rebooting Computing 2017, Washington D.C., 2017.Abstract

 

Rebooting computing using in-memory architectures relies on the ability of emerging devices to execute a legacy software stack. In this paper, we present our approach of executing compute kernels written in a subset of the C pro- gramming language using flow-based computing on nanoscale memristor crossbars. Our framework also tests the correctness of the design using the parallel Xyces electronic simulation software. We demonstrate the potential of our design methodology by designing and testing a compute kernel for edge detection in images. 

 

icrc2017.pdf
D. Chakraborty, S. Raj, and S. K. Jha, “ A Compact 8-bit Adder Design using In-Memory Memristive Computing: Towards Solving the Feynman Grand Prize Challenge ,” in 13th ACM/IEEE International Symposium on Nanoscale Architectures, Newport, USA, 2017, pp. in press.Abstract

We introduce a new compact in-memory computing design for implementing 8-bit addition using eight vertically-stacked nanoscale crossbars of  one-diode one-memristor 1D1M switches. Each crossbar in our design only has 5 rows and 4 columns. Hence, the design may be used to fabricate a compact 8-bit adder that meets the size constraint of  50nm x 50nm x 50nm imposed by the electrical component of the Feynman Grand Prize. The potential availability of sub-5nm nanoscale memristors and single-molecule diode devices coupled with the ability to fabricate high-density nanoscale memristor crossbars suggests that our design may eventually be fabricated to meet the size constraints of the  Feynman Grand Prize.

feynmangrandprize_nanoarch2017.pdf
A. Velasquez and S. K. Jha, “ Computation of Boolean Matrix Chain Products in 3D ReRAM ,” in IEEE International Symposium on Circuits and Systems (ISCAS), Baltimore, MD, 2017, pp. 2643-2646.Abstract

 

Energy concerns, the infamous memory wall, and the enormous data deluge of the current big-data age have made the integration of processing and memory elements into a very appealing paradigm. In this paper, we focus on a computation-in- memory solution to the problem of multiplying a set of Boolean matrices, also known as Boolean matrix chain multiplication (BMCM). This is a fundamental computational task with applica- tions in graph theory, group testing, data compression, and digital signal processing. In particular, we propose a framework for mapping arbitrary instances of BMCM to a 3-dimensional (3D) crossbar memory architecture consisting of 1-diode 1-resistor (1D1R) structures. 

 

3d_reram_iscas_2017.pdf
S. Raj, D. Chakraborty, and S. K. Jha, “ In-Memory Flow-Based Stochastic Computing on Memristor Crossbars using Bit-Vector Stochastic Streams ,” in IEEE International Conference on Nanotechnology (IEEE NANO), Pittsburgh, PA, 2017, pp. in press. ieeenano2017_JHA.pdf
D. Chakraborty and S. K. Jha, “ Design of Compact Memristive In-Memory Computing Systems using Model Counting ,” in IEEE International Symposium on Circuits and Systems (ISCAS)., Baltimore, MD, 2017, pp. 2655-2658.Abstract

 

Crossbars of nanoscale memristors are being fab- ricated to serve as high-density non-volatile memory devices. The flow of current through memristor crossbars has been recently used to perform in-memory computations. However, existing approaches based on decision procedures only scale to the simplest circuits such as one-bit adders and other approaches employing decision diagrams produce large crossbar designs. 

In this paper, we present a new method for synthesizing 3 compact combinational circuits using nanoscale crossbars. Our synthesis procedure exploits a symbolic representation of Boolean functions and employs model counting to guide a simulated annealing based search procedure. 

 

 

MLnFM_iscas2017.pdf
D. Chakraborty and S. K. Jha, “ Automated synthesis of compact crossbars for sneak-path based in-memory computing ,” in 2017 Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017, pp. 770–775.Abstract

 

The rise of data-intensive computational loads has 1) exposed the processor-memory bottleneck in Von Neumann architectures and has reinforced the need for in-memory com- puting using devices such as memristors. Existing literature on computing Boolean formula using sneak-paths in nanoscale memristor crossbars has only focussed on short Boolean formula. There are two open questions: (i) Can one synthesize sneak-path based crossbars for computing large Boolean formula? (ii) What is the size of a memristor crossbar that can compute a given Boolean formula using sneak paths? In this paper, we make progress on both these problems. First, we show that the number of rows and columns required to compute a Boolean formula is at most linear in the size of the Reduced Ordered Binary Decision Diagram representing the Boolean function. Second, we demonstrate how Boolean Decision Diagrams can be used to synthesize nanoscale crossbars that can compute a given Boolean formula using naturally occurring sneak paths. In particular, we synthesize large logical circuits such as 128-bit adders for the first-time using sneak-path based crossbar computing. 

 

crossbarsusingformalmethods.pdf
2016
S. K. Jha, D. E. Rodriguez, J. E. Van Nostrand, and A. Velasquez, “ Computation of boolean formulas using sneak paths in crossbar computing ”, US Patent: 9319047, 2016. patent2016_memristorcomputing_jha.pdf

US Patent 9,319,047

Z. Alamgir, K. Beckmann, N. Cady, A. Velasquez, and S. K. Jha, “ Flow-based computing on nanoscale crossbars: Design and implementation of full adders ,” in Circuits and Systems (ISCAS), 2016 IEEE International Symposium on, 2016, pp. 1870–1873. iscas2016_flowmemristor_jha_01.pdf
A. Velasquez and S. K. Jha, “ Parallel boolean matrix multiplication in linear time using rectifying memristors ,” in Circuits and Systems (ISCAS), 2016 IEEE International Symposium on, 2016, pp. 1874–1877. iscas2016_parallel_memristor_jha.pdf
2015
A. Velasquez and S. K. Jha, “ Automated synthesis of crossbars for nanoscale computing using formal methods ,” in Nanoscale Architectures (NANOARCH), 2015 IEEE/ACM International Symposium on, 2015, pp. 130–136.Abstract

 

Since the fabrication of nanoscale memristors by HP Labs in 2008, there has been a renewed interest in the use of crossbars of nanoscale memristors as digital storage and neuromorphic computing devices. However, the same success has not been replicated in the use of crossbars for performing general-purpose computations that can support the existing software infrastructure originally designed for Von Neumann architectures. One of the key challenges facing this technology is the existence of sneak paths. While it has been shown that sneak paths can be used to perform Boolean computations in crossbars, the human mind is not particularly suited to reason about the exponential complexity of sneak paths in crossbars. Hence, the size of the crossbar designs proposed in the literature has been large for practical applications. In this paper, we demonstrate how formal methods can be used to automatically synthesize compact crossbar designs that can be used to evaluate Boolean formula by using the sneak paths phenomena as a design primitive. We show that our automated synthesis technique can be used to generate a state-of-the-art nano-crossbar design for a 1-bit full adder. 

 

nanoarch-2.pdf
A. Velasquez and S. K. Jha, “ Fault-tolerant in-memory crossbar computing using quantified constraint solving ,” in Computer Design (ICCD), 2015 33rd IEEE International Conference on, 2015, pp. 101–108.Abstract

 

There has been a surge of interest in the effective storage and computation of data using nanoscale crossbars. In this paper, we present a new method for automating the design of fault-tolerant crossbars that can effectively compute Boolean formula. Our approach leverages recent advances in Satisfiability Modulo Theories (SMT) solving for quantified bit-vector formula (QBVF). We demonstrate that our method is well-suited for fault- tolerant computation and can perform Boolean computations despite stuck-open and stuck-closed interconnect defects as well as wire faults. We employ our framework to generate various arithmetic and logical circuits that compute correctly despite the presence of stuck-at faults as well as broken wires. 

 

iccd2015.pdf
2014
A. Velasquez and S. K. Jha, “ Parallel computing using memristive crossbar networks: Nullifying the processor-memory bottleneck ,” in Design & Test Symposium (IDT), 2014 9th International, 2014, pp. 147–152.Abstract

 

We are quickly reaching an impasse to the number of transistors that can be squeezed onto a single chip. This has led to a scramble for new nanotechnologies and the subsequent emergence of new computing architectures capable of exploiting these nano-devices. The memristor is a promising More-than- Moore device because of its unique ability to store and manipulate data on the same device. In this paper, we propose a flexible architecture of memristive crossbar networks for computing Boolean formulas. Our design nullifies the gap between processor and memory in von Neumann architectures by using the crossbar both for the storage of data and for performing Boolean com- putations. We demonstrate the effectiveness of our approach on practically important computations, including parallel Boolean matrix multiplication. 

 

We are quickly reaching an impasse to the number of transistors that can be squeezed onto a single chip. This has led to a scramble for new nanotechnologies and the subsequent emergence of new computing architectures capable of exploiting these nano-devices. The memristor is a promising More-than- Moore device because of its unique ability to store and manipulate data on the same device. In this paper, we propose a flexible architecture of memristive crossbar networks for computing Boolean formulas. Our design nullifies the gap between processor and memory in von Neumann architectures by using the crossbar both for the storage of data and for performing Boolean com- putations. We demonstrate the effectiveness of our approach on practically important computations, including parallel Boolean matrix multiplication. 

 

idt2014.pdf