Patent ID: 12254195

DETAILED DESCRIPTION

Overview

Computing devices implement algorithms that include matrix operations, such as matrix multiplication, for a wide range of applications, such as graph algorithms, conjugate gradient solvers, sparse linear algebra, and so forth. Algorithms designed for performing operations using dense matrix structures, however, are slow and inefficient when applied to sparse matrices, as computational resources and processing time are wasted on handling zeroes in sparse matrices. This waste of computational resources and processing time is compounded when dense matrix operations are applied to large sparse matrices.

In some implementations, conventional dense-matrix algorithms cause timeouts when extended to very large sparse matrices and fail to function as intended. In terms of computational memory requirements, sparse data is more easily compressed and thus requires significantly less storage relative to dense data of a similar size. For instance, in the case of a sparse matrix, substantial memory requirement reductions are realized by storing only non-zero entries in memory. Depending on the number and distribution of non-zero entries in a sparse matrix, different data structures are implementable to achieve significant memory savings when compared to storing the sparse matrix with its zeroes.

While storing only the non-zero entries of sparse matrices is beneficial from a reduced memory requirement standpoint, the trade-off is that accessing individual matrix elements from memory becomes more complex and requires certain structures in memory to unambiguously access these elements. Conventional formats that have been developed to represent sparse matrices using such structures include Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC). Computing applications frequently leverage sparse matrices to compute sparse matrix-vector products, often requiring computation of a sparse matrix-vector product (SpMV) multiple times over the course of executing an algorithm.

In many instances, such as when implementing iterative solvers, a majority of time spent by a host processing device when executing an algorithm is spent performing matrix-vector product evaluations. When performing SpMV using sparse matrices, conventional systems require a host processing device to repeatedly retrieve matrix and vector elements from memory before using those matrix and vector elements to compute a product. This creates a significant amount of traffic on a communication pathway connecting the host processor with the memory, and the host processor is unable to perform such operations until the vector and matrix elements are retrieved from memory. When performing SpMV using a compressed representation of a sparse matrix (e.g., CSR or CSC), this communication burden is compounded due to the irregular storage of sparse matrix elements in memory.

To address these conventional problems, performing sparse matrix operations using processing-in-memory is described. In implementations, a system includes a memory module having a memory and a processing-in-memory component. The memory module is communicatively coupled to a core of a host, such as a core of a host processor. Using the techniques described herein, the processing-in-memory component is configured to access a vector stored in virtual memory of the memory module. The processing-in-memory component is further configured to access a representation of a sparse matrix stored in physical memory of the memory module. Using the representation of the sparse matrix, the processing-in-memory component is configured to identify an index value that describes, for a non-zero element of the sparse matrix, a location of the sparse matrix in which the non-zero element is disposed.

For instance, in an example implementation where the sparse matrix is represented using CSR, the index value specifies a column of the sparse matrix in which the non-zero element is disposed. As another example, in an implementation where the sparse matrix is represented using CSC, the index value specifies a row of the sparse matrix in which the non-zero element is disposed. The processing-in-memory component is further configured to identify an element in the vector stored in virtual memory based on the index value for the non-zero element of the sparse matrix.

In some implementations, the processing-in-memory component identifies the vector element by computing an offset virtual address that increments a base virtual address for the vector using an offset integer value defined by the index value. The processing-in-memory component is further configured to compute a result vector element using the vector element and the non-zero element of the sparse matrix (e.g., multiply the vector element by the non-zero element and output the resulting product as the result vector element). In some implementations, the processing-in-memory component is configured to repeat these operations for multiple non-zero elements of the sparse matrix.

For instance, in an example scenario the processing-in-memory component identifies, for each non-zero element in a row of the sparse matrix represented in memory using CSR, a column index value and an element of the vector stored in virtual memory for the non-zero element. Continuing this example scenario, the processing-in-memory component computes a result vector element for each non-zero element in the row of the sparse matrix (e.g., by multiplying each non-zero element by a corresponding element in the vector identified by the column index value for the non-zero element).

In some implementations, the processing-in-memory component is configured to perform sparse matrix operations using data stored in different memory locations based on sparse matrix processing logic. In some implementations, the sparse matrix processing logic is received in a command or an instruction from a host processor communicatively coupled to a memory module implementing the processing-in-memory component. Alternatively, or additionally, the processing-in-memory component is configured to perform sparse matrix operations based on sparse matrix processing logic stored in the memory module. Alternatively or additionally, the processing-in-memory component is configured to perform sparse matrix operations based on sparse matrix processing logic stored in the processing-in-memory component (e.g., sparse matrix processing logic maintained in one or more registers of the processing-in-memory component).

Although described with respect to functionality implemented by a single processing-in-memory component, in some implementations the techniques described herein are implemented by multiple processing-in-memory components in parallel (e.g., simultaneously, or near-simultaneously with one another). As an example, when memory is configured as dynamic random-access memory (DRAM), a processing-in-memory component is included at each hierarchical DRAM component (e.g., channel, bank, array, and so forth). For instance, consider an example implementation where a command or instruction from a host processor includes a request to compute a result vector element for each of a plurality of non-zero elements in a sparse matrix. In this example implementation, the command or instruction is provided to a plurality of processing-in-memory components, which are each tasked with handing one or more of the plurality of non-zero elements. For instance, in this example implementation each processing-in-memory component is tasked with processing a different row of the sparse matrix.

