3-D crossbar architecture for fast energy-efficient in-memory computing of graph transitive closure

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