IEEE Circuits and Systems Magazine - Q3 2023 - 44

obtain the input address for fetching the nonzero data
in the compressed format and to calculate the output
address for writing back the computed result. Different
sparse compression formats have different requirements
in terms of total storage size (including nonzero
data and metadata) and decoding complexity. Here, we
present and discuss some common sparse compression
formats used for sparse neural network processing.
Coordinate List (COO): In the COO format, nonzero
data are stored along with their absolute indices in the
original uncompressed vector or matrix. Fig. 11(a) shows
an example of a matrix with zero and nonzero data. The
COO format of the matrix stores all nonzero data in a
1D value array and records the (row, column) indices of
each nonzero data, as shown in Fig. 11(b). The advantage
of COO is its low decoding complexity, since the
row and column indices can be directly used to locate
the positions of the nonzero data in the uncompressed
vector or matrix. However, the row and column indices
may require significant amount of storage overhead
which makes COO less efficient for data of medium or
low sparsity.
Compressed Sparse Row (CSR): In the CSR format,
nonzero data are stored first by row, then by column in
a 1D value array. Different from COO, the metadata consists
of a pointer (Ptr) array and a column index array.
The Ptr array stores the row-by-row count of the total
number of nonzero data. The first entry Ptr[0] is always
0; the second entry Ptr[1] stores the count of nonzero
data in the first row; and Ptr[2] stores the count of nonzero
data in the first two rows, etc. The column index
array stores the column index of each nonzero data.
Fig. 11(c) shows the CSR format of our matrix example.
The CSR format requires a two-step decoding process.
For instance, to access data in Row 1, the two steps are:
1) obtain the positions of the nonzero data of Row 1
stored in the value array: Ptr[1] Ptr,
,[ ]11+ and so on and
2) obtain the column indices of the nonzero data in Row
1: Index[Ptr[1]], Index[Ptr[1]+1], and so on.
Compressed Sparse Column (CSC): The CSC format
is similar to the CSR format, but nonzero data are
first stored by column, then by row in a 1D value array.
Fig. 11(d) shows the CSC format for our matrix example,
where the Ptr array stores the column-by-column count
of the total number of nonzero data and the row index
array stores the row index of each nonzero data. The
CSC format shares the same advantages and disadvantages
as the CSR format.
Run-Length Coding (RLC): In the RLC format, nonzero
data are stored in a 1D value array in either row
major or column major, and a run array keeps track of
the number of zeros before each nonzero data (known
as the " run length " ). Fig. 11(e) shows the RLC format of
our matrix example using 2-bit run lengths. In this example,
nonzero values a, b, c, and d are stored in the 1D
value array, and they have 1, 3, 0, and 3 preceding zeros
or run lengths, respectively, that are recorded in the
run array. Note that the nonzero data e has four preceding
zeros, which exceeds the two bits allocated to a run
length. Therefore, an additional padding zero is inserted
before e with a run length of 3. The RLC format can be
decoded in one step. The position of i-th nonzero data
in the value array can be calculated by accumulating all
preceding run lengths in the run array.
Figure 11. Examples of sparse compression formats: (a) sparse uncompressed tensor,
(b) COO format, (c) CSR format, (d) CSC format, and (e) RLC format with a run
of 2-bit.
44
IEEE CIRCUITS AND SYSTEMS MAGAZINE
C. Sparse Computation Pipeline
The high-level computation pipeline
of sparse DNN processing in
the compressed format is illustrated
in Fig. 12. Following the computation
pipeline, nonzero data and
metadata arrays of Ws and IAs are
first fetched on-chip for processing.
The compressed W and IA pairs
are then searched, paired and dispatched
to a multiplier array for
computation in the so-called frontend
part of the pipeline. Finally,
the computed psums are accumulated
and written back to their respective
OAs in output buffers in
the so-called backend part of the
pipeline.
The challenges of processing
sparse data are two folds: 1) at the
THIRD QUARTER 2023
IEEE Circuits and Systems Magazine - Q3 2023

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q3 2023