In another example implementation, an individual processing-in-memory component is tasked with processing an individual non-zero element in the sparse matrix. In implementations where spars matrix operations are performed by a plurality of processing-in-memory components in parallel with one another, the vector stored in virtual memory is duplicated such that each processing-in-memory component is provided with a copy of the vector. As a specific example, the vector is duplicated such that one copy resides in each of a plurality of memory channels that are each associated with a processing-in-memory component, where each vector copy is assigned a base virtual address on a per-channel basis. Thus, rather than requiring multiple commands, one for each memory component to perform sparse matrix operations, the described techniques enable a single command to cause each processing-in-memory component to perform discrete sparse matrix operations.

By performing sparse matrix operations using a processing-in-memory component, the described techniques do not cause additional traffic on the interface between a host processor and a memory module implementing the processing-in-memory component. This is not possible using conventional systems, which utilize the core of the remote host processor to perform operations involving data stored in memory. The described techniques further advantageously save cycles of the remote host processor, which reduces system power consumption and frees the host processor to perform additional operations relative to conventional systems.

In some aspects, the techniques described herein relate to a system including: a memory of a memory module and a processing-in-memory component of the memory module configured to receive a request for at least one element of a vector stored at a first location in the memory, identify, from a representation of a sparse matrix stored at a second location in the memory, at least one index value for at least one non-zero element in a row of the sparse matrix, and output a result that includes the at least one element of the vector by retrieving the at least one element of the vector from the first location in the memory using the at least one index value.

In some aspects, the techniques described herein relate to a system, wherein the first location in the memory corresponds to a virtual memory location identified by a base virtual address.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to retrieve the at least one element of the vector from the first location in the memory by computing, for an index value of the identified at least one index value, an offset virtual address by incrementing the base virtual address using the index value and accessing data stored at the offset virtual address.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is further configured to access the representation of the sparse matrix from the second location in the memory and store the representation of the sparse matrix in a register of the processing-in-memory component in response to receiving the request.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to output the result by overwriting the representation of the sparse matrix in the register of the processing-in-memory component with the at least one element of the vector.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is further configured to compute a result vector element using the at least one element of the vector and the at least one non-zero element in the row of the sparse matrix.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to receive the request for the at least one element of the vector from a host that includes a core.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to output the result to the host.

In some aspects, the techniques described herein relate to a system, the memory module further including a plurality of processing-in-memory components, wherein the memory module is configured to load sparse matrix processing logic into each of the plurality of processing-in-memory components and task each of the plurality of processing-in-memory components with identifying, for a different row of the sparse matrix, one or more index values for one or more non-zero elements in the different row of the sparse matrix.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to output the result by writing the result to a memory location that is communicatively coupled to a host that includes a core.

In some aspects, the techniques described herein relate to a system, wherein the core is a central processing unit or a graphics processing unit.

In some aspects, the techniques described herein relate to a system, wherein the processing-in-memory component is configured to identify the at least one index value and output the result by executing sparse matrix processing logic that is received from a host that includes a core.

In some aspects, the techniques described herein relate to a system, wherein the request is received from a host that includes a core and the processing-in-memory component is configured to identify the at least one index value and output the result without traffic on a connection between the host and the memory.

In some aspects, the techniques described herein relate to a system, wherein the at least one element of the vector is a floating-point number stored at the first location in the memory and wherein the processing-in-memory component is further configured to identify a single precision bit in the floating-point number by removing a plurality of bits from the floating-point number, wherein the result is computed using the single precision bit and the at least one non-zero element in the row of the sparse matrix.

In some aspects, the techniques described herein relate to a method including accessing, by a processing-in-memory component, a dense vector stored in virtual memory, accessing, by the processing-in-memory component, a representation of a sparse matrix stored in physical memory and identifying an index value for a non-zero value in the sparse matrix using the representation of the sparse matrix, identifying, by the processing-in-memory component, an element in the dense vector using the index value, and computing a result vector element using the element in the dense vector and the non-zero value in the sparse matrix.

In some aspects, the techniques described herein relate to a method, wherein identifying the element in the dense vector using the index value includes computing an offset virtual address by incrementing a base virtual address for the dense vector using an offset identified by the index value.

In some aspects, the techniques described herein relate to a method, further including storing, by the processing-in-memory component, the representation of the sparse matrix in at least one register of the processing-in-memory component in response to accessing the representation of the sparse matrix and outputting, by the processing-in-memory component, the result vector element by overwriting the representation of the sparse matrix in the at least one register of the processing-in-memory component.

In some aspects, the techniques described herein relate to a method, further including outputting, by the processing-in-memory component, the result vector element to a host that includes a core, wherein the host is communicatively coupled to a memory module implementing the processing-in-memory component.

In some aspects, the techniques described herein relate to a method, wherein accessing the dense vector, accessing the representation of the sparse matrix, identifying the element in the dense vector, and computing the result vector element are performed by the processing-in-memory component independent of traffic on a connection between a memory module implementing the processing-in-memory component and a host that includes a core.

