Matrix processing apparatus

Methods, systems, and apparatus, including a system for transforming sparse elements to a dense matrix. The system is configured to receive a request for an output matrix based on sparse elements including sparse elements associated with a first dense matrix and sparse elements associated with a second dense matrix; obtain the sparse elements associated with the first dense matrix fetched by a first group of sparse element access units; obtain the sparse elements associated with the second dense matrix fetched by a second group of sparse element access units; and transform the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix to generate the output dense matrix that includes the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix.

BACKGROUND

This specification generally relates to using circuitry to process a matrix.

SUMMARY

According to one innovative aspect of the subject matter described in this specification, a matrix processor can be used to perform a sparse-to-dense or a dense-to-sparse matrix transformation. In general, high performance computing systems may use linear algebra routines to process a matrix. In some instances, the size of the matrix may be too large to fit in one data storage, and different portions of the matrix may be sparsely stored in different locations of a distributed data storage system. To load the matrix, the central processing unit of a computing system may instruct a separate circuitry to access different portions of the matrix. The circuitry may include multiple memory controllers arranged according to a network topology, where sparse data may be partitioned and stored based on a set of predetermined rules. Each memory controller may gather sparse data based on the set of predetermined rules, to perform concurrent computation on the sparse data, and to generate a dense matrix that can be concatenated together for the central processing unit to perform further processing.

In general, one innovative aspect of the subject matter described in this specification can be embodied in a system for transforming sparse elements to a dense matrix. The system includes a first group of sparse element access units configured to fetch sparse elements associated with a first dense matrix; and a second group of sparse element access units configured to fetch sparse elements associated with a second dense matrix that is different from the first dense matrix. The system is configured to receive a request for an output matrix based on sparse elements including sparse elements associated with a first dense matrix and sparse elements associated with a second dense matrix; obtain the sparse elements associated with the first dense matrix fetched by the first group of sparse element access units; obtain the sparse elements associated with the second dense matrix fetched by the second group of sparse element access units; and transform the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix to generate the output dense matrix that includes the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix.

These and other implementations can each optionally include one or more of the following features. For example, the first group of sparse element access units may include a first sparse element access unit and a second sparse element access unit. The first sparse element access unit may be configured to fetch a first subset of the sparse elements associated with the first dense matrix. The second sparse element access unit may be configured to fetch a second, different, subset of the sparse elements associated with the first dense matrix.

The first sparse element access unit is configured to receive a request for a plurality of sparse elements including the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix; and transmit the request to the second sparse element access unit. The first sparse element access unit may be configured to determine that an identify of a particular sparse element of the plurality of sparse elements matches with an identify of one of the first subset of the sparse elements associated with the first dense matrix. The first sparse element access unit may be configured to fetch the first subset of the sparse elements associated with the first dense matrix including the particular sparse element in response to determining that the identity of the particular sparse element of the plurality of sparse elements matches with the identify of one of the first subset of the sparse elements associated with the first dense matrix.

The first sparse element access unit may be configured to fetch the first subset of the sparse elements associated with the first dense matrix from a first data shard, and the second sparse element access unit may be configured to fetch the second, different, subset of the sparse elements associated with the first dense matrix from a second, different data shard. The first sparse element access unit may configured to transform the first subset of the sparse elements associated with the first dense matrix to generate a third dense matrix, and the second sparse element access unit may be configured to receive the third dense matrix; transform the second subset of the sparse elements associated with the second dense matrix to generate a fourth dense matrix; and transform the third dense matrix with the fourth dense matrix to generate a fifth dense matrix that includes the first subset of the sparse elements associated with the first dense matrix and the second subset of the sparse elements associated with the first dense matrix.

The first group of sparse element access units and the second group of sparse element access units may be arranged in a two-dimensional mesh configuration. The first group of sparse element access units and the second group of sparse element access units may be arranged in a two-dimensional torus configuration. The sparse elements associated with and first dense matrix and the sparse elements associated with second dense matrix may be multi-dimensional matrices, and the output dense matrix may be a vector.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages. Connecting memory controller units according to a network topology allows the partitioning of the storage of sparse data to following a set of predetermined rules. Shifting the sparse-to-dense data loading task from the central processing unit to a separate circuitry increases the computation bandwidth of the central processing unit and decreases the processing cost of the system. By using specialized circuitry, the use of processors that are specialized for dense linear algebra to fetch sparse data can be avoided. By using many memories simultaneously in the distributed system, the sum aggregate bandwidth available in the distributed system is higher than the bandwidth for a single memory bank that requires serialization and has a single-memory-cap on the aggregate bandwidth.

