3-D crossbar architecture for fast energy-efficient in-memory computing of graph transitive closure
An in-memory computing architecture is disclosed that can evaluate the transitive closure of graphs using the natural parallel flow of information in 3-D nanoscale crossbars. The architecture can be implemented using 3-D crossbar architectures with as few as two layers of 1-diode 1-resistor (1D1R) interconnects. The architecture avoids memory-processor bottlenecks and can hence scale to large graphs. The approach leads to a runtime complexity of O(n 2 ) using O(n 2 ) memristor devices. This compares favorably to conventional algorithms with a time complexity of O((n 3 )/p+(n 2 ) log p) on p processors. The approach takes advantage of the dynamics of 3-D crossbars not available on 2-D crossbars.
1. A computer-implemented method for simulating operation of a physical system having a plurality of physical subsystems, for computing a transitive closure of a directed graph, G, comprising:
implementing a Boolean circuit model of a 3D crossbar memory for in-memory parallel computation of a matrix X based on the directed graph G,
wherein the Boolean circuit model of the 3D crossbar memory consists of at least two layers of memory cells, each memory cell being in a binary state of 1, describing a low-resistance state, or a binary state of 0, describing a high-resistance state,
wherein the Boolean circuit model includes a topmost set of row wires where voltages are applied to read the binary state of the memory cells,
wherein a memory cell with a binary state of 1 permits a high current to be redirected between two connected wires and a memory cell with a binary state of 0 inhibits current from one connected wire to another connected wire,
wherein a first layer of memory cells connect the topmost row wires to column wires,
wherein a second layer of memory cells connect the column wires with a set of bottommost row wires,
wherein the bottommost row wires are connected to the topmost row wires via feedback loops and,
wherein the Boolean circuit model having at least one external feedback loop;
for each row in the matrix, performing repeated Boolean matrix multiplication of the matrix X so as to generate a converged wire vector associated with the given row in the matrix;
combining the converged wire vectors to generate a transitive closure matrix X*; and
outputting the transitive closure matrix X*.
2. The computer-implemented method for simulating operation of a physical system having a plurality of physical subsystems of claim 1 , wherein a first layer of the 3D crossbar memory stores the matrix X and a second layer of the 3D crossbar memory stores a transpose of the matrix X.
3. The computer-implemented method for simulating operation of a physical system having a plurality of physical subsystems of claim 1 , wherein the graph G=(V,E),
where V is the set of vertices in the graph G and
E∈{0,1} |V|×|V| the adjacency matrix of the graph G.
4. The computer-implemented method for simulating operation of a physical system having a plurality of physical subsystems of claim 3 , wherein the transitive closure matrix X* is the matrix X*, where
X
ij
*
=
{
1
if
i
=
j
or
there
is
a
path
from
v
i
to
v
j
in
G
0
otherwise
.
5. The computer-implemented method for simulating operation of a physical system having a plurality of physical sub systems of claim 1 , wherein the graph G is an unweighted graph.