In some aspects, the techniques described herein relate to a method including receiving, by a processing-in-memory component of a memory module, a request for at least one element of a vector stored at a first location in a memory of the memory module, identifying, by the processing-in-memory component and from a representation of a sparse matrix stored at a second location in the memory, at least one column index value for at least one non-zero element in a row of the sparse matrix, and outputting, by the processing-in-memory component, a result that includes the at least one element of the vector by retrieving the at least one element of the vector from the first location in the memory using the at least one column index value.

FIG.1is a block diagram of a system100that includes a host with a core and further includes a memory module with a memory and a processing-in-memory component. In particular, the system100includes host102and memory module104, where the host102and the memory module104are communicatively coupled via connection/interface106. In one or more implementations, the host102includes core108, and the memory module104includes memory110and processing-in-memory component112.

In accordance with the described techniques, the host102and the memory module104are coupled to one another via a wired or wireless connection, which is depicted in the illustrated example ofFIG.1as the connection/interface106. Example wired connections include, but are not limited to, buses (e.g., a data bus), interconnects, traces, and planes. Examples of devices in which the system100is implemented include, but are not limited to, supercomputers and/or computer clusters of high-performance computing (HPC) environments, servers, personal computers, laptops, desktops, game consoles, set top boxes, tablets, smartphones, mobile devices, virtual and/or augmented reality devices, wearables, medical devices, systems on chips, and other computing devices or systems.

The host102is an electronic circuit that performs various operations on and/or using data in the memory110. Examples of the host102and/or the core108include, but are not limited to, a central processing unit (CPU), a graphics processing unit (GPU), a field programmable gate array (FPGA), an accelerated processing unit (APU), and a digital signal processor (DSP). For example, the core108is a processing unit that reads and executes instructions (e.g., of a program), examples of which include to add, to move data, and to branch. Although one core108is depicted in the illustrated example, in variations, the host102includes more than one core108(e.g., the host102is a multi-core processor).

In one or more implementations, the memory module104is a circuit board (e.g., a printed circuit board), on which the memory110is mounted and includes the processing-in-memory component112. In some variations, one or more integrated circuits of the memory110are mounted on the circuit board of the memory module104, and the memory module104includes one or more processing-in-memory components112. Examples of the memory module104include, but are not limited to, a TransFlash memory module, a single in-line memory module (SIMM), and a dual in-line memory module (DIMM). In one or more implementations, the memory module104is a single integrated circuit device that incorporates the memory110and the processing-in-memory component112on a single chip. In some examples, the memory module104is composed of multiple chips that implement the memory110and the processing-in-memory component112that are vertically (“3D”) stacked together, are placed side-by-side on an interposer or substrate, or are assembled via a combination of vertical stacking or side-by-side placement.

The memory110is a device or system that is used to store information, such as for immediate use in a device (e.g., by the core108of the host102and/or by the processing-in-memory component112). In one or more implementations, the memory110corresponds to semiconductor memory where data is stored within memory cells on one or more integrated circuits. In at least one example, the memory110corresponds to or includes volatile memory, examples of which include random-access memory (RAM), dynamic random-access memory (DRAM), synchronous dynamic random-access memory (SDRAM), and static random-access memory (SRAM).

In some implementations, the memory110corresponds to or includes a cache memory of the core108and/or the host102such as a level 1 cache, a level 2 cache, a level 3 cache, and so forth. For example, the memory110represents high bandwidth memory (HBM) in a 3D-stacked implementation. Alternatively or additionally, the memory110corresponds to or includes non-volatile memory, examples of which include solid state disks (SSD), flash memory, read-only memory (ROM), programmable read-only memory (PROM), erasable programmable read-only memory (EPROM), and electronically erasable programmable read-only memory (EEPROM). The memory110is thus configurable in a variety of ways that support memory verification (e.g., of the memory110) using processing-in-memory without departing from the spirit or scope of the described techniques.

Broadly, the processing-in-memory component112is configured to process processing-in-memory instructions, e.g., received from the core108via the connection/interface106. The processing-in-memory component112is representative of a processor with example processing capabilities ranging from relatively simple (e.g., an adding machine) to relatively complex (e.g., a CPU/GPU compute core). In an example, the processing-in-memory component112processes the instructions using data stored in the memory110.

Processing-in-memory contrasts with standard computer architectures which obtain data from memory, communicate the data to a remote processing unit (e.g., the core108of the host102), and process the data using the remote processing unit (e.g., using the core108of the host102rather than the processing-in-memory component112). In various scenarios, the data produced by the remote processing unit as a result of processing the obtained data is written back to memory, which involves communicating the produced data over the connection/interface106from the remote processing unit to memory. In terms of data communication pathways, the remote processing unit (e.g., the core108of the host102) is further away from the memory110than the processing-in-memory component112, both physically and topologically. As a result, conventional computer architectures suffer from increased data transfer latency, reduced data communication bandwidth, and increased data communication energy, particularly when the volume of data transferred between the memory and the remote processing unit is large, which can also decrease overall computer performance.

Thus, the processing-in-memory component112enables increased computer performance while reducing data transfer energy as compared to standard computer architectures that implement remote processing hardware. Further, the processing-in-memory component112alleviates memory performance and energy bottlenecks by moving one or more memory-intensive computations closer to the memory110. Although the processing-in-memory component112is illustrated as being disposed within the memory module104, in some examples, the described benefits of memory verification using processing-in-memory are realizable through near-memory processing implementations in which the processing-in-memory component112is disposed in closer proximity to the memory110(e.g., in terms of data communication pathways) than the core108of the host102.