DETAILED DESCRIPTION

In general, data can be represented in the form of a matrix and a computing system may manipulate the data using linear algebra algorithms. A matrix may be a one-dimensional vector or a multi-dimensional matrix. A matrix may be represented by a data structure, such as a database table or a variable. However, when the size of a matrix is too large, it may not be possible to store the entire matrix in one data storage. A dense matrix may be transformed into multiple sparse elements, where each sparse element may be stored in a different data storage. A sparse element of a dense matrix may be a matrix where only a small sub-matrix of the matrix (e.g., a single-value element, a row, a column, or a sub-matrix) have non-zero values. When a computing system needs to access the dense matrix, the central processing unit (CPU) may start a thread that reaches to each of the data storage to fetch the stored sparse elements, and applies a sparse-to-dense transform to get back the dense matrix. However, the amount of time it takes to fetch all the sparse elements may be long, and the computation bandwidths of the CPU may be under-utilized as the result. In some cases, a computing system may need to access sparse elements of several dense matrices to form a new dense matrix, where the dense matrices may not have equal dimensions. The CPU idle time associated with a thread reaching to each of the data storage to fetch sparse elements of different dense matrices may encounter different waiting time, and may further impact the performance of the computing device in an undesirable manner. In some cases, a computing system may need to access sparse elements of several dense matrices to form a new dense matrix, where the sparse elements may not have equal dimensions. The CPU idle time associated with a thread reaching to each of the data storage to fetch sparse elements of different dense matrices may encounter different waiting time, and may further impact the performance of the computing device in an undesirable manner. A hardware sparse-dense transform unit that is separate from a CPU may increase the computation bandwidth of the processor by collecting sparse elements and transforming the sparse element into a dense matrix independent of the CPU operations.

FIG. 1shows a block diagram of an example computing system100for transforming sparse elements from one or more dense matrices to generate a dense matrix. The computing system100includes a processing unit102, a sparse-dense transform unit104, and data shards106a-106k, where k is an integer greater than one. In general, the processing unit102processes an instruction for accessing a target dense matrix, and sends an instruction110to the sparse-dense transform unit104to generate the target dense matrix. The sparse-dense transform unit104accesses the corresponding sparse elements108a-108nfrom one or more of the data shards106a-106k, where n is an integer greater than one. The sparse-dense transform unit104generates the target dense matrix112using the corresponding sparse elements108a-108n, and provides the target dense matrix112to the processing unit102for further processing. For example, the sparse elements108a-108nmay be two-dimensional matrices having different sizes, and the sparse-dense transform unit104may generate the target dense matrix112by transforming each of the sparse elements108a-108ninto a vector, and concatenating the n vectors into a single vector.

In some implementations, the processing unit102may process an instruction for updating a target dense matrix and send an updated dense matrix to the sparse-dense transform unit104. The sparse-dense transform unit104may transform the updated dense matrix into corresponding sparse elements and update one or more sparse elements stored in the data shards106a-106kaccordingly.

The processing unit102is configured to process instructions for execution within the computing system100. The processing unit102may include one or more processors. In some implementations, the processing unit102is configured to process the target dense matrix112generated by the sparse-dense transform unit104. In some other implementations, the processing unit102may be configured to request the sparse-dense transform unit104to generate the target dense matrix112, and another processing unit may be configured to process the target dense matrix112. The data shards106a-106kstore data including sparse elements108a-108n. In some implementations, the data shards106a-106kmay be a volatile memory unit or units. In some other implementations, the data shards106a-106kmay be a non-volatile memory unit or units. The data shards106a-106kmay also be another form of computer-readable medium, such as devices in a storage area network or other configurations. The data shards106a-106kmay be coupled to the sparse-dense transform unit104using electrical connections, optical connections, or wireless connections. In some implementations, the data shards106a-106kmay be part of the sparse-dense transform unit104.

