@conference {116,
title = {
3D Crosspoint Memory as a Parallel Architecture for Computing Network Reachability
},
booktitle = {IEEE International Conference on Computer Design (ICCD)},
year = {Forthcoming},
publisher = {IEEE},
organization = {IEEE},
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.
},
author = {Velasquez, Alvaro and Jha, Sumit Kumar}
}