Hierarchical computations on sparse matrix rows via a memristor array

#A resistive memory array may be utilized to perform analog computations that exploit the fundamental relationship between row voltage and column current in a resistive mesh to realize an analog multiply-accumulate unit. The memory array is typically organized as a grid of cells interconnected by horizontal and vertical wires, referred to as word lines and bit lines. With emerging resistive memories, this may be further developed to build a powerful multiply-accumulate unit within the memory. For instance, the fundamental relationship between a row access voltage and the resulting bit line current may act as an analog multiplier of row voltage and cell conductance. Instead of accessing a single row as performed for loading and storing data, multiple rows may be activated concurrently.

#FIG. 1 is a functional block diagram illustrating one example of a circuit for hierarchical computations on sparse matrix rows via a memristor array.

#FIG. 2 is a functional block diagram illustrating another example of a circuit for hierarchical computations on sparse matrix rows via a memristor array.

#FIG. 3 illustrates an example of a circuit that utilizes cluster processing to perform hierarchical computations on sparse matrix rows via a memristor array.

#A Dot-Product Engine (DPE) is a powerful hardware primitive to accelerate matrix-vector multiplication. Memristor arrays are employed as computing engines where cell conductance and voltage values perform an analog multiplication between vectors representing the respective values. The vectors from the input matrices are generally greater than the size of the memristor arrays and may therefore be broken into smaller units (e.g., clusters operating on sub matrices) to accommodate the array size and then combined via a parallel pipelined architecture to facilitate computational speed. For such an architecture, the input matrix is first split into a number of submatrices (“submats”) such that the number of rows and columns in a submat is a function of the number of DPE rows and columns. Each submat is then split into bitslices. Finally, the submats are mapped to DPEs. A group of DPEs may share a set of peripheral circuits such as local vector buffer, partial result buffer, ADCs, and h-tree interconnect to form a cluster.

#While it may be generally faster and more efficient than existing techniques, efficiency of the DPE relies on the density of the input matrix. Accordingly, utilizing a DPE directly to operate on sparse matrices may result in a significant increase in latency and energy consumption. In some examples, the sparsity of a matrix, measured as a ratio of the number of non-zero elements in matrix to the total matrix size, may be 0.1-0.5%. Additional, and all alternative sparsity thresholds may be utilized based on specific use cases. Since a DPE maps every input element of the matrix to one or more memristor cells, a poor matrix density will generally lead to inefficient use of DPE resources, which may in turn result in low performance, high energy consumption, and large area overhead.

#In some examples, elimination of all zero submats may lead to an overall utilization of less than 5% of the DPE. However, even though these applications may utilize matrices with thousands of rows and columns, each row generally has very few non-zero elements, making it feasible to handle an entire row in a few clusters—in most cases with just one cluster. Accordingly, instead of splitting a matrix into submats of specific number of rows and columns, it may be more efficient to map each row of a sparse matrix to one or more clusters, and operate each cluster with different sets of input vectors to perform matrix-vector multiplication. Since a cluster is designed to operate on a submat, this may require enhancements to the cluster pipeline and a list of peripheral circuits. Rows that require non-trivial number of clusters may be handled using via submat based computations. As described herein, a combination of row-wise and submat based computations may be utilized for matrices with large sparsity.