The sparse-dense transform unit104is configured to determine a dense matrix based on sparse elements. In some implementations, the sparse-dense transform unit104may be configured to determine locations of sparse elements based on a dense matrix. In some implementations, the sparse-dense transform unit104may include multiple interconnected sparse element access units, as described in more detail below with reference toFIGS. 2A-2D.

In some implementations, the sparse element access units X1,1to XM,Nmay be physically or logically arranged into a two-dimensional mesh configuration. For example, the sparse element access unit X1,1is directly coupled to the sparse element access units X1,2and X2,1. As another example, the sparse element access unit X2,2is directly coupled to the sparse element access units X2,1, X3,1, X2,3, and X1,2. The coupling between two sparse element access units may be an electrical connection, an optical connection, a wireless connection, or any other suitable connection.

In some other implementations, the sparse element access units X1,1to XM,Nmay be physically or logically arranged into a two-dimensional torus configuration. For example, the sparse element access unit X1,1is directly coupled to the sparse element access units X1,2, X2,1, X1,N, and XM,1. As another example, the sparse element access unit XM,Nis directly coupled to the sparse element access units XM,N-1, XM-1,N, XM,1, and X1,N.

In some implementations, the sparse-dense transform unit200may be configured to partition the sparse elements transformed from dense matrices according to a set of predetermined conditions. Each row of the sparse element access units X1,1to XM,Nmay be partitioned to access sparse elements transformed from specific dense matrices. For example, the sparse-dense transform unit200may be configured to access sparse elements transformed from dense matrices that correspond to 1,000 different database tables of a computer model. One or more of the database tables may have different sizes. The first row202of the sparse element access units may be configured to access sparse elements transformed from database table No. 1 to database table No. 100, the second row204of the sparse element access units may be configured to access sparse elements transformed from database table No. 101 to database table No. 300, and the M-th row206of the sparse element access units may be configured to access sparse elements transformed from database table No. 751 to database table No. 1,000. In some implementations, the partitions may be configured by hardware instructions before a processor accesses sparse elements using the sparse-dense transform unit200.

Each column of the sparse element access units X1,1to XM,Nmay be partitioned to access a subset of the sparse elements transformed from the specific dense matrices. For example, the dense matrix corresponding to database table No. 1 may be transformed into 1,000 sparse elements, where the 1,000 sparse elements are accessible by the first row202as described above. The sparse element access unit X1/1may be configured to access sparse elements No. 1 to No. 200 of database table No. 1, and the sparse element access unit X1,2may be configured to access sparse elements No. 201 to No. 500 of database table No. 1. As another example, the dense matrix corresponding to database table No. 2 may be transformed into 500 sparse elements, where the 500 sparse elements are accessible by the first row202as described above. The sparse element access unit X1,1may be configured to access sparse elements No. 1 to No. 50 of database table No. 2, and the sparse element access unit X1,2may be configured to access sparse elements No. 51 to No. 200 of database table No. 2. As another example, the dense matrix corresponding to database table No. 1,000 may be transformed into 10,000 sparse elements, where the 10,000 sparse elements are accessible by the M-th row206as described above. The sparse element access unit XM,1may be configured to access sparse elements No. 1 to No. 2,000 of database table No. 1,000, and the sparse element access unit XM,Nmay be configured to access sparse elements No. 9,000 to No. 10,000 of database table No. 1,000.