The processing-in-memory component112is illustrated as receiving sparse matrix processing logic114, which represents instructions that are executable by the processing-in-memory component112to cause the processing-in-memory component112to perform sparse matrix operations using data stored in the memory110. In accordance with the described techniques, execution of the sparse matrix processing logic114causes the processing-in-memory component112to access a vector stored at a first location in memory110. In some implementations, the first location in memory110is a virtual memory location identified by a base virtual address for a corresponding hierarchical component of memory110(e.g., a base virtual address for a DRAM channel) in which the processing-in-memory component112is implemented. Execution of the sparse matrix processing logic114further causes the processing-in-memory component112to access a representation of a sparse matrix stored in a second location in the memory110. In some implementations, the second location in memory110represents a physical memory location (e.g., a DRAM array). In response to accessing the representation of the sparse matrix, the processing-in-memory component112is configured to store at least a portion of the sparse matrix representation locally (e.g., in one or more registers of the processing-in-memory component112).

In implementations, the representation of the sparse matrix is configured using a CSR or a CSC matrix representation format, an example of which is described in further detail below with respect toFIG.2. Specifically, in an example implementation where the sparse matrix representation is stored in memory110using CSR, execution of the sparse matrix processing logic114causes the processing-in-memory component112to identify a column index value for a non-zero element of the sparse matrix to be used in performing a sparse matrix operation (e.g., to be used in computing a SpMV product). In such an implementation, the column index value is an integer ranging from zero to M, inclusive, where a number of columns included in the sparse matrix is defined as M−1. In this implementation, the vector stored at the first location in memory110is a vector comprising M elements, such that the column index value indicates a corresponding position of one of the elements in the vector stored at the first location in memory110.

As another example, in an implementation where the sparse matrix representation is stored in memory110using CSC, execution of the sparse matrix processing logic114causes the processing-in-memory component112to identify a row index value for a non-zero element of the sparse matrix. In such an implementation the row index value is an integer ranging from zero to N, inclusive, where a number of rows included in the sparse matrix is defined as N−1. In such an implementation, the vector stored at the first location in memory110is a vector comprising N elements, such that the row index value indicates a corresponding position of one of the elements in the vector stored at the first location in memory110. In the following description, execution of the sparse matrix processing logic114is described in the context of an implementation where the sparse matrix is stored in memory110using a CSR format.

Using the index value (e.g., the column index value for a non-zero element of a sparse matrix stored using a CSR format), the processing-in-memory component112is configured to identify a corresponding element in the vector stored at the first location in memory110. In implementations where elements of the vector stored at the first location in memory110are stored contiguously, the processing-in-memory component112is configured to identify the corresponding element in the vector by computing an offset virtual address. The processing-in-memory component112computes the offset virtual address by incrementing a base virtual address for the vector stored at the first location in memory110using an offset identified by the index value (e.g., incrementing the base virtual address by an integer specified by the column index value for the non-zero element of the sparse matrix).

In implementations, the processing-in-memory component112is configured to identify the element in the vector stored at the first location in memory110using one or more indirect PIM commands for performing indirect addressing as described in 210133-US-NP., the disclosure of which is hereby incorporated by reference in its entirety. In this manner, the processing-in-memory component112is configured to execute the sparse matrix processing logic114to retrieve target data (e.g., the element in the vector) by determining a virtual address for the target data based on a physical memory address (e.g., the index value for a non-zero element in a sparse matrix, as defined by the sparse matrix representation stored in physical memory). In some implementations, executing the sparse matrix processing logic114causes the processing-in-memory component112to output the identified vector element as result116.

Alternatively or additionally, executing the sparse matrix processing logic114further causes the processing-in-memory component112to perform a matrix operation using the identified element from the vector stored at the first location in memory110and a corresponding non-zero entry from a sparse matrix representation stored at the second location in memory110. In an example implantation, the sparse matrix operation is performed as part of a SpMV algorithm and includes computing a product of the identified vector element and the non-zero entry from the sparse matrix representation. The product of the identified vector element and the non-zero entry from the sparse matrix representation is computed as a result vector element. In some implementations, the product of the identified vector element and the non-zero sparse matrix entry is by the processing-in-memory component112output as result116.

Instructions included in the sparse matrix processing logic114for outputting the result116are configurable in a variety of manners. For instance, in some implementations the sparse matrix processing logic114includes an instruction that causes the processing-in-memory component112to communicate the result116to the host102(e.g., via the interface106). Alternatively or additionally, in some implementations the sparse matrix processing logic114includes an instruction that causes the processing-in-memory component112to output the result116to a storage location in memory110(e.g., for subsequent access and/or retrieval by the host102). Alternatively or additionally, in some implementations the sparse matrix processing logic114includes an instruction that causes the processing-in-memory component112to store the result116locally (e.g., in a register of the processing-in-memory component112). In an implementation where the sparse matrix processing logic114previously caused the processing-in-memory component112to store at least a portion of a sparse matrix representation in a register of the processing-in-memory component112, executing the sparse matrix processing logic114causes the processing-in-memory component112to output the result116to the register of the processing-in-memory component112by overwriting the previously stored data.

