# Nanoscale Computing

2019
B. Shaia, A. Velasquez, and S. K. Jha, “ Spatially Efficient in-Memory Addition Through Destructive and Non-Destructive Operations ,” in IEEE International Symposium on Circuits and Systems, Sapporo, Japan, 2019.
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. Velasquez and S. K. Jha, “ 3D Crosspoint Memory as a Parallel Architecture for Computing Network Reachability ,” in IEEE International Conference on Computer Design (ICCD), 2018.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.

A. U. Hassen and S. K. Jha, “ Free BDD based Computer-aided Design of Compact Memristor Crossbars for in-Memory Computing ,” in 14th IEEE / ACM International Symposium on Nanoscale Architectures (NANOARCH), Athens, Greece, 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.

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.

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.

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.

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.

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.

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.
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.
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.