FIG. 2Bshows an example of how the sparse-dense transform unit200may request sparse elements using a two-dimensional mesh network of the sparse element access units. As an example, a processing unit may execute an instruction requesting the sparse-dense transform unit200for a dense one-dimensional vector generated using sparse elements No. 1 to No. 50 of database table No. 1, sparse elements No. 100 to No. 200 of database table No. 2, and sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. After the sparse-dense transform unit200receives the request from the processing unit, the sparse-dense transform unit200may instruct the sparse element access unit X1/1to broadcast a request for the sparse elements to the other sparse element access units in the mesh network. The sparse element access unit X1,1may broadcast a request222to the sparse element access unit X1,2and a request224to the sparse element access unit X2,1. After receiving the request222, the sparse element access unit X1,2may broadcast a request226to the sparse element access unit X1,3. In some implementations, a sparse element access unit may be configured to broadcast a request to another sparse element access unit based on a routing scheme. For example, the sparse element access unit X1,2may not be configured to broadcast a request to the sparse element access unit X2,2because the sparse element access unit X2,2is configured to receive a broadcast from the sparse element access unit X2,1. The routing scheme may be static or dynamically generated. For example, the routing scheme may be a lookup table. In some implementations, a sparse element access unit may be configured to broadcast the request224to another sparse element access unit based on the request224. For example, the request224may include identifications of the requested sparse elements (e.g., database table No. 1, sparse elements No. 1 to No. 50), and the sparse element access unit X1,2may determine whether to broadcast the request224to the sparse element access unit X2,2and/or the sparse element access unit X1,3based on the identifications. The broadcast process propagates through the mesh network, where the sparse element access unit XM,Nreceives a request230from the sparse element access unit XM,N-1.

FIG. 2Cshows an example of how the sparse-dense transform unit200may generate the requested dense matrix using the two-dimensional mesh network of the sparse element access units. In some implementations, after a sparse element access unit receives the broadcasted request, the sparse element access unit is configured to determine whether it is configured to access any of the requested sparse elements. For example, the sparse element access unit X1,1may determine that it is configured to access sparse elements No. 1 to No. 50 of database table No. 1, but it is not configured to access sparse elements No. 100 to No. 200 of database table No. 2 or sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. In response to determining that it is configured to access sparse elements No. 1 to No. 50 of database table No. 1, the sparse element access unit X1,1may fetch sparse elements No. 1 to No. 50 of database table No. 1 from the data shard(s) where these sparse elements are being stored, and generate a dense matrix242based on these sparse elements.

As another example, the sparse element access unit X2,1may determine that it is not configured to access any of the sparse elements No. 1 to No. 50 of database table No. 1, the sparse elements No. 100 to No. 200 of database table No. 2, or sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. In response to determining that it is not configured to access any of the requested sparse elements, the sparse element access unit X2/1may perform no further action.

As another example, the sparse element access unit X1,2may determine that it is configured to access sparse elements No. 100 to No. 200 of database table No. 2, but it is not configured to access sparse elements No. 1 to No. 50 of database table No. 1 or sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. In response to determining that it is configured to access sparse elements No. 100 to No. 200 of database table No. 2, the sparse element access unit X1,2may fetch these sparse elements from the data shard(s) where these sparse elements are being stored, and generate a dense matrix244based on these sparse elements. In some implementations, after a sparse element access unit generates a dense matrix, the sparse element access unit may be configured to forward the dense matrix to the sender of the broadcast request. Here, the sparse element access unit X1,2forwards the dense matrix244to the sparse element access unit X1,1.

As another example, the sparse element access unit XM,Nmay determine that it is configured to access sparse elements No. 9,050 to No. 9,060 of database table No. 1,000, but it is not configured to access sparse elements No. 1 to No. 50 of database table No. 1 or sparse elements No. 100 to No. 200 of database table No. 2. In response to determining that it is configured to access sparse elements No. 9,050 to No. 9,060 of database table No. 1,000, the sparse element access unit XM,Nmay fetch these sparse elements from the data shard(s) where these sparse elements are being stored, and generate a dense matrix246based on these sparse elements. In some implementations, after a sparse element access unit generates a dense matrix, the sparse element access unit may be configured to forward the dense matrix to the sender of the broadcast request. Here, the sparse element access unit XM,Nforwards the dense matrix246to the sparse element access unit XM,N-1. In the next cycle, the sparse element access unit XM,N-1is configured to forward the dense matrix246to the sparse element access unit XM,N-1. This process continues until the sparse element access unit X2,1has forwarded the dense matrix246to the sparse element access unit X1,1.

In some implementations, the sparse-dense transform unit200is configured to transform the dense matrices generated by the sparse element access units and generate a dense matrix for the processor unit. Here, the sparse-dense transform unit200transforms the dense matrices242,244, and246into a dense matrix for the processor unit. For example, the dense matrix242may have dimensions of 100-by-10, the dense matrix244may have dimensions of 20-by-100, and the dense matrix246may have dimensions of 3-by-3. The sparse-dense transform unit200may transform the dense matrices242,244, and246into a vector with dimensions of 1-by-3009. Advantageously, the partitioning of the rows according to dense matrices (e.g., database tables) allows the sparse-dense transform unit200to obtain all the requested sparse elements after the generated dense matrices has propagated from column N to column 1. The partitioning of the columns reduces bandwidth bottlenecks caused by accessing too many sparse elements using only one of the sparse element access units.

FIG. 2Dshows an example of how the sparse-dense transform unit200may update sparse elements based on a dense matrix using a two-dimensional mesh network of the sparse element access units. As an example, a processing unit may execute an instruction requesting the sparse-dense transform unit200to update the stored sparse elements using a dense one-dimensional vector generated using sparse elements No. 1 to No. 50 of database table No. 1 and sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. After the sparse-dense transform unit200receives the request from the processing unit, the sparse-dense transform unit200may instruct the sparse element access unit X1,1to broadcast a sparse elements update request to the other sparse element access units in the mesh network, where the sparse elements update request may include the dense one-dimensional vector provided by the processing unit. In some implementations, the sparse element access unit X1/1may determine whether it is assigned to access the sparse elements included in the dense one-dimensional vector. In response to determining that it is assigned to access the sparse elements included in the dense one-dimensional vector, the sparse element access unit X1/1may update the sparse elements stored in the data shard(s). Here, the sparse element access unit X1,1determines that it is assigned to access sparse elements No. 1 to No. 50 of database table No. 1, and the sparse element access unit X1,1executes an instruction to update these sparse elements in the data shard(s).

In general, the request identification unit302is configured to receive the request342to fetch sparse elements stored in one or more data shards330, and determine whether the sparse element access unit300is assigned to access the sparse elements indicated by the request342. In some implementations, the request identification unit302may determine whether the sparse element access unit300is assigned to access the sparse elements indicated by the request342by using a lookup table. For example, if an identification of a particular requested sparse element (e.g., No. 1 of database table No. 1) is included in the lookup table, the request identification unit302may send a signal344to the data fetch unit304to fetch the particular requested sparse element. If an identification of a particular requested sparse element (e.g., No. 1 of database table No. 1) is not included in the lookup table, the request identification unit302may discard the received request. In some implementations, the request identification unit302may be configured to broadcast the received request to another sparse element access unit on the node network320.

The data fetch unit304is configured to fetch one or more requested sparse elements from the data shards330in response to receiving the signal344. In some implementations, the data fetch unit304includes one or more processors322a-322k, where k is an integer. Processors322a-322kmay be vector processing units (VP U), array processing units, or any suitable processing units. In some implementations, the processors322a-322kare arranged to be near the data shards330to reduce the latency between the processors322a-322kand data shards330. Based on the number of requested sparse elements that the sparse element access unit300are assigned to fetch, the data fetch unit304may be configured to generate one or more requests to be distributed among the processors322a-322k. In some implementations, each of the processors322a-322kmay be assigned to specific sparse elements based on the identification of the sparse elements, and the data fetch unit304may be configured to generate one or more requests for the processors322a-322kbased on the identification of the sparse elements. In some implementations, the data fetch unit304may determine the processor assignment by using a lookup table. In some implementations, the data fetch unit304may general multiple batches for the processors322a-322k, where each batch is a request for a subset of the requested sparse element. The processors322a-322kare configured to independently fetch the assigned sparse elements from the data shards330, and to forward the fetched sparse elements346to the sparse reduce unit306.

The sparse reduce unit306is configured to reduce the dimensions of the fetched sparse elements346. For example, each of the processors322a-322kmay generate a sparse element having dimensions of 100-by-1. The sparse reduce unit306may receive fetched sparse elements346having dimensions of 100-by-k, and to generate sparse-reduced elements348by reducing the dimensions of the fetched sparse elements346to 100-by-1 by logic operations, arithmetic operations, or a combination of both. The sparse reduce unit306is configured to output the sparse-reduced elements348to the concatenation unit308.