In one example, the processing-in-memory component112receives the sparse matrix processing logic114from the host102and/or the core108(e.g., via the interface106). Alternatively or additionally, the processing-in-memory component112receives (e.g., loads) the sparse matrix processing logic114from a dedicated portion of the memory110(e.g., an externally non-addressable memory of a bank of the memory110). Alternatively or additionally, the processing-in-memory component112receives (e.g., loads) the sparse matrix processing logic114from a defined location within the system100(e.g., independent of creating traffic to/from the memory module104).

In some implementations, the sparse matrix processing logic114is received by the processing-in-memory component112as part of a command from the host102(e.g., as part of a command transmitted to the memory module104from the host102). The processing-in-memory component112is thus configured to perform the sparse matrix operations described herein responsive to an instruction by the host102. Alternatively or additionally, the processing-in-memory component112is configured to execute instructions set forth in the sparse matrix processing logic114independent of receiving a command or instruction from the host102. For instance, in an example implementation the processing-in-memory component112is configured to store the sparse matrix processing logic114locally (e.g., in one or more registers of the processing-in-memory component112). In such an implementation, the sparse matrix processing logic114causes the processing-in-memory component112to monitor one or more defined locations in memory110(e.g., a defined memory address range, non-contiguous storage locations in memory110, or a combination thereof) and execute instructions set forth in the sparse matrix processing logic114in response to a data write operation to the one or more defined locations in memory110(e.g., in response to a sparse matrix being written to a defined physical memory location).

Because the processing-in-memory component112executes the sparse matrix processing logic114to perform sparse matrix operations using data stored in memory110, the processing-in-memory component112performs the described techniques with minimal impact on the system100(e.g., without invalidating caches of the system100or causing traffic on the connection/interface106). For instance, the processing-in-memory component112performs sparse matrix operations on data stored in the memory110“in the background” with respect to the host102and the core108, which frees up cycles of the host102and/or the core108, reduces memory bus traffic (e.g., reduces traffic on the connection/interface106), and reduces power consumption relative to performing operations at the host102and/or the core108. Notably, because the processing-in-memory component112is closer to the memory110than the core108of the host102in terms of data communication pathways, performing sparse matrix operations using data stored in memory110is generally completed in a shorter amount of time using the processing-in-memory component112than if the same sparse matrix operations were performed using the same data at the core108of the host102.

For a detailed description of a sparse matrix representation stored in memory110and example operations performed by the processing-in-memory component112when executing the sparse matrix processing logic114, considerFIGS.2and3.

FIG.2depicts an example200of a sparse matrix and a representation of the sparse matrix in a CSR format.

The example200is depicted as including a sparse matrix202. The sparse matrix202is depicted as including five rows: row204, row206, row208, row210, and row212. The sparse matrix202is further depicted as including five columns: column214, column216, column218, column220, and column222. With five rows and five columns, the sparse matrix202includes 25 different elements in total. Although described herein with respect to a 5×5 sparse matrix for purposes of simplicity, the described techniques are not so limited and should be understood to extend to sparse matrices of significantly larger sizes. Among the 25 elements in the sparse matrix202, there are nine non-zero elements, represented as a, b, c, d, e, f, g, h, and i.

The example200is further depicted as including a representation224of the sparse matrix202. The representation224is formatted as a CSR format, also known as a compressed row storage format or Yale format, of the sparse matrix202. The representation224represents the sparse matrix202using a plurality of one-dimensional arrays that respectively include non-zero values of the sparse matrix202, column indices for the non-zero values, and extents of non-zero values included in respective rows of the sparse matrix202. For instance, representation224includes a value array226that contains the non-zero values of the sparse matrix202(e.g., a, b, c, d, e, f, g, h, and i).

The representation224further includes a column index array228, which contains column indices for the non-zero values of the sparse matrix202. For instance, each column of the sparse matrix202is assigned an integer value, with a leftmost column of the sparse matrix202being assigned an index value of zero. With respect to the illustrated example200, column214has an index value of zero, column216has an index value of one, column218has an index value of two, column220has an index value of three, and column222has an index value of four. In this manner, the ordering of column index values set forth in the column index array228identifies a corresponding column of the sparse matrix202in which a non-zero value of the value array226is located. For instance, values a, b, d, and f are each associated with a column index value of zero, values c and h are each associated with a column index value of one, value e is associated with a column index value of two, value g is associated with a column index value of three, and value i is associated with a column index value of four.

The representation224further includes a row index array230, including a sequence of index pointers that indicate how many non-zero values are included in respective rows of the sparse matrix202. Adjacent pairs of values in the row index array are useable to define how many non-zero values are included in a given row of the sparse matrix202. A position of a value pair in the row index array230identifies a corresponding row number in the sparse matrix202and a difference between values of the value pair describe how many non-zero values exist in the identified row. For instance, the row index array230includes five value pairs, one for each row in the sparse matrix202. As a specific example, value pair (0, 1) is positioned first in the row index array230, indicating that the value pair corresponds to row204and has a difference identifying that only one non-zero value exists in row204(e.g., value “a”). As another specific example, value pair (5, 7) is positioned fourth in the row index array230, indicating that the value pair corresponds to row210and has a difference identifying that two non-zero values exist in row210(e.g., values “f” and “g”).

