Browse Prior Art Database

Sparse Matrix Storage Format for Stream Processing

IP.com Disclosure Number: IPCOM000245939D
Publication Date: 2016-Apr-19
Document File: 3 page(s) / 68K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a Compressed Sparse Row (CSR)-Interlaced or CSRI format, which is a storage format that requires fewer arrays and is thus better suited for stream processing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 01 of 3

Sparse Matrix Storage Format for Stream Processing

compressed format to avoid the storage and transmission overhead of zero elements . Many compression formats are defined for this purpose. The most-used are Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC).

CSR defines three arrays per matrix with the structure shown below. Figure 1 illustrates the nonzero elements of MatrixA(i.e., nonzeros). This matrix is stored by value arrays (a), column index arrays (c) and row index arrays (r). Array r has the same length as a and represents the index of the element in each row. Array cstores the indexes in a that start a new row and thus, its length is equal to the number of rows.

Figure 1: CSR format and its related arrays

In addition, an array for the length of each rowlis sometimes defined to facilitate the implementations.

Storing the sparse matrices in several arrays and in complex data structures creates a challenge for streaming applications , as the accelerator needs to read multiple different addresses from memory , which breaks bursty reads from the memory and cause cache misses as well as long latency in accessing data elements.

To improve performance, the novel solution is a storage format with fewer arrays. Sincerand aare typically used together and have the same length per definition, the novel approach is to store the two in an interlaced format. This allows the hardware to read the arrays one after the other from the subsequent memory address . The same concept is applied to cand l.

1


Page 02 of 3

The new format is referred to as CSR-Interlaced or CSRI. Instead of four, if length array is considered, the proposed format only deals with two arrays. This allows an increased frequency of bursty read operations.

The same idea is applicable to most of the other formats , in order to increase compatibility with stream processing. The proposed format is illustrated below.

Figure 2: CSRI format and its related arrays

This also allows an increased frequency of bursty read operations. Moreover, most stream processing requires read aand rto be able to process the element. This operation happens seamlessly in the proposed format. The disadvantage is that there might be a slight overhead for separating the two arrays in software; however, because the new format is targeted for the accelerators, specifically the associated hardware implementation, there is no associated overhead.

The same idea can be implemented for other compressed formats . In particular, appl...