The concatenation unit308is configured to rearrange and concatenate the sparse-reduced elements348to generate concatenated elements350. For example, The sparse element access unit X1,1may be configured to access sparse elements No. 1 to No. 200 of database table No. 1. Processor322amay return the fetched sparse element No. 10 to the sparse reduce unit306sooner than processor322bthat is configured returns the fetched sparse element No. 5. The concatenation unit308is configured to rearrange the later-received sparse element No. 5 to be ordered before the earlier-received sparse element No. 10, and concatenate sparse elements No. 1 to No. 200 as the concatenated elements350.

The compress/decompress unit310is configured to compress the concatenated elements350to generate a dense matrix352for the node network320. For example, the compress/decompress unit310may be configure to compress the zero values in the concatenated elements350to improve the bandwidth of the node network320. In some implementations, the compress/decompress unit310may decompress a received dense matrix. For example, the sparse element access unit300may receive a dense matrix from a neighboring sparse element access unit via the node network320. The sparse element access unit300may decompress the received dense matrix, and may concatenate the decompressed dense matrix with the concatenated elements350to form updated concatenated elements that can be compressed and then output to the node network320.

FIG. 3Bshows an example of how the sparse element access unit300may update sparse elements based on a dense matrix received from the node network320. As an example, a processing unit may execute an instruction requesting the sparse-dense transform unit to update the stored sparse elements using a dense one-dimensional vector generated using sparse elements No. 1 to No. 50 of database table No. 1 and sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. After the sparse-dense transform unit receives the request from the processing unit, the sparse-dense transform unit may send a request362to instruct the sparse element access unit300to determine whether it is assigned to access the sparse elements included in the dense one-dimensional vector. The request identification unit302is configured to determine whether the sparse element access unit300is assigned to access the sparse elements included in the dense one-dimensional vector. In response to determining that the sparse element access unit300is assigned to access the sparse elements included in the dense one-dimensional vector, the request identification unit302may send an indication364to the split unit312to update the sparse elements stored in the data shard(s).

The split unit312is configured to transform a received dense matrix into sparse elements that can be updated in the data shards330by the data fetch unit304. For example, the split unit312may be configured to transform the dense one-dimensional vector into multiple sparse elements, and instruct the data fetch unit304to update the sparse elements stored in the data shards330that the sparse element access unit300is assigned to fetch.

FIG. 4is a flow diagram that illustrates an example of a process400for generating a dense matrix. The process400may be performed by a system, such as the sparse-dense transform unit104or the sparse-dense transform unit200. The system may include a first group of sparse element access units and a second group of sparse element access units. For example, referring toFIG. 2A, the sparse-dense transform unit200may include M-by-N sparse element access units X1/1to XM,Nthat are physically or logically arranged into M rows and N columns. Each row of the sparse element access units X1,1to XM,Nmay be partitioned to access sparse elements transformed from specific dense matrices. In some implementations, the first group of sparse element access units may include a first sparse element access unit and a second sparse element access unit. For example, the first row of the sparse-dense transform unit200may include sparse element access units X1,1and X1,2. In some implementations, the first group of sparse element access units and the second group of sparse element access units may arranged in a two-dimensional mesh configuration. In some implementations, the first group of sparse element access units and the second group of sparse element access units may be arranged in a two-dimensional torus configuration.

The system receives a request for an output matrix based on sparse elements including sparse elements associated with a first dense matrix and the sparse elements associated with a second dense matrix (402). For example, referring toFIG. 2B, a processing unit may execute an instruction requesting the sparse-dense transform unit200for a dense one-dimensional vector generated using sparse elements No. 1 to No. 50 of database table No. 1, sparse elements No. 100 to No. 200 of database table No. 2, and sparse elements No. 9,050 to No. 9,060 of database table No. 1,000.

In some implementations, the first sparse element access unit may receive a request for a plurality of sparse elements including the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix. The first sparse element access unit may transmit the request to the second sparse element access unit. For example, referring toFIG. 2B, after the sparse-dense transform unit200receives the request from the processing unit, the sparse-dense transform unit200may instruct the sparse element access unit X1,1to broadcast a request for the sparse elements to the other sparse element access units in the mesh network. The sparse element access unit X1/1may broadcast a request222to the sparse element access unit X1,2.

The system obtains the sparse elements associated with the first dense matrix fetched by a first group of sparse element access units (404). In some implementations, the first sparse element access unit may determine that an identity of a particular sparse element of the plurality of sparse elements matches with an identity of one of the first subset of the sparse elements associated with the first dense matrix. For example, referring toFIG. 2C, the sparse element access unit X1,1may be configured to access sparse elements No. 1 to No. 200 of database table No. 1. The sparse element access unit X1,1may determine that it is configured to access sparse elements No. 1 to No. 50 of database table No. 1, but it is not configured to access sparse elements No. 100 to No. 200 of database table No. 2 or sparse elements No. 9,050 to No. 9,060 of database table No. 1,000. In response to determining that the identity of the particular sparse element of the plurality of sparse elements matches with the identity of one of the first subset of the sparse elements associated with the first dense matrix, the first sparse element access unit may fetch the first subset of the sparse elements associated with the first dense matrix including the particular sparse element. For example, in response to determining that it is configured to access sparse elements No. 1 to No. 50 of database table No. 1, the sparse element access unit X1,1may fetch sparse elements No. 1 to No. 50 of database table No. 1 from the data shard(s) where these sparse elements are being stored.

The second sparse element access unit may fetch a second, different, subset of the sparse elements associated with the first dense matrix. For example, referring toFIG. 2C, the sparse element access unit X1,2may be configured to access sparse elements No. 51 to No. 200 of database table No. 2. In response to determining that it is configured to access sparse elements No. 100 to No. 200 of database table No. 2, the sparse element access unit X1,2may fetch these sparse elements from the data shard(s) where these sparse elements are being stored.

The system obtains the sparse elements associated with the second dense matrix fetched by a second group of sparse element access units (406). For example, referring toFIG. 2C, the second group sparse element access units may be the M-th row of the M-by-N sparse element access units, where the sparse element access unit XM,Nmay be configured to access sparse elements No. 9,000 to No. 10,000 of database table No. 1,000. In response to determining that it is configured to access sparse elements No. 9,050 to No. 9,060 of database table No. 1,000, the sparse element access unit XM,Nmay fetch these sparse elements from the data shard(s) where these sparse elements are being stored, and generate a dense matrix246based on these sparse elements.

In some implementations, the first sparse element access unit may fetch the first subset of the sparse elements associated with the first dense matrix from a first data shard, and the second sparse element access unit may fetch the second, different, subset of the sparse elements associated with the first dense matrix from a second, different data shard. For example, referring toFIG. 1, the first sparse element access unit may fetch the first subset of the sparse elements associated with the first dense matrix from data shard106a, and the second sparse element access unit may fetch the second, different, subset of the sparse elements associated with the first dense matrix from data shard106b.

The system transforms the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix to generate an output dense matrix that includes the sparse elements associated with the first dense matrix and the sparse elements associated with the second dense matrix (408). For example, referring toFIG. 2C, the sparse-dense transform unit200may transform the dense matrices242,244, and246into a dense matrix for the processor unit.

In some implementations, the sparse elements associated with and first dense matrix and the sparse elements associated with second dense matrix may be multi-dimensional matrices, and the output dense matrix may be a vector. For example, the dense matrix242may have dimensions of 100-by-10, the dense matrix244may have dimensions of 20-by-100, and the dense matrix246may have dimensions of 3-by-3. The sparse-dense transform unit200may transform the dense matrices242,244, and246into a vector with dimensions of 1-by-3009.

FIG. 5is a flow diagram that illustrates an example of a process500for generating a dense matrix. The process500may be performed by a system, such as the sparse-dense transform unit104or the sparse element access unit300.

The system receives an indication for accessing the subset of the particular sparse elements (502). For example, referring toFIG. 3A, the data fetch unit304may be configured to receiving a signal344for fetching one or more requested sparse elements from the data shards330. In some implementations, a request for particular sparse elements that are stored in one or more data shards may be received over a node network. For example, referring toFIG. 3A, the request identification unit302may be configured to receive a request342over a node network320to fetch sparse elements stored in data shards330. The system may determine that the data fetch unit is assigned to handle a subset of the particular sparse elements. For example, the request identification unit302may be configured to determine whether the sparse element access unit300is assigned to access the sparse elements indicated by the request342. In response to determining that the data fetch unit is assigned to handle a subset of the particular sparse elements, the indication may be generated for accessing the subset of the particular sparse elements. For example, if an identification of a particular requested sparse element (e.g., No. 1 of database table No. 1) is included in a lookup table, the request identification unit302may send a signal344to the data fetch unit304to fetch the particular requested sparse element.

The system determines, based on identifications of the subset of the particular sparse elements, a processor designation for fetching the subset of the particular sparse elements (504). For example, referring toFIG. 3A, the data fetch unit304includes one or more processors322a-322k. Each of the processors322a-322kmay be assigned to specific sparse elements based on the identification of the sparse elements, and the data fetch unit304may be configured to generate one or more requests for the processors322a-322kbased on the identification of the sparse elements. In some implementations, the system may determine that the system is assigned to handle the subset of the particular sparse elements comprises determining that the system is assigned to handle a subset of the particular sparse elements based on a lookup table. For example, the data fetch unit304may determine the processor assignment by using a lookup table.

The system fetches, based on the designation and by a first processor of the plurality of processors, a first sparse element of the subset of the particular sparse elements (506). For example, referring toFIG. 3A, the data fetch unit304may instruct the processor322ato fetch a sparse element that is included in the signal344.

The system fetches, based on the designation and by a second processor of the plurality of processors, a second sparse element of the subset of the particular sparse elements (508). For example, referring toFIG. 3A, the data fetch unit304may instruct the processor322bto fetch a different sparse element that is included in the signal344.

In some implementations, a first matrix that includes the first sparse element from the first processor may be received, where the first matrix may have a first dimension. The system may generate a second matrix that includes the first sparse element, the second matrix having a second dimension that is smaller than the first dimension. For example, the sparse reduce unit306may be configured to reduce the dimensions of the fetched sparse elements346. Each of the processors322a-322kmay generate a sparse element having dimensions of 100-by-1. The sparse reduce unit306may receive fetched sparse elements346having dimensions of 100-by-k, and to generate sparse-reduced elements348by reducing the dimensions of the fetched sparse elements346to 100-by-1 by logic operations, arithmetic operations, or a combination of both. The system may generate the output dense matrix, the output dense matrix may be generated based on the second matrix. For example, the concatenation unit308may be configured to rearrange and concatenate the sparse-reduced elements348to generate concatenated elements350.

In some implementations, the first sparse element may be received at a first point of time, and the second sparse element may be received at a second, different, point of time. The system may determine an order of the first sparse element and the second sparse element for the output dense matrix. For example, referring toFIG. 3A, processor322amay return the fetched sparse element No. 10 to the sparse reduce unit306sooner than processor322bthat is configured returns the fetched sparse element No. 5. The concatenation unit308is configured to rearrange the later-received sparse element No. 5 to be ordered before the earlier-received sparse element No. 10, and concatenate sparse elements No. 1 to No. 200 as the concatenated elements350.

The system generates an output dense matrix based on a transformation that is applied to at least the first sparse element and the second sparse element (510). In some implementations, the system may compress the output dense matrix to generate a compressed output dense matrix. The system may provide the compressed output dense matrix to the node network. For example, the compress/decompress unit310may be configured to compress the concatenated elements350to generate a dense matrix352for the node network320.

In some implementations, the system may receive a first dense matrix representing a dense matrix sent over the node network, and generate the output dense matrix based on the first dense matrix, the first sparse element, and the second sparse element. For example, the sparse element access unit300may receive a dense matrix from a neighboring sparse element access unit via the node network320. The sparse element access unit300may decompress the received dense matrix, and may concatenate the decompressed dense matrix with the concatenated elements350to form updated concatenated elements that can be compressed and then output to the node network320.

The processes and logic flows described in this specification can be performed by one or more programmable computers executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array), an ASIC (application specific integrated circuit), or a GPGPU (General purpose graphics processing unit).