FIG.3depicts an example300of sparse matrix operations performed by the processing-in-memory component112using the example sparse matrix ofFIG.2when executing the sparse matrix processing logic114. Specifically, the illustrated example300depicts an implementation where the processing-in-memory component112executes the sparse matrix processing logic114to perform SpMV using the sparse matrix202ofFIG.2.

In the illustrated example300, the processing-in-memory component112is depicted as performing SpMV using the sparse matrix202and a dense vector302as part of generating a result vector304. The dense vector302is representative of a one-dimensional array of values stored in virtual memory (e.g., stored at a base virtual address issued to a hierarchical component of memory110(e.g., a DRAM channel) in which the processing-in-memory component112is implemented. The dense vector302includes a plurality of elements, one for each column of the sparse matrix202. Specifically, dense vector302is depicted as including elements X0, X1, X2, X3, and X4.

Result vector304includes a same number of elements as dense vector302, depicted as elements Y0, Y1, Y2, Y3, and Y4. In computing elements of the result vector304using SpMV, each non-zero value of the sparse matrix202is multiplied with a corresponding one of the elements included in the dense vector302, where a column index for the non-zero element (e.g., as specified by column index array228) indicates a position of the corresponding one of the elements included in the dense vector302. The resulting products generated from multiplying non-zero elements of a given row in the sparse matrix202are then summed to achieve an element in the result vector304.

The illustrated example300depicts a plurality of operations306that are performed as part of computing individual elements of the result vector304. For instance, element Y0corresponds to a first position in a sequence of elements of the result vector304, and is thus computed using non-zero values from a first row of the sparse matrix202(e.g., using non-zero elements included in row204). Non-zero elements from row204are individually multiplied by corresponding values in the dense vector302and the resulting products are summed. In a similar manner, element Y1is computed by summing the products of non-zero elements from row206multiplied by values in the dense vector302, where respective values in the dense vector302are identified using the column index array228.

Specifically, operations306demonstrate how Y0is computed as the product of value “a” in the sparse matrix202with element X0in the dense vector302. Operations306further demonstrate how Y1is computed as the sum of the product of value “b” in the sparse matrix202with element X0in the dense vector302and the product of value “c” with element X1. Operations306further demonstrate how Y2is computed as the sum of the product of value “d” with element X0 and the product of value “e” with element X2. Operations306further demonstrate how Y3is computed as the sum of the product of value “f” with element X0and the product of value “g” with element X3. Operations306further demonstrate how Y4is computed as the sum of the product of value “h” with element X1and the product of value “i” with element X4.

In implementations, the processing-in-memory component112is configured to execute the sparse matrix processing logic114to compute any one or more of the products that define one or more of the elements in the result vector304and output a result of the computation as result116. For instance, in an example implementation the processing-in-memory component112is configured to compute a single product (e.g., d·X0) and output the resulting single product as the result116. In other implementations, the processing-in-memory component112is configured to compute multiple products, such as products involving non-zero entries for one or more rows of the sparse matrix202or one or more columns of the sparse matrix202, and output the computed products as result116. In implementations where the processing-in-memory component112computes multiple products as part of computing the result vector304, result116is generated to specify unsummed results of the multiple products. For instance, in an implementation where the processing-in-memory component112is tasked with computing SpMV products for non-zero elements in row208of the sparse matrix202, the result116is generated to specify the respective products of d·X0and e·X2, without summing the respective products. Alternatively, the processing-in-memory component112is configured to sum the results of multiple products, such that in the implementation where the processing-in-memory component112is tasked with computing SpMV products for non-zero elements in row208of the sparse matrix202, result116includes a single value for Y2.

Having considered example details of performing sparse matrix operations using compressed sparse matrix representations, consider an example of using processing-in-memory to perform sparse matrix operations.

FIG.4depicts an example400of using processing-in-memory to perform sparse matrix operations.

The example400is depicted as including the host102, the memory110, and the processing-in-memory component112. The processing-in-memory component112is depicted as receiving (e.g., loading) and executing instructions included in the sparse matrix processing logic114, which cause the processing-in-memory component112to perform one or more operations using data for a sparse matrix stored in memory110. Example locations in memory110include a bank of the memory110, a cell of the memory110, a block of the memory110, and so forth. In accordance with the techniques described herein, the sparse matrix processing logic114advantageously enable the processing-in-memory component112to perform sparse matrix operations using first data stored in virtual memory and second data stored in physical memory. In executing the instructions set forth in the sparse matrix processing logic114, the processing-in-memory component112is configured to retrieve a dense vector from memory110via a dense vector request402. The dense vector request402is representative of a request for a vector stored at a base virtual address for a copy of a dense vector assigned to a hierarchical component of memory110(e.g., a base virtual address for a DRAM channel) in which the processing-in-memory component112is implemented. In implementations, the base virtual address for the memory location from which the dense vector is requested is defined by the sparse matrix processing logic114.

The processing-in-memory component112is configured to access the dense vector404from the base virtual address in memory110. For instance, the processing-in-memory component112accesses the dense vector302from a base virtual address specified by the sparse matrix processing logic114. In some implementations, the processing-in-memory component112stores the dense vector404in one or more registers of the processing-in-memory component112. Alternatively, in some implementations the processing-in-memory component112accesses data included in the dense vector404from virtual memory without storing one or more elements of the dense vector404in a register of the processing-in-memory component112. In executing the instructions set forth in the sparse matrix processing logic114, the processing-in-memory component112is further configured to retrieve at least a portion of a sparse matrix representation from memory110via a sparse matrix request406. The sparse matrix request406is representative of a request for a portion or an entirety of a sparse matrix representation stored at one or more physical memory locations in memory110.

The processing-in-memory component112is configured to access at least a portion of a sparse matrix representation408from memory110in response to the sparse matrix request406. In some implementations, the portion of the sparse matrix representation retrieved as part of the sparse matrix representation408includes a value array and a column index array for a sparse matrix representation formatted using CSR. For instance, the sparse matrix representation408is representative of the value array226and the column index array228of the representation224for sparse matrix202. In some implementations, the processing-in-memory component112is configured to store at least a portion of the sparse matrix representation408locally, such as in one or more registers of the processing-in-memory component112. For instance, the processing-in-memory component112stores the at least one non-zero value of a sparse matrix in one or more registers. In this manner, one or more sparse matrix non-zero values are readily accessible for subsequent processing when computing one or more sparse matrix operations.

In executing the instructions set forth in the sparse matrix processing logic114, the processing-in-memory component112is further configured to identify an index value410for at least one non-zero element included in the sparse matrix representation408. The processing-in-memory component112, for instance, identifies an index value set forth in the column index array228for a non-zero element included in the value array226. Based on the identified index value for a non-zero element in the sparse matrix representation408, the processing-in-memory component112identifies a dense vector element412in the dense vector404. The processing-in-memory component112, for instance, identifies an integer value specified by the identified index value and computes an offset virtual address by incrementing the base virtual address of the dense vector404using the integer value.

The processing-in-memory component112then uses the offset virtual address to retrieve an element from the dense vector404stored at the offset virtual address. In some implementations, although the dense vector request402and accessing the dense vector404are depicted inFIG.4as occurring above the block representing where the processing-in-memory component112identifies the dense vector element412, in some implementations the dense vector request402is not communicated until after the processing-in-memory component112identifies the dense vector element412. For instance, in some implementations, after identifying the dense vector element412, the processing-in-memory component112communicates a dense vector request402to the offset virtual address and retrieves only the element stored at the offset virtual address as the dense vector404. In this manner, the processing-in-memory component112is configured to request no more of the dense vector404than is needed to perform the sparse matrix operation with which the processing-in-memory component112is tasked (e.g., retrieve a single dense vector element for a single non-zero value in the sparse matrix representation408).

In some implementations, the processing-in-memory component112is configured to store the identified dense vector element locally, such as in one or more registers of the processing-in-memory component112. The processing-in-memory component112is configured to perform the steps of identifying an index value410and identifying a dense vector element412for each non-zero element in the sparse matrix representation408that the processing-in-memory component112is tasked with processing. In some implementations, executing the sparse matrix processing logic114further causes the processing-in-memory component112to perform masking on the identified dense vector element, based on a data type of the dense vector element. For instance, in an example implementation where the non-zero value of the sparse matrix representation and the corresponding dense vector element are stored as floating-point numbers, the processing-in-memory component112performs masking to remove a plurality of upper bits so that data stored in one or more registers of the processing-in-memory component112(e.g., the non-zero value and the dense vector element) are represented as single precision values.

In executing the sparse matrix processing logic114, the processing-in-memory component112is further configured to compute a result116based on the dense vector element414. The processing-in-memory component112, for instance, computes a result vector element by multiplying the non-zero element in the sparse matrix representation408and the identified dense vector element as part of executing an SpMV algorithm. In some implementations, the processing-in-memory component112is configured to store a result416of the result116computed using the dense vector element and the non-zero sparse matrix element. The processing-in-memory component112, for instance, stores the result116locally, such as in one or more registers of the processing-in-memory component112. In some implementations, storing the result416is performed by overwriting data previously stored in the one or more registers of the processing-in-memory component112. For instance, the processing-in-memory component112overwrites at least one sparse matrix non-zero value and/or at least one identified dense vector element previously written to one or more registers of the processing-in-memory component112. Alternatively, in some implementations the processing-in-memory component112stores the result116locally without overwriting data previously written to one or more registers of the processing-in-memory component112.

Alternatively or additionally, the processing-in-memory component112is configured to store the result416by writing the result116to a storage location of memory110. Alternatively or additionally, in some implementations the processing-in-memory component112is configured to output the result116to the host102. For instance, the processing-in-memory component112communicates the result116to the host102via the interface106. For instance, in an example implementation the processing-in-memory component112communicates the result116as individual result vector elements to the host102for further processing. As a specific example, the processing-in-memory component112communicates the result116as indicating the respective products of d·X0and e·X2, unsummed, such that the host102is able to perform the summation to compute the final value of Y2for the result vector304.

FIG.5depicts a procedure500in an example implementation of performing sparse matrix operations using processing-in-memory.

Sparse matrix processing logic is loaded into a processing-in-memory component (block502). For instance, sparse matrix processing logic114is loaded into processing-in-memory component112from the host102, from a dedicated portion of the memory110, from another location within the memory110, combinations thereof, and so forth. As an example, the sparse matrix processing logic114is loaded into the processing-in-memory component112at the instruction of an application kernel executing on the host102. As another example, the sparse matrix processing logic114is loaded into the processing-in-memory component112upon an initialization of the system100(e.g., during boot of the system100).

The sparse matrix processing logic is executed by the processing-in-memory component (block504). As part of executing the sparse matrix processing logic, an index value for a non-zero element in a sparse matrix is identified using a representation of a sparse matrix stored at a location in memory of a memory module implementing the processing-in-memory component (block506). The processing-in-memory component112, for instance, accesses a sparse matrix representation408from physical memory in memory110and identifies a non-zero value included in the sparse matrix. As a specific example, the processing-in-memory component112identifies a non-zero element included in the value array226for the representation224of sparse matrix202. The processing-in-memory component112then identifies an index value for the non-zero element in the sparse matrix representation408. Continuing the specific example, the processing-in-memory component112identifies an index value from the column index array228of the representation224for sparse matrix202.

As further part of executing the sparse matrix processing logic, an element from a vector stored at a different location in the memory of the memory module is retrieved using the index value (block508). The processing-in-memory component112, for instance, identifies a base virtual address of a dense vector stored in virtual memory from the sparse matrix processing logic114. The processing-in-memory component112then computes an offset virtual address by incrementing the base virtual address by an integer value defined by the index value. The processing-in-memory component112retrieves a dense vector element stored at the offset virtual address using a dense vector request402.

A result that includes the element from the vector is then output (block510). The processing-in-memory component112, for instance, outputs the retrieved dense vector element as result116. Alternatively or additionally, the processing-in-memory component112further processes the retrieved dense vector element using one or more sparse matrix operations. For instance, the processing-in-memory component112computes a result vector element by multiplying the dense vector element by the non-zero element in the sparse matrix corresponding to the index value that was used to retrieve the vector element and outputs the result vector element as the result116. In some implementations, the processing-in-memory component112outputs the result116to the host102. Alternatively or additionally, the processing-in-memory component112stores the result116for subsequent access by the host102, such as in one or more storage locations of memory110, locally in one or more registers of the processing-in-memory component112, or combinations thereof.

FIG.6depicts a procedure600in an example implementation of performing sparse matrix operations using processing-in-memory.

A vector stored in virtual memory is accessed by a processing-in-memory component (block602). The processing-in-memory component112, for instance, transmits a dense vector request402to memory110and retrieves a dense vector404from a base virtual address in memory110. In implementations, the base virtual address for the dense vector404is specified by sparse matrix processing logic114executed by the processing-in-memory component112.

A representation of a sparse matrix stored in physical memory is accessed by the processing-in-memory component (block604). The processing-in-memory component112, for instance, transmits a sparse matrix request406to memory110and retrieves a sparse matrix representation408from a physical memory location in memory110. In implementations, the physical memory location for the sparse matrix representation408is specified by the sparse matrix processing logic114executed by the processing-in-memory component112.

An index value for the non-zero value in the sparse matrix is identified by the processing-in-memory component using the representation of the sparse matrix (block606). The processing-in-memory component112, for instance, accesses a sparse matrix representation408from physical memory in memory110and identifies a non-zero value included in the sparse matrix. As a specific example, the processing-in-memory component112identifies a non-zero element included in the value array226for the representation224of sparse matrix202. The processing-in-memory component112then identifies an index value for the non-zero element in the sparse matrix representation408. Continuing the specific example, the processing-in-memory component112identifies an index value from the column index array228of the representation224for sparse matrix202.

An element in the vector is then identified by the processing-in-memory component using the index value (block608). The processing-in-memory component112, for instance, identifies a base virtual address of a dense vector stored in virtual memory from the sparse matrix processing logic114. The processing-in-memory component112then computes an offset virtual address by incrementing the base virtual address by an integer value defined by the index value. The processing-in-memory component112retrieves a dense vector element stored at the offset virtual address using a dense vector request402.

A result vector element is then computed by the processing-in-memory component using the element in the vector and the non-zero value in the sparse matrix (block610). For instance, the processing-in-memory component112computes a result vector element by multiplying the dense vector element by the non-zero element in the sparse matrix corresponding to the index value that was used to retrieve the vector element and outputs the result vector element as the result116. In some implementations, the processing-in-memory component112outputs the result116to the host102. Alternatively or additionally, the processing-in-memory component112stores the result116for subsequent access by the host102, such as in one or more storage locations of memory110, locally in one or more registers of the processing-in-memory component112, or combinations thereof.

The example techniques described herein are merely illustrative and many variations are possible based on this disclosure. Although features and elements are described above in particular combinations, each feature or element is usable alone without the other features and elements or in various combinations with or without other features and elements.

The various functional units illustrated in the figures and/or described herein (including, where appropriate, the host102having the core108and the memory module104having the memory110and the processing-in-memory component112) are implemented in any of a variety of different manners such as hardware circuitry, software or firmware executing on a programmable processor, or any combination of two or more of hardware, software, and firmware. The methods provided are implemented in any of a variety of devices, such as a general-purpose computer, a processor, or a processor core. Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a graphics processing unit (GPU), a parallel accelerated processor, a plurality of microprocessors, one or more microprocessors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine.

In one or more implementations, the methods and procedures provided herein are implemented in a computer program, software, or firmware incorporated in a non-transitory computer-readable storage medium for execution by a general-purpose computer or a processor. Examples of non-transitory computer-readable storage mediums include a read only memory (ROM), a random-access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs).