# Two Sparsities Are Better Than One: Unlocking the Performance Benefits of
Sparse-Sparse Networks

Kevin Hunter, Lawrence Spracklen and Subutai Ahmad
Numenta, Redwood City, CA, USA
{khunter, lspracklen<EMAIL_ADDRESS>
###### Abstract

In principle, sparse neural networks should be significantly more efficient
than traditional dense networks. Neurons in the brain exhibit two types of
sparsity; they are sparsely interconnected and sparsely active. These two
types of sparsity, called weight sparsity and activation sparsity, when
combined, offer the potential to reduce the computational cost of neural
networks by two orders of magnitude. Despite this potential, today’s neural
networks deliver only modest performance benefits using just weight sparsity,
because traditional computing hardware cannot efficiently process sparse
networks. In this article we introduce Complementary Sparsity, a novel
technique that significantly improves the performance of dual sparse networks
on existing hardware. We demonstrate that we can achieve high performance
running weight-sparse networks, and we can multiply those speedups by
incorporating activation sparsity. Using Complementary Sparsity, we show up to
100X improvement in throughput and energy efficiency performing inference on
FPGAs. We analyze scalability and resource tradeoffs for a variety of kernels
typical of commercial convolutional networks such as ResNet-50 and
MobileNetV2. Our results with Complementary Sparsity suggest that weight plus
activation sparsity can be a potent combination for efficiently scaling future
AI models.

> Keywords: DNNs, Sparsity, FPGA, ResNet, CNN, convolutional networks, Deep
> Learning

##  1 Introduction

In recent years, larger and more complex deep neural networks (DNNs) have led
to significant advances in artificial intelligence (AI). However, the
exponential growth of these models threatens forward progress. Training
requires large numbers of GPUs or TPUs, and can take days or even weeks,
resulting in large carbon footprints and spiraling cloud costs [63, 66].

Taking inspiration from neuroscience, sparsity has been proposed as a solution
to this rapid growth in model size. Sparse networks either constrain the
connectivity (weight sparsity) or activity (activation sparsity) of their
neurons, significantly reducing both the size and computational complexity of
the model. Typically, these techniques are applied in isolation to create
sparse-dense networks. However, weight and activation sparsity are
synergistic, and when deployed in combination, the computational savings are
multiplicative. Consequently, sparse-sparse networks have the potential to
reduce the computational complexity of the model by over two-orders of
magnitude. For example, as illustrated in Figure 1, when a network is 90%
weight sparse, only 1 out of every 10 weights is non-zero, facilitating a
10-fold reduction in compute. When a network is 90% activation sparse, only 1
out of every 10 inputs is non-zero, similarly delivering a 10-fold reduction
in compute. When applied in concert, the zero-values interplay, such that on
average only 1 out of every 100 results will be non-zero, delivering a
100-fold savings, if techniques can be developed to efficiently skip fetching,
multiplying and storing zero valued elements.

Figure 1: An illustration of the potential speedups that can be achieved with
sparse networks (compared to their dense equivalents). When weight and
activation sparsity are leveraged simultaneously (a sparse-sparse network),
the benefits are multiplicative, enabling speedups that exceed two orders of
magnitude.

However, with current implementations, the resulting speedups only represent a
small fraction of these theoretical computational savings [20]. The irregular
patterns of neuron interconnections and activity introduced by sparsity have
proved difficult to exploit on modern hardware, which is optimized for the
execution of regular dense data structures. This “impedance mismatch”
significantly erodes the performance of sparse-dense networks and impedes the
implementation of efficient sparse-sparse networks. Hardware platforms with
dedicated logic for exploiting sparsity have begun to appear [58], but the
performance gains remain modest [48].

In this article we discuss Complementary Sparsity, a novel solution that
inverts the sparsity problem. Rather than creating hardware to support
unstructured sparse networks, we illustrate how sparsity can be structured to
match the requirements of the target hardware. We demonstrate that this
solution both creates highly efficient weight-sparse networks, and establishes
viable sparse-sparse networks, yielding large multiplicative benefits.

We investigate the potential of Complementary Sparsity and sparse-sparse
networks on FPGAs, due to their flexible architecture. This flexibility
provides an ideal laboratory for investigating the trade-offs associated with
different implementation approaches, and enables us to refine our
understanding of sparse-sparse resource requirements. The resulting
implementations not only provide a path to highly efficient sparse-sparse
network inference on FPGAs, but also provide insights that can be leveraged as
IP blocks in other architectures or ASICs, or adapted to fit a wide range of
other compute architectures.

In this paper, we make four main contributions:

  1. 1.

We introduce Complementary Sparsity, a novel form of structured sparsity.

  2. 2.

We establish how Complementary Sparsity can enable the construction of
efficient sparse-sparse networks.

  3. 3.

We discuss our sparse-sparse network implementation on a FPGA, demonstrating a
110X speedup over an optimized dense implementation.

  4. 4.

We demonstrate that leveraging activation sparsity reduces the hardware
resource utilization associated with the core components of convolutional
networks.

##  2 Sparsity in the Brain, in Deep Learning, and in Hardware

###  2.1 Sparsity in the Brain

It is well known that neural activity in the brain, specifically the
neocortex, is highly sparse. However, sparsity in the neocortex is
instantiated in multiple different ways. Numerous studies show that only a
small percentage of neurons become active in response to sensory stimuli [3,
73, 6]. On average less than $2\%$ of neurons fire for any given input. This
is true for all sensory modalities as well as areas that deal with language,
abstract thought, planning, etc. Sparsity is also present in neural
connectivity. Cortical pyramidal neurons show highly sparse connectivity to
each other and receive relatively few excitatory inputs from most surrounding
neurons [27]. The density of local area connections is often less than $5\%$
[27]. The brain is incredibly power efficient, a fact that has been directly
linked to both activation sparsity [3, 42] and connection sparsity [56].
Sparsity has also been linked to the brain’s ability to form useful
representations [52, 53], make predictions [24, 68, 47], as well as detect
surprise and anomalies. It seems evident that sparsity is ubiquitous in the
neocortex and fundamental to its efficiency and functionality.

Figure 2: We focus on sparse networks with both sparse connectivity and sparse
activations. Zeroes in the weight matrices enforce sparse connectivity. A
$k$-WTA activation function ensures activations with fixed sparsity.

###  2.2 Sparsity in Deep Learning

The prevalence of sparsity in the brain stands in contrast to standard DNNs
where sparsity is still a research area. DNNs are composed of stacked layers
of linear neurons, with the output of layer N forming the input to layer N+1.
Neurons compute a weighted sum of their inputs, with the weights for the
neurons in each layer typically being expressed as a 2D weight matrix. The
output of a layer can be computed as a simple matrix multiplication; the
inputs to the layer form either an activation vector (in the case of a single
input), or a matrix (when a batch of inputs are being processed). In standard
DNNs both the weight matrices and the activation vectors are dense.

Analogous to the neurology, it is possible to create two forms of sparsity in
DNNs: sparse connections and sparse activations (Figure 2). Absent connections
are represented by 0’s in the weight matrices, while inactive neurons are
represented by 0’s in the inputs to each layer. Recently, there has been an
increase in research focused on creating networks that are both sparse and
accurate. A variety of techniques have been proposed in the literature to
achieve either form of sparsity, as summarized in the following sections. Note
however that, unlike biology, it is rare for DNNs to combine both types of
sparsity in the same network.

####  2.2.1 Weight Sparsity

In contemporary dense networks, neurons are fully connected, with each neuron
in a layer receiving input from each and every neuron in the previous layer.
Research has shown that many DNNs are heavily overparameterized, and sparsity
can be successfully applied to these networks [41, 12]. This technique of
limiting neuron interconnectivity is referred to as _weight sparsity_.

In weight-sparse networks, each neuron is only connected to a subset of the
neurons in the prior layer. As the sparsity of the weight matrices is
increased the overall accuracy can drop. However, a variety of techniques have
been developed to create networks that are both sparse and accurate [26]. Most
research has focused on the creation of: a) sparse models by direct training;
or, b) sparse models from existing dense networks by removing (or ‘pruning’)
the least important weights [26]. Within these two broad approaches exist a
variety of different techniques, with varying degrees of sophistication and
dynamism. Most simplistic are single-shot pruning algorithms [26], that remove
all of the weights necessary to achieve the desired sparsity in one event.
Iterative algorithms gradually increase the sparsity over the span of a number
of steps until the desired sparsity is achieved [26]. In addition to
undertaking iterative pruning, algorithms can iteratively grow connections,
working to ensure that the optimal set of interconnections is retained [17].

Pruning techniques primarily focused on reducing computational overheads are
also in use [49, 17]. Different levels of sparsity in each layer allows
sparsity to be focused in components of the model to deliver the most
significant speedups, while smaller layers that only contribute minimally to
the overall computational costs and parameter counts are protected. Novel
pruning techniques and sparsity patterns that are tailored to hardware
requirements have also focused on convolutional layers, where the multiplicity
of channels provides opportunity for a variety of hardware friendly sparsity
patterns [9].

Figure 3: An illustration illustrating the simplification of matrix
multiplication operations when both activations and weights are sparse. It is
only necessary to compute a product if it contains a non-zero element in both
the input activation _and_ the weight matrix.

####  2.2.2 Activation Sparsity

In DNNs the outputs (activations) of each layer are generally dense, with
between $50\%$ to $100\%$ of the neurons having non-zero activations. While
less commonly discussed, activation sparsity can also be applied to DNNs [45,
1, 39, 55]. For activation sparsity, the determination of neurons to activate
is typically performed by either explicitly selecting the top-k activations
(frequently termed $k$-Winner-Take-All ($k$-WTA)) [45, 1] or by computing
dataset specific activation thresholds for the neurons that, on average,
reduce the number of activated neurons to the desired level [39]. It is also
possible to reduce the overall magnitudes of activations by introducing
appropriate regularizers that penalize large values [52, 41].

In this article we focus on networks using $k$-WTA [43, 14] (Figure 2). In
these networks the ReLU activation function is replaced by an activation
function where the output of each layer is constrained such that only the $K$
most active neurons are allowed to be non-zero [45, 1]. Whereas ReLU allows
all activations above $0$ to propagate, $k$-WTA allows exactly the top $K$
activations to propagate. $k$-WTA thus provides the ability to precisely
control the percentage of active neurons by setting $k$ appropriately.
Typically $K$ is much smaller than the number of neurons in that layer. A
detailed description of the activation function and results on several
datasets can be found in [1].

###  2.3 Sparse DNNs in Hardware

####  2.3.1 Theoretical Performance Benefits of Sparsity

Sparse models provide a variety of potential benefits compared to traditional
dense models, including model compression and computational efficiency. In
weight-sparse networks, each absent connection is represented by a zero-valued
element in the weight matrix, which in turn translates into a reduction in the
number of multiply-accumulate (MAC) operations required for matrix
multiplication. Accordingly, the theoretical computational savings associated
with weight sparsity are directly proportional to the degree of weight
sparsity.

Activation sparsity can also deliver significant computational savings. When
an incoming activation is zero valued, its contributions to all of the
neurons’ weighted sums will also be zero, allowing the computations of these
sub-products to be skipped. Similar to the computational savings associated
with weight sparsity, the computational savings from activation sparsity are
directly proportional to the degree of activation sparsity.

Activation and weight sparsity can be applied to DNNs independently or in
combination. With both forms of sparsity independently reducing the number of
MAC operations required, exploiting both forms of sparsity has the potential
to yield significant computational savings (Figure 1). MAC operations can be
eliminated if either the corresponding input or the corresponding weight is
zero (Figure 3). These savings can be realized if the underlying hardware is
capable of efficiently performing operations on these sparse matrices.

In practice it has proved extremely difficult to realize these performance
benefits on current hardware architectures. Even for DNNs with high-degrees of
weight sparsity, the performance gains observed are small. For example, on
CPUs, even for weight sparse networks in which 95% of the neuron weights have
been eliminated, the performance improvements observed are typically less than
4X [51]. In addition, there are almost no techniques that simultaneously
exploit both weight and activation sparsity. In part due to these
difficulties, sparse networks have not been widely deployed in commercial
settings.

Figure 4: The Compressed Sparse Row (CSR) format for representing sparse
matrices provides a compact representation, but requires index arrays to
interpret the data.

####  2.3.2 Challenges of Accelerating Sparse Matrices

Modern hardware architectures thrive on processing dense, regular data
structures. Dense DNNs are perfectly suited to these architectures; their
regular-dense matrix operations are painstakingly optimized for peak
performance on every conceivable hardware platform.

For sparse models, performance gains are possible if the underlying hardware
is capable of efficiently performing sparse matrix operations, skipping the
unnecessary computations associated with the zero valued elements. The
efficient rendezvous of non-zero weights with non-zero activations ensures the
minimum number of operations, enabling sparse-sparse networks to reduce
computations and the attendant power consumption.

Connections between neurons in sparse networks are ideally determined to
maximize the accuracy of the network. As such, there is typically no regular
pattern to these connections. Similarly, the locations of the non-zero
activations will likely display no regular pattern, and will change
constantly. The resulting irregular patterns of non-zero elements in the
weight and activation matrices present challenges to efficiently exploiting
sparsity on today’s hardware architectures.

Sparse matrices are often represented in a compressed form, where only the
non-zero elements are retained, along with sufficient indexing information to
locate the elements within the matrix, as illustrated in Figure 4, or are
highly structured (such as the Band matrices and Block Diagonal Matrices [74].
These are often found in the context of High Performance Computing (HPC)
software packages [5]. However, given the overheads associated with explicitly
storing and retrieving data in these compressed formats, such approaches are
mainly practical for highly sparse matrices, 99% or greater.

In DNNs, significant overheads are introduced by the indirection required by
the indexing. For each non-zero element in the sparse matrix, its location in
memory must be determined by consulting the index before a corresponding
element in the other matrix is loaded. In addition, the irregular nature of
sparse matrices in DNNs removes many locality benefits (limiting the benefits
from data caches and vector engines). Adjacent elements in the sparse weight
matrix no longer necessarily interact with adjacent elements in the activation
matrix, requiring serial processing or costly scatter-gather operations.

####  2.3.3 Structured Sparsity

These problems with sparse matrices have been long recognized, and techniques
have been developed to increase locality and amortize the overheads associated
with the indices. These techniques constrain the locations at which non-zero
elements can appear in the sparse matrices. There are two techniques commonly
used to introduce structure and make sparsity more hardware friendly:

  * •

Partitioned Sparsity: the matrices are divided into N partitions, and
conditions are placed upon the locations and number of non-zero elements in
each partition [82, 85, 21].

  * •

Block Sparsity: Non-zero elements are forced to occur in blocks (typically
square or rectangular). The indexing overhead is now amortized over the
processing of all of the elements in the block, and a degree of locality is
restored [8].

Figure 5: Examples of 75% sparse matrices (a) illustrates unstructured
sparsity in a matrix; non-zero elements are shaded, (b) illustrates block
sparsity, with non-zero elements constrained to appear in 4-element blocks
along a row, (c) illustrates partitioned sparsity, where each row is
considered a partition and is forced to contain the same number of non-zero
elements, while (d) applies both constraints.

These techniques can be applied independently or in combination, with
partitioning constraints imposed on the locations of the non-zero blocks, as
illustrated in Figure 5. Imposing these constraints can provide significant
performance benefits, as illustrated in Figure 6a and 6b. In these figures the
performance of sparse matrix multiplication (1024$\times$1024 matrix)
operations is shown on a modern CPU processor using the highly tuned Intel
OneAPI math libraries [29]. It is apparent that imposing structure on the non-
zero locations improves performance: for unstructured 96% sparse matrices,
sparse-dense multiplications are accelerated by around 2X, while no
performance benefit is observed for spare-sparse multiplication. In contrast,
when block sparse constraints are introduced, we achieve an almost 6X
improvement for sparse-sparse operations. However, given that the sparse
matrices are 96% sparse, the theoretical computational savings associated with
a sparse-dense operation is 25X, and 625X for the sparse-sparse operation,
dwarfing the actual performance gains realized. It is also important to note
that until a high degree of sparsity is obtained, matrix computations using
the OneAPI sparse methods actually observed a slowdown, clearly demonstrating
the challenges posed by sparse matrices on current hardware. Similar results
are reported on GPUs using block sparse techniques [81].

Imposing structure on the locations of the non-zero elements places
limitations on the assignment of connected neurons and active neurons. There
has been significant research into whether the imposition of these constraints
degrades the achievable accuracy or peak sparsity. As might be expected, the
impact is dictated by the severity of the constraints. If the partitions are
too small, or the blocks too large, accuracy becomes degraded to an
unacceptable extent [40].

Significant research has been invested in developing software optimization
techniques to maximize the performance achievable with existing sparsity
patterns [23, 71]. However, while partitioned and block sparsity techniques
have been partially successful in delivering the performance benefits of
sparse DNNs on current hardware, these sparse techniques fall far short of
their theoretical potential.

####  2.3.4 Additional Challenges For Activation Sparsity

Further to the costs of actually performing the sparse matrix multiplications,
there are overheads associated with first determining which elements should be
non-zero. During inference, the neuron weights are static, allowing the non-
zero elements and resulting compressed representations to be computed offline.
In contrast, for sparse activations, the non-zero elements are input
dependent, and must be repeatedly recomputed during inference. Once the non-
zero elements have been determined, there is an overhead for generating an
appropriate representation of the sparse activations. For $k$-WTA, determining
the winning elements involves performing a computationally costly sort
operation, although partitioning or blocking schemes can be used to reduce the
overheads. These overheads are not incurred when activations are dense, and
represent a significant obstacle to achieving speedups from activation
sparsity.

(a) Sparse-Dense Matrix Computation

(b) Sparse-Sparse Matrix Computation

Figure 6: Performance improvements from OneAPI sparse matrix routines for both
CSR and BSR (Block Compressed Row Format). The study was performed on an
8-core, AVX-512 capable processor (1024$\times$1024 matrix, with block size =
8$\times$8).

##  3 Complementary Sparsity

Directly processing a native representation of a sparse matrix is inefficient
because of the presence of the zero-valued elements. Block and partitioned
sparsity help align the patterns of non-zero elements with hardware
requirements, but are fundamentally at odds with creating highly sparse and
accurate networks. Optimal performance requires large blocks and reduced
partition sizes but this limits both the obtainable sparsity and the accuracy
[40]. This in turn compromises the approaches from achieving the theoretical
performance benefits of highly sparse networks.

We propose an alternate approach that inverts the sparsity problem by
structuring sparse matrices such that they are almost indistinguishable from
dense matrices. We achieve this by overlaying multiple sparse matrices to form
a single dense structure. An optimal packing can be readily achieved if no two
sparse matrices contain a non-zero element at precisely the same location.
Given incoming activations, we can perform an element-wise product with the
incoming activations (a dense operation) and then recreate each individual
sum.

We term this technique _Complementary Sparsity_. Complementary Sparsity
introduces constraints upon the locations of non-zero elements but it does not
dictate the relative positions of the non-zero elements, nor does it dictate
the permissible sparsity levels. The technique can be applied to convolutional
kernels by overlaying multiple 2D sparse matrices from a layer’s 3D sparse
weight tensor. Importantly, the technique provides a path to linear
performance improvements as the number of non-zero elements decreases, even
for very high levels of sparsity.

Figure 7(a) illustrates the use of Complementary Sparsity for convolutional
kernels. In this example, each kernel is 80% sparse, and a set of 5 kernels
with non-overlapping patterns is overlaid to form a single dense kernel. The
number of sparse kernels that can be combined is directly proportional to
their sparsity. The primary constraint is that the non-zero elements in each
set should not collide with each other. Note that it is not necessary that all
the weights in a layer are non-overlapping - the restriction applies only to
each set being combined. Using our 80% example, if a convolutional layer
contains 20 channels, there are 4 dense sets each containing 5 sparse kernels.
The elements must be complementary within a set, but there are no restrictions
across the 4 sets. In addition, sets of convolutional kernels can be overlaid
in either the filter or channel dimensions. Given this flexibility, in
practice we have found that networks trained with the restrictions imposed by
Complementary Sparsity do not compromise on accuracy when compared with
unstructured sparsity.

Another important advantage of Complementary Sparsity is that it provides a
path to facilitate both sparse weights and sparse activations. In the
following subsections, we first describe the architecture of sparse-dense
networks (i.e. networks with sparse weights and dense activations) and then
describe the extension to sparse-sparse networks. Finally, we describe how
these concepts can be implemented in an FPGA.

###  3.1 Complementary Sparsity and Sparse-Dense Networks

The basic technique described above combines multiple sparse weight structures
into a single dense entity, and natively supports sparse-dense networks, i.e.
networks with dense activations and sparse weights. Partial results from each
sparse entity must be kept separate and independently accumulated for final
results. In sparse-dense networks processing is comprised of four distinct
steps (Figure 7b):

  1. 1.

Combine: multiple sparse weight structures are overlaid to form a single dense
entity. This is done offline as a preprocessing step.

  2. 2.

Multiply: each element of the activation is multiplied by the corresponding
weight elements in the dense entity (Hadamard product).

  3. 3.

Route: the appropriate element-wise products are routed separately for each
output.

  4. 4.

Sum: routed products are aggregated and summed to form a separate result for
each sparse entity.

The optimal techniques for implementing each component are dictated by the
specifics of the target hardware. For example, in some cases, instead of
routing the element-wise products, it may prove preferential to reorder the
incoming activations.

Given that Complementary Sparsity reduces $N$ sparse convolutions into a
single dense operation, there is the potential for a linear $N$-fold
performance improvement. The key challenge is to reduce the cost associated
with routing and accumulating the packed results. Accordingly, of particular
interest are techniques focused on minimizing the overheads associated with
the routing of the Hadamard sub-products. Implementation of arbitrary routing
usually involves resource hungry crossbar modules, where footprint increases
as the square of the number of inputs. However, for DNN inference operations,
the locations of the non-zero elements have been determined during training,
and remain static throughout inference. The required routing is both fixed and
predetermined, ensuring efficiency by tailoring implementations to the
specific requirements of the network.

Figure 7: (a) 80% Complementary Sparsity packs 5 sparse convolutional kernels
into a single kernel for processing, (b) Complementary Sparsity applied in the
filter dimension for 3x3 convolutional kernels. With 66% sparsity, 3 sparse
kernels are combined into a single dense kernel for processing.

To further minimize the overheads associated with the routing of the sub-
products, Complementary Sparsity can be combined with the other forms of
structural sparsity. For example, in Figure 7a, each column in the kernel is a
partition, with one non-zero element permitted per column. Similarly,
complementary patterns with blocks of non-zero elements are possible, as shown
in Figure 5. Section 3.3.2 below describes our FPGA implementation of routing
in more detail, and Section 5 analyzes resource tradeoffs.

###  3.2 Complementary Sparsity and Sparse-Sparse Networks

The above sparse-dense Complementary Sparsity technique can be extended to
handle sparse-sparse networks, i.e. networks comprised of both sparse
activations and sparse weights. As discussed in Section 2.3, significant
inefficiencies are traditionally associated with sparse-sparse matrix
computations due to the changing locations of non-zero elements in the
activation vectors. For optimal performance, these non-zero activations must
be paired with the respective non-zero weights. The overheads associated with
dynamically interpreting the sparse representations, and then ensuring they
rendezvous with the appropriate sparse non-zero weights severely degrades any
performance gains associated with processing the sparse subset of elements.

Using Complementary Sparsity, the sparse-sparse problem is simplified to a
problem with sparse activations and dense weights. Since the weights are
dense, the above overheads are eliminated. As illustrated in Figure 8a, when
the sparse weights are represented in a dense format, the incoming sparse
activations are paired with the relevant weights. For each non-zero activation
there exists a corresponding column of non-zero weight elements at a
predefined location in the dense weight structure. Processing is comprised of
the following five steps:

  1. 1.

Combine: multiple sparse weight structures are overlaid to form a single dense
structure. This is done offline as a preprocessing step.

  2. 2.

Select: a $k$-WTA component is used to determine the top-$k$ activations and
their indices.

  3. 3.

Multiply: each non-zero activation is multiplied by the corresponding weight
elements in the dense structure.

  4. 4.

Route: the appropriate element-wise products are routed separately for each
output.

  5. 5.

Sum: routed products are aggregated and summed to form a separate result for
each sparse matrix.

Compared to sparse-dense, the extensions are in the second and third steps.
This formulation directly takes advantage of sparse activations. The
computation in the third step is reduced in proportion to the sparsity of the
incoming activations. As with the sparse-dense case, a key issue is the
additional overhead imposed by routing. For sparse-sparse there is also
additional overhead imposed by the $k$-WTA block. An efficient implementation
of these components is critical to realizing an overall benefit, and are
detailed below in Sections 3.3.2 and 3.3.3.

(a)

(b)

Figure 8: (a) With Complementary Sparsity, sparse weight tensors are
represented as simple dense tensors, simplifying the addition of activation
sparsity, (b) An illustration of the Sparse-Sparse weight tensor structure, C
is the number of channels, W is the width of the kernel, N is the number of
non-zero weights per kernel, BW is the bit width of the weight values, K is
the number of activations processed in parallel, and BID is the bit width of
the Kernel ID.

###  3.3 Complementary Sparsity on FPGAs

In this section, we discuss our implementation of Complementary Sparsity on
FPGAs, before presenting both performance and resource utilization results in
Sections 4 and 5. We focus our discussion on the sparse-sparse implementation
of convolutional kernels, specifically the individual components of Figure 8a.
The implementations are focused on inference operations, and assume the use of
fixed-point arithmetic. As discussed, the flexible architecture of FPGAs
represents a model platform for exploring idealized circuit structures for
Complementary Sparsity.

####  3.3.1 Sparse-Sparse Hadamard Product Computation

For each non-zero activation the relevant weights must be extracted from the
weight tensor, and then individually multiplied by the activation (Hadamard
product, third step in Section 3.2), before being passed to the next stage for
routing. The sparse filter kernels, once converted into a set of dense
kernels, are retained in a series of memories on the FPGA. As illustrated in
Figure 8a, the indices associated with the non-zero elements of an incoming
sparse activation are used to directly extract the relevant elements from the
weight tensor. For each non-zero activation value, we chose to retrieve all
relevant weights in the weight tensor in parallel. Associated with each weight
is a Kernel ID (identifying the channel index in the output tensor) that is
subsequently used to route the resulting sub-product. The Kernel ID index is
determined a priori, and is attached to the corresponding weight value,
forming an augmented tensor.

Processing the incoming activation tensor in parallel delivers the greatest
convolution throughput. However, this parallelism comes at a cost, requiring
parallel accesses to the augmented weight tensor. Assuming $K$ non-zero
activation values, and, given that the indices of each value are dynamic, a
$K$-ported weight tensor memory is required to retrieve each set of weights in
parallel, as illustrated in Figure 8b. The figure demonstrates that each port
must also be sufficiently wide to handle the multiplicity of kernels
associated with an activation index.

Note that, as activation sparsity is increased, the number of ports required
decreases. Similarly, the higher the weight sparsity, the smaller the port
size for each of those memories. Both requirements are approximately
proportional to the degree of sparsity. In Figure 8b, the factor $N$
associated with the port width is the number of dense complementary filter
weight vectors that must be accessed in parallel.

(a)

(b)

Figure 9: Sparse-Sparse sub-product routing: (a) Sub-products serially routed
to the appropriate accumulator, (b) Sub-products routed in parallel to the
appropriate adder-tree.

####  3.3.2 Sparse-Sparse Hadamard Product Routing

A second critical component is the efficient routing of the sub-products from
the Hadamard operation. Once an activation has been multiplied by the
retrieved weights, to complete the computation of the convolution, each
resulting sub-product must be combined with the other sub-products from the
same kernel. The relevant products are identified using their Kernel ID tag.

For $K$ non-zero activation vectors, the retrieved weights may belong to a
single filter kernel (identical Kernel IDs), or might be distributed across
several filter kernels. Each of the $K$ activations can be processed serially,
in which case the results for each of the products can be simply routed via a
multiplexor network to an accumulator, based upon its Kernel ID. This is
diagrammed in Figure 9a.

For greater performance, the products from all the activations can be
processed in parallel. In this case, the resulting sub-products must be routed
to an adder tree for summing, rather than to a single accumulator (Figure 9b).
Routing of multiple addends to non-conflicting locations in an adder tree
introduces additional complexity. Not only is it necessary to route based upon
the Kernel ID, but additional destination address bits are required to
designate the slot of the adder in which the product should land. This is
resolved with an arbitration module, which supplies these additional address
bits before the product is passed to a larger multiplexor network. The
arbitration module generates the low order address bits from the set of Kernel
IDs, using a prefix sum algorithm. Each occurrence of a product with the same
Kernel ID increments the value of the lower order bits, ensuring they are
assigned to a non-conflicting slot in the adder tree for that kernel.
Partitioning reduces the size of these indices since we only need sufficient
bits to identify their position within the partition, not within the entire
activation or output tensor.

####  3.3.3 Activation sparsity using k-WTA

For $k$-WTA, activation sparsity is induced by explicitly restricting the
number of non-zero elements to the $K$ largest values produced by a layer.
Determining these top $K$ values efficiently can represent a significant
obstacle to the effective use of activation sparsity. The time and resources
expended performing the sort operation erodes the performance benefits
associated with leveraging the resulting sparsity in subsequent processing.
Accordingly, an optimized $k$-WTA implementation is central to our FPGA
implementation.

Figure 10: Parallel Global $k$-WTA: performs a histogram based search of
entire activation tp determine the threshold yielding K non-zero elements. In
this example, the 1500-element activation is stored as 300 5-element blocks in
memory AMem. Each block is read out and the element values are used to address
and increment counts in 5 separate memories, A-E. The counts are then
cumulatively summed together into variable Accum, starting with the largest
value location, until Accum reaches a total count of K, establishing a
thresholding value. Values in AMem are then compared to Thresh, and sent
through to the next layer if they are greater than or equal to Thresh, along
with their indices in the original 1500 element vector.

We divide $k$-WTA implementations into two broad categories:

  * •

Global: All elements of an activation are examined to determine the $K$
largest. We use global $k$-WTA following linear layers.

  * •

Local: The activation is partitioned into smaller units, and only the elements
belonging to a partition are compared to each other. We use local $k$-WTA
following convolutional layers, where the winner take all competition happens
along the channel dimension.

For 8-bit activation values, our implementation of global $k$-WTA leverages a
histogram-based approach. In our implementation, a 256-element array in memory
is used to build the histogram, with each activation value being used to
increment a count at a location addressed by that value. Once all of the
activation values have been processed, the histogram array represents the
distribution of the activation values. For a specified value of $K$, the
histogram values can be read, largest first, to determine the appropriate
minimum value cutoff; values above this threshold should be retained as part
of the top-$k$ and the remainder discarded. As a final step, the activation
values are compared against the threshold and the winners passed to the next
layer.

For improved performance, an implementation may process multiple activation
elements in parallel. In this scenario, multiple histograms are built in
parallel and then combined to determine the overall cutoff value. An example
of this implementation is illustrated in Figure 10, for 1500-activations,
5-way parallelism, and activation sparsity of 85%.

Figure 11: Structure of $k$-WTA when serially processing Complementary Sparse
Convolutions.

For convolutional layers, activations have a natural partitioning in the
channel dimension. When the top-$k$ operation in $k$-WTA is implemented as a
sorting operation, which is $O(N*log(N))$ either in time or hardware
resources, partitioning provides significant efficiency benefits. The position
of each result value produced by the convolutional layer must be tracked
through the sorting process. This is achieved by appending an index to each
data value entering the sorting function.

Sorting is performed in several stages, and the implementation is optimized
based on the key observation that it is only necessary to find the top $K$
values in each vector. The ordering of the low valued elements is immaterial,
and, as $K$ decreases with increasing activation sparsity, we ensure that the
cost of sorting implementation falls accordingly. First, each vector is
subdivided into $M$ sub-vectors, and each sub-vector is sent through a sorting
network. The sorted sub-vector is subsequently loaded into one of $M$ FIFOs,
with each sub-vector’s largest value at the front of its FIFO.

A vector composed from the $M$ top-of-FIFO values is then passed through a
$log_{2}(M)$ stage comparator tree, in order to determine the maximum value in
the vector. The maximum value is retained, and its associated indexing
information (which indicates in which FIFO the value was located) is used to
pop that element from the appropriate FIFO, exposing the FIFO’s next largest
element. This process is repeated $K$ times; at which point the output vector
has been filled with the top $K$ elements and is passed to the next processing
layer. In our implementation, a 64-element vector is subdivided into eight
8-element sub-vectors. The sorting network is comprised of 19 comparators,
arranged into depth 6 layers. There are 8 FIFOs, and a 3-level comparator tree
is used to determine the maximum value in the 8-element top-of-FIFO vector.

To prevent bottlenecks, the performance of the $k$-WTA implementation should
be matched to the performance of the convolutional operator. The incoming
results can either arrive in serial bursts or as complete result vectors. A
$k$-WTA implementation could wait until all bursts have been concatenated and
a complete activation result is available, or take advantage of the burst
intervals and combinationally sort [37] the burst values before loading it
into one of the FIFOs. The serial burst implementation is illustrated in
Figure 11. Alternatively, all the activation results could be computed in
parallel, partitioned into $M$ groups, and pushed through $M$ instances of a
combinational sort before being loaded in parallel to the $M$ FIFOs, as
illustrated in Figure 12.

Figure 12: Structure of $k$-WTA when parallel processing Complementary Sparse
Convolutions.

In summary, there are a number of ways to implement $k$-WTA efficiently. By
choosing appropriately we find that overall the $k$-WTA is a relatively small
percentage of overall resource usage (see Section 5.3).

##  4 Results on an End to End Speech Network

In this section we discuss the application of Complementary Sparsity to an end
to end speech recognition system. We trained a convolutional network [57] to
recognize one-word speech commands using the Google Speech Commands (GSC)
dataset [72]. We implemented dense and sparse versions of the network on both
large and small FPGA platforms. Our goal was to study the impact of
Complementary Sparsity on full system throughput (the number of words
processed per second) and understand trade-offs in resources, memory
consumption and energy usage.

GSC consists of 65,000 one-second long utterances of keywords spoken by
thousands of individuals. The task, to recognize the spoken word from the
audio signal, is designed for embedded smart home applications that respond to
speech commands. State of the art convolutional networks on this dataset
achieve accuracies (before quantization) of 96-97% using $10$ categories [60,
64].

Our base dense GSC network is a standard convolutional network composed of two
convolutional layers, a linear hidden layer plus an output layer, as described
in Table 1. We also trained a sparse network with identical layer sizes but
with both sparse weights and sparse activations. Our sparse network follows
the structure and training described in [1]. To enforce sparse weights we used
a static binary mask that dictates the locations of the non-zero elements and
meets requirements of Complementary Sparsity. The ReLU activation function was
replaced by a ($k$-WTA) [44, 1] activation function (see Section 2.2.2 and
Figure 2).

The baseline dense version of the network contained 2,522,128 parameters,
while the sparse network contained 127,696 non-zero weights, or about 95%
sparse. The activations in the sparse network range from 88% to 90% sparsity
(i.e. 10-12% of the neurons are ‘winners’), depending on the layer. Both dense
and sparse models were trained on the GSC data set, achieving comparable
accuracies (see [1] for details). In our implementation, the accuracies of the
sparse and dense networks are between 96.4% and 96.9%. Both activations and
weights are quantized to 8-bits.

Table 1: Architecture of the CNN network trained on GSC data Layer | Channels | Kernel Size | Stride | Output Shape
---|---|---|---|---
Input | - | - | - | 32$\times$32$\times$1
Conv-1 | 64 | 5$\times$5$\times$1 | 1 | 28$\times$28$\times$64
MaxPool-1 | - | 2$\times$2$\times$1 | 2 | 14$\times$14$\times$64
Conv-2 | 64 | 5$\times$5$\times$64 | 1 | 10$\times$10$\times$64
MaxPool-2 | - | 2$\times$2$\times$1 | 2 | 5$\times$5$\times$64
Flatten | - | - | - | 1600$\times$1
Linear-1 | 1500 | 1600$\times$1 | - | 1500$\times$1
Output | 12 | 1500$\times$1 | - | 12$\times$1

###  4.1 FPGA Implementation

We implemented the baseline dense GSC network using the XilinxTM software
“Vitis AI” [79]. Vitis AI is the preferred solution for deploying deep
learning networks on Xilinx FPGA platforms. Convolution and linear layers in
Vitis AI invoke hand-optimized Processing Elements (PE) implemented using RTL.
A software compiler converts a given network, including parameters and
weights, into schedules of calls to these PEs.

We implemented our sparse GSC networks using the Xilinx Vivado HLS toolset
[77, 76]. Although HLS uses a C++ compiler (with Xilinx specific pragmas) and
does not produce hand-optimized designs, it represents a faster design path.
There was sufficient flexibility in the toolset to implement our sparse
designs. We note however that the results for our sparse networks below would
likely be improved using hand-optimized designs.

We created two pipelined implementations of our sparse network using HLS. The
_Sparse-Dense_ implementation leveraged weight sparsity in Conv-2 and the
linear layer, ignoring sparse activations. The _Sparse-Sparse_ implementation
leveraged both sparse activations and sparse weights (as described in Section
3.3). In the Sparse-Dense implementation, the Conv-1 layer was left as fully
dense as its profile was small relative to the other pipeline stages. In the
Sparse-Sparse implementation the other stages became faster and Conv-1 became
a bottleneck. As such we implemented Conv-1 using a sparse-dense strategy (the
input to the network is dense, hence sparse-sparse is not an option for
Conv-1).

###  4.2 Benchmark Description

The performance of the 3 different CNN implementations were tested on two
different Xilinx FPGA platforms. The first, the Alveo U250 [78], is a high-end
card targeted at data centers, while the second, the UtraScale ZU3EG [80], is
a smaller system targeted at embedded applications. Compared to the ZU3EG, the
U250 has 11X the number of system logic cells, about 56X the internal memory,
and consumes 9X more power.

For each CNN network on each FPGA two different experiments were undertaken:

  1. 1.

Single network performance: a single network is a pipelined implementation of
one GSC network, processing a single stream of speech commands.

  2. 2.

Full chip performance: multiple network instances are placed on the FPGA until
the entire FPGA’s resources are exhausted, or the design cannot be routed by
the software. Multiple input streams are distributed across the instances, and
the inference throughput delivered by the entire chip is reported.

In both experiments, the input data is a repeating sequence of 50,000 pre-
processed audio samples. We chose overall throughput, measured as the total
number of input words processed per second, as the primary performance metric.

###  4.3 Single Network Results

Table 2 shows the results of running a single network instance on the U250 and
ZU3EG platforms. On the U250, the Sparse-Dense implementation achieves over
11.7X the throughput of the dense implementation, while the Sparse-Sparse
implementation outperforms both the dense and the Sparse-Dense implementations
by 33.6X and 2.8X respectively (Figures 13a and 13b).

The dense implementation did not fit on the smaller ZU3EG platform due to the
limited resources available. Both sparse implementations were able to compile
and run successfully on the platform due to their smaller size and lower
resource requirements. The Sparse-Sparse implementation was about 2.1X faster
than the Sparse-Dense implementation. Interestingly, the Sparse-Dense
implementation on the ZU3EG platform was still 6.9X faster than the dense
implementation on the more powerful U250. This demonstrates the performance
benefits associated with sparse networks, and also the potential for sparse
networks to open up new applications in embedded scenarios that were
previously impossible.

Table 2: Throughput of single sparse and dense networks on the U250 and ZU3EG platforms, measured in words processed per second. The dense network did not fit on the ZU3EG due to its limited resources. All sparse implementations, regardless of platform, were significantly faster than the dense network running on the U250. The Sparse-Sparse implementation was consistently 2X to 3X faster than the Sparse-Dense implementation. FPGA Platform | Network Implementation | Throughput | Speedup
---|---|---|---
| Dense | 3049 | 1.0
U250 | Sparse-Dense | 35,714 | 11.71
| Sparse-Sparse | 102,564 | 33.63
| Dense | 0 | -
ZU3EG | Sparse-Dense | 21,053 | N/A
| Sparse-Sparse | 45,455 | N/A

###  4.4 Full Chip Results

Table 3 shows the full-chip throughput results for the U250. The numbers
illustrate the performance benefits of sparse networks. In the experiments on
the U250, the Sparse-Dense and Sparse-Sparse implementations outperformed the
dense implementation by 56.5X and 112.3X respectively (Figure 13a). The
increased performance delta between the dense and sparse implementations can
be attributed to the relative compactness of sparsity allowing significantly
more sparse networks to be accommodated on the chip (e.g. 20 Sparse-Sparse
networks versus 4 dense networks). This results in the observed increase in
aggregate throughput. Only one copy of each sparse network could fit on the
ZU3EG, thus overall throughput on this platform was identical to that in Table
2.

Note that the 20X replication count achieved for the Sparse-Sparse
implementation is lower than the 24X replication achieved for the Sparse-
Dense. The added complexity of handling sparse activation indices (see Section
3.3.2) increases the FPGA resources required to support the network.
Nevertheless, the additional performance benefits associated with exploiting
activation sparsity more than outweigh the resource costs, almost doubling the
aggregate throughput.

Table 3: Full-Chip throughput of sparse and dense networks on the U250, measured in words processed per second. The relatively compact footprint of the sparse networks allowed the compiler to fit a larger number of networks per chip. The Sparse-Sparse implementation was over 100X faster than the Dense implementation. FPGA Platform | Network Implementation | Total Networks | Throughput | Speedup
---|---|---|---|---
| Dense | 4 | 12,195 | 1.0
U250 | Sparse-Dense | 24 | 689655 | 56.5
| Sparse-Sparse | 20 | 1,369,863 | 112.3

(a)

(b)

(c)

(d)

Figure 13: Performance comparisons between sparse and dense networks: (a)
Sparse network performance on the U250 relative to dense, (b) Sparse-Sparse
network performance, relative to Sparse-Dense, on the U250, (c) Sparse-Dense
network performance on CPUs using common inference runtimes (relative to a
dense network on the same runtime), (d) Sparse network performance on CPUs and
FPGAs.

###  4.5 Comparisons with CPU Inference Engines

In this section we report performance gains of our sparse GSC network on a
variety of widely available inference runtimes. The CPU in these experiments
is a 3.0GHz 24-core Intel Xeon 8275CL processor. Figure 13c demonstrates the
speedup of the sparse-dense network on these runtimes (relative to the dense
network on the same engine) observed for our GSC CNN network. Most strikingly,
both the well-known ONNX Runtime [54] and OpenVino [30] runtimes fail to
exploit sparsity. For the other runtime engines the sparse networks outperform
the dense network, with Neural Magic’s Deepsparse [50] and the Apache TVM
providing a 2X and 3X speedup, respectively. The observed performance gains
are relatively modest, considering there is a 20X reduction in the number of
non-zero weights.

In Figure 13d, the absolute performance for the sparse networks on the CPU and
FPGA are compared. The results show significant speedups from sparsity on an
FPGA with absolute performance over 10X that currently achievable on a CPU
system. None of these runtime engines exploit both sparsity in activations and
weights.

###  4.6 Power Efficiency

Table 4: Power efficiency of sparse networks on the U250 and ZE3EG FPGAs in comparison with the dense network baseline. We estimate power efficiency using a word/sec/watt metric based on worst-case (i.e. total system power of each platform). FPGA Platform |  System Power (W) |  Network Type |  Number of Networks |  Words Sec/Watt |  Relative Efficiency, %
---|---|---|---|---|---
|  | Dense | 4 | 54 | 100
|  | Sparse-Dense | 1 | 158 | 292
U250 | 225 | Sparse-Dense | 24 | 3065 | 5675
|  | Sparse-Sparse | 1 | 455 | 842
|  | Sparse-Sparse | 20 | 6088 | 11274
|  | Dense | 0 | 0 | 0
ZU3EG | 24 | Sparse-Dense | 1 | 877 | 1624
|  | Sparse-Sparse | 1 | 1893 | 3505

In addition to improved inference performance, reduced power consumption is
becoming increasingly critical [63, 66]. Table 4 shows the absolute and
relative power efficiency for inference operations. Due to the significant
resource reductions associated with sparse networks, not only has the total
throughput improved, but the power consumed per inference operation has also
dropped considerably. It is common to improve throughput at the expense of
increasing energy consumption [66]. Our results demonstrate that sparsity
avoids many unnecessary operations altogether, simultaneously improving
throughput and power efficiency.

##  5 Resource Tradeoffs Analysis

In the previous section, we discussed end-to-end throughput results for a full
network. It became clear during implementation that a key consideration is the
resource usage required to implement the routing and $k$-WTA components. In
this section we implemented a series of controlled experiments to analyze
these resource tradeoffs in isolation.

In GSC, the convolutional layers employed $5\times 5$ kernels. In these
experiments we focus on two other structures, $1\times 1$ and $3\times 3$
kernel types. These kernel types are typical of a number of common networks
structures, such as the ResNet-50 (Figure 14), ResNeXt, and MobileNetV2
networks [25, 75, 61]. We investigate the resource savings achievable via a
combination of activation and weight sparsity applied to these convolutional
layer types. The key questions revolve around how the FPGA resource
requirements scale with weight sparsity, and how this changes as we add in
activation sparsity.

Figure 14: Overview of a ResNet-50 architecture, illustrating the repeated use
of identity and convolutional blocks, and the increasing number of channels
deeper in the network. As can be seen, most of the layers use either $1\times
1$ or $3\times 3$ kernel sizes. The very first ”stem” layer uses a $7\times 7$
kernel size.

###  5.1 Experiment Setup

To investigate whether Complementary Sparsity could be applied generally, we
developed the component shown in Figure 8a as a set of general-purpose
parameterized blocks. For the $k$-WTA block, $K$ is defined per instance at
compilation time. Three convolutional blocks were developed: a sparse-dense
7$\times$7 convolutional block, and separate blocks for $1\times 1$ and
$3\times 3$ sparse-sparse convolutions. The parameterization of these blocks
included: boundary padding size, stride, weight sparsity, and memory
bandwidth, as well as input activation sparsity for the 1$\times$1 and
$3\times 3$ blocks.

When implementing components on an FPGA there is a great deal of flexibility
in choosing how resources are allocated. There is significant latitude to
trade serial processing for parallel processing by allocating sufficient
resources to every stage. This in turn makes it challenging to explore both
resource utilization and throughput in a controlled manner. In these
implementations, we targeted a fixed throughput for all components in order to
focus on resources. Our throughput target was chosen to be aggressive without
leading to exploding resources. The primary target stipulated that a
1$\times$1 [64:64]111Our notation [$a$:$b$] refers to an input channel count
of $a$ and an output channel count of $b$. convolution should be computed in a
single cycle. For a 1x1 [64:64] convolution, when weights and activations are
dense, 4096 multiplications and 4096 additions are required to carry out the
computation per spatial location. For a sparse-sparse computation ($N$=4 and
$K$=8), this requirement is reduced to 32 multiplications and 32 additions,
making this aggressive target feasible. Our $3\times 3$ [64:64] convolution
used nine 1$\times$1 convolutions, taking about 9 cycles. The $k$-WTA layer
had a target of one cycle. As sparsity levels varied the compiler
automatically allocated the hardware resources to achieve this target,
allowing a controlled investigation of resource impact. We removed bandwidth
as a confounding parameter by allocating sufficient memory to meet the target
(but see Section 5.5 below for an analysis of bandwidth).

The parameterization and above setup facilitated a systematic analysis of
Complementary Sparsity for a variety of convolutional layers, primarily as a
function of weight and activation sparsities. Our goal was to gain an improved
understanding of the resource consumption and its scaling with degree of
sparsity. Since extending sparse architectures to dense configurations is not
meaningful, we confine our analysis to $k$-WTA activation sparsity $\geq
50\%$, and weight sparsity $\geq 50\%$. These represent reasonable break
points between sparse and dense implementations.

(a)

(b)

(c)

Figure 15: Impact of activation sparsity on resource utilization for
1$\times$1 [64:64] convolution operations for different degrees of weight
sparsity for: (a) LUTs, (b) FFs and (c) URAMs (K and N indicate the number of
non-zero elements, reduction in utilization relative to K=16).

###  5.2 Resource Utilization of Sparse-Sparse Convolution Kernels

In Figure 15a-15c, and Figure 16a-16c, we present the resource utilization
observed for the convolutional layers when activation sparsity is increased.
In each experiment, we hold the weight sparsity constant, increase the
activation sparsity and report the reduction in resource utilization. Our FPGA
implementations of convolutional layers consume a variety of FPGA resources,
including Lookup Tables (LUTs), Flip Flops (FFs), and memory blocks (URAMs).
We found that, for all investigated levels of weight sparsity, increasing the
activation sparsity delivered a significant reduction in the resource
utilization across all FPGA resources. For example, looking a Figure 15a, for
a weight sparsity of 4 non-zeros out of 64-elements (i.e.
$\frac{60}{64}$=93.75% sparse), as the activation sparsity is increased from
$\frac{16}{64}$ to $\frac{8}{64}$ and $\frac{4}{64}$, the number of LUTs
required for the implementation of the 1$\times$1 convolution is reduced by
2.7X and 4.1X, respectively.

(a)

(b)

(c)

Figure 16: Impact of activation sparsity on resource utilization for
3$\times$3 [64:64] convolution operations for different degrees of weight
sparsity for: (a) LUTs, (b) FFs, (c) URAMs (K and N indicate the number of
non-zero elements, reduction in utilization relative to K=16).

It is apparent that, across all levels of weight sparsity investigated, as the
level of activation sparsity is increased, the complexity of the
implementations of the convolutional layers is reduced. The degree to which
the resource utilization decreased with increased sparsity is dictated by the
resource type and the degree of weight sparsity. For instance, there is a
clear linear relationship between URAMs consumed and the degree of activation
sparsity. This is true for all levels of weight sparsity investigated.

LUTs are used for both routing and implementing multipliers in this design.
The LUT count is reduced as a function of weight sparsity due to the decreased
number of multipliers, while conversely there is greater routing complexity
with increased weight sparsity. This latter effect is due to managing larger
numbers of consolidated sparse weight kernels. Despite these competing
factors, the overall LUT count decreases significantly with weight sparsity.

For FF utilization, the resource savings are more muted at higher weight
sparsities. For FFs, which are primarily used for high bandwidth local
storage, there is a baseline quantity for holding input and output values. The
especially muted 3$\times 3$ convolution FF resource utilization results
illustrated in Figure 16b reflect the fact that FFs are also used to buffer
intermediate results; the results of the 9 internal $1\times 1$ operations are
serially accumulated. Therefore the FF utilization scaling as a function of
weight sparsity is on top of these relatively static baselines. However, in
many instances we demonstrate a super-linear reduction in resource
utilization. This is rate of reduction is observed because a number of the
elements in the implementations of the convolutions scale non-linearly with
the number of non-zero activations; resulting in significant resource savings
as $K$ is decreased.

Figure 17a-17c and Figure 18a-18c show the impact of varying weight sparsity
for a fixed activation sparsity. In these results, the resource savings are
sub-linear. Increases in weight sparsity result in decreases in the number of
multiplies, but as discussed, routing overheads limit these reductions.
However, for LUTs, FFs and URAMs, at any given activation sparsity, increasing
the weight sparsity reduces the resource consumed by the implementation.

In summary, for our FPGA implementations using Complementary Sparsity,
increasing sparsity (weight, activation or both) results in more resource
efficient implementations, while continuing to meet the stipulated throughput
metric.

(a)

(b)

(c)

Figure 17: Impact of weight sparsity on resource utilization for 1$\times$1
[64:64] convolution for different degrees of activation sparsity for: (a)
LUTs, (b) FFs and (c) URAMs (K and N indicates the number of non-zero
elements, reduction in utilization relative to K=16).

(a)

(b)

(c)

Figure 18: Impact of weight sparsity on resource utilization for 3$\times$3
[64:64] convolution operations for different degrees of activation sparsity
for: (a) LUTs, (b) FFs, (c) URAMs (K and N indicate the number of non-zero
elements, reduction in utilization relative to N=16).

###  5.3 Resource Utilization of $k$-WTA

We also investigated the resource impact of our $k$-WTA implementations. Here
too increasing activation sparsity resulted in the consumption of fewer
hardware resources, as illustrated in Figure 19. The resource utilization was
found to decrease almost linearly with the degree of sparsity. This represents
an important synergy, with the convolutional kernel implementations benefiting
from increased levels of activation sparsity, and the cost of providing the
sparse activations decreasing as the level of activation sparsity is
increased.

In Figures 20b\- 20a, the combined resource utilization for sparse-sparse
convolutions and their associated $k$-WTA components is shown. For both the
$1\times 1$ and $3\times 3$ convolutions, the costs associated with the
$k$-WTA implement is small compared with the costs associated with the
convolutions, especially for the $3\times 3$ convolution, where the
implementation cost of the convolution is increased, but the $k$-WTA cost
remains constant.

Figure 19: Impact of activation sparsity levels on $k$-WTA resource
utilization (K indicates the number of non-zero elements, reduction in
utilization relative to K=32).

(a) 1x1 Convolution + $k$-WTA

(b) 3x3 Convolution + $k$-WTA

Figure 20: Total resource utilization of convolution operations and associated
$k$-WTA components (for N=8 and k=8). $k$-WTA consumes a relatively small
percentage of LUTs and FFs, and no URAMS.

###  5.4 Sparsity in the Network Stem

In addition to the convolutional kernels that form the convolutional and
identity blocks in ResNet-50, the network contains an initial “stem”. This
stem performs a 7$\times$7$\times$3 (RGB color values) convolution on the
input image [17]. In many sparse implementations, this first convolutional
layer is left as a standard dense operation, because it represents a small
part of the overall implementation profile. However, the implementation of
this initial convolution can both require significant hardware resources and
dictate overall network throughput. Although the overall latency of the entire
network pipeline will shrink when recast as a sparse implementation, the
throughput benefits will be capped by this first layer, making an efficient
sparse implementation highly desirable.

Complementary sparsity can be successfully applied to this stem convolution,
but, because the inputs to this first layer are dense images, a sparse-sparse
implementation is not feasible. However, a weight-sparse implementation on an
FPGA provides a considerable performance benefit: in our implementations, by
increasing the weight sparsity (from N=9 to N=5) by 1.8X, we increased
throughput by 1.6X. In this layer we chose to implement Complementary Sparsity
in the spatial dimensions. We also imposed block sparsity constraints, with
the 3-element input dimension being treated as a block, either fully non-zero
or completely zero.

The first layer of most DNNs process a dense input data stream and will only
be able to exploit weight sparsity in a sparse-dense configuration. If the
rest of the DNN is implemented as sparse-sparse layers those layers will see
large performance gains. As an unexpected result, in pipelined implementations
we find that the first layer’s throughput will often dictate the maximum
throughput of the network. To increase overall throughput, in FPGAs it is
possible to increase the parallelism of the first layer, such that its sparse-
dense layer latency is less than or equal to the highest latency sparse-sparse
layer. This additional resource cost is made up by the resource gains achieved
in the rest of the network. As a general rule, we find that the large gains
achieved by a sparse-sparse implementation warrant careful profiling of the
rest of the system as unexpected bottlenecks can emerge.

###  5.5 Sparse-Sparse Memory Bandwidth Considerations

Memory represents a scarce resource, and its efficient utilization is a key
contributor to the success of sparse-sparse implementations. Two factors
dictate memory utilization on the FPGA. The first is simply dictated by the
capacity required to retain the relevant weight elements. Second is the
requirement for sufficient memory bandwidth to extract all needed weight
elements on a per-cycle basis. This bandwidth requirement is dictated both by
the number of weights that need to be fetched for each activation and the
number of activations that are processed in parallel:

  1. 1.

Weight Sparsity: for each non-zero activation, the elements from the
corresponding compacted dense weight kernels are processed in parallel. As
weight sparsity is increased (i.e. smaller $N$), the width of the port
required to support the parallel read of all the associated data decreases
linearly.

  2. 2.

Activation Sparsity: processing for each non-zero activation requires an
independent lookup. If activations are processed in parallel, each operation
requires its own memory port. As activation sparsity is increased (i.e.
smaller $K$), the number of memory ports falls linearly.

On FPGAs, memory bandwidth requirements are served by numerous relatively
small Tightly Coupled Memories (TCM) that are implemented as Static RAMs
(SRAMs). On Xilinx platforms, UltraRAMs (URAMs) are dual-ported, with a port
width of 72 bits and a capacity of 288 Kbits (4096 locations). In our
implementation, memory requirements for the first few stages of a network such
as ResNet-50 will be driven by bandwidth rather than capacity. In order to
achieve the stipulated throughput target, weights must be distributed across a
larger number of URAMs than would be dictated by storage capacity requirements
alone. The memory bandwidth required to support the computation of a 1x1
[64:64] convolution in a single cycle (i.e. fully parallelize [64:64] channel
dot products) necessitates multiple dual-ported URAMs. As a result, the
storage capacity of each URAM unit is relatively underutilized.

In summary, in this experiment where we employ a high degree of parallel
computation to make an aggressive but fixed throughput target, sufficient
local memory bandwidth is key. The pattern of access is not predictable, due
to the dynamic selections of the $k$-WTA module. Although this disrupts
location access coherence, the rate of access is predictable. This rate is a
combined function of both weight and activation sparsity. Compared to an
equivalent fully parallel dense network, sparse-sparse networks deliver
significant reductions in both the number and capacity of FPGA TCMs, and the
associated bandwidth.

##  6 Discussion

Over the last decade there has been significant attention focused on
accelerating DNNs using FPGAs and other architectures, including convolutional
networks [18]. In this section we compare our approach to research that is
closest to our work, discuss some of the issues that arise in deploying our
solution to complex networks, and suggest some directions for future work.

###  6.1 Accelerating Sparse DNNs on FPGAs

With Complementary Sparsity we demonstrated that sparse filter kernels can be
interleaved such that multiple convolutional kernels are processed
simultaneously. A related idea has appeared in [38] where they compact columns
of a weight matrix used in a matrix multiply implementation of convolution,
which is then processed through a bit-serial systolic array. As such they can
reduce the number of MAC operations by a factor of 8 (see below for additional
discussion on systolic arrays). They also discuss a process for creating an
interleaved weight matrix by incrementally pruning and compacting during
training. Although they did not explicitly discuss sparse-sparse
optimizations, their compaction technique could potentially be adapted for
creating complementary sparse kernels that are compatible with our
implementation.

There have been a number of papers investigating sparse-dense network
implementations on FPGAs. Employing either weight [31, 19, 16, 85, 34, 38, 10]
or activation sparsity [2], they show it is possible to reduce the number of
MAC operations by routing a subset of the dense values to the sparse set of
operands at the processing units. This can be done either via multi-ported
memories [16] or multiplexor networks [19]. Although reducing the number of
multiplies results in power savings, these techniques typically perform only
one dot product at a time in each processing unit. Unlike these methods,
Complementary Sparsity makes full use of dense activations and sparse weights.
Each activation is paired with a corresponding weight value which allows
multiple dot products to be performed every cycle and enables fully parallel
operations. In addition, Complementary Sparsity provides a path to sparse-
sparse implementations.

###  6.2 Accelerating Sparse Networks on Other Platforms

Recognizing that hardware limitations have held back the deployment of sparse
networks [28], there has been increasing interest in accelerating sparsity on
GPU platforms. It is possible to extract meaningful performance gains with
block-sparse kernels by implementing large blocks, of size $32\times 32$ or
larger [23] with a potential negative impact on accuracy. In [20] CSR based
techniques are used to accelerate common DNN networks such as MobileNet [61].
However, the end to end performance gains are limited and restricted to about
$1.2\times$ and $2\times$ increase over the dense implementations,
respectively. Recently NVIDIA has introduced native support for sparsity in
their Ampere [48] architecture. In Ampere there is a limit of 50% sparsity and
end-to-end gains are modest at about $1.3\times$ faster than dense. To date,
GPU based techniques are limited in their ability to achieve significant
performance gains on full networks. In addition they do not provide a path to
exploiting both sparse activations and sparse weights.

For sparse-sparse networks, when both weight and activation sparsity are
employed [70, 32, 46, 69, 21, 11], it is difficult to efficiently pair the
non-zero weight and activations. Many emerging solutions are based around 2D
systolic arrays of processing units, on both FPGAs and custom ASIC designs.
Here each processing unit performs a check for either matching indices [46,
32] or non-zeros [11] as the weight and activation values are streamed through
the systolic array. One concern with this approach is overall performance.
With Complementary Sparsity we are able to parallelize computation such that
we can execute an entire $1\times 1$ conv block, representing many sparse
kernels, in one cycle. Systolic arrays fundamentally require several cycles to
flow through the weights and activations. This process would then have to
occur for each sparse kernel, thereby limiting their performance gains.
Finally, implementing them efficiently often requires the costly development
of specialized hardware. In contrast, Complementary Sparsity can deliver
performance gains today on currently available hardware.

In this paper we have focused on standard DNNs. Spiking Neural Networks (SNNs)
represent an alternate formalism that offers significant potential for
performance improvements [22, 59]. SNNs model neurons using an analog,
continuous time, framework. Neurons in SNNs have high temporal sparsity, i.e.,
they rarely become active. Hardware chips are emerging that exploit this
characteristic to create event-based systems that achieve significant energy
efficiencies [15, 59]. SNNs historically have been unable to match the
accuracy of DNNs on complex tasks, an issue that has held back their wide-
scale deployment. This problem is an active area of research, with promising
recent results [36, 65], including approaches that attempt to model the
temporal sparsity of SNNs in DNN systems [83].

There exist a number of emerging hardware architectures for exploiting
sparsity. In [35] the authors review different factors for DNNs, including
activation and weight sparsity, and compare a large set of architectures. They
suggest that analog crossbar-based architectures represent the most promising
direction. This is also investigated in [4] where they review memristors,
memristive crossbars, FPGAs, and SNNs for embedded healthcare applications.
Another approach is to implement a scatter-compute-gather module to aggregate
operands based upon the indices of their non-zero values [70]. In [86] the
authors implemented a completely custom memristor-based mixed signal
architecture. They demonstrate large performance gains and energy efficiencies
for embedded applications using a biologically inspired sparse-sparse learning
algorithm.

###  6.3 Deploying Complex Sparse-Sparse Systems

Our results indicate that it is possible to create convolutional networks that
exploit both sparse activations and sparse weights. In this article we
presented results for an end-to-end speech network as well as the core
components used in most convolutional networks. Although these components can
form the foundation for building many networks, modern convolutional networks
often contain a large number of layers and a variety of structures. In these
networks a number of other issues come into play when designing end-to-end
systems. These issues, outlined below, are important design considerations in
implementing efficient commercial systems based on Complementary Sparsity.

_Channel Partitioning_ : The number of channels associated with the
convolutional kernels is not constant and often increases for the deeper
layers. For example, in a Resnet-50, layers start with $64$ channels, but this
increases to $2048$, as illustrated in Figure 14. However, as explicitly noted
in [25], the feature map size is reduced correspondingly, keeping the
computational requirements roughly constant. In ResNet-50, all convolution
operations can be decomposed into groups of 64 dot-products between 64 element
vectors, enabling the increasing channel dimension to be handled by the
repeated use of our modular [64:64] channel blocks. Our implementation of the
$k$-WTA operator also processes the output of the convolutions in units of 64
elements, enabling the modular construction of the ResNet-50 layers.

_Pipeline Latency Balancing_ : When balancing the pipeline of an
implementation with multiple layers, carefully “right-sizing” the layers is
important to maximize efficiency and minimize resource utilization. This in
particularly important in sparse-sparse networks. As discussed in Section 5.4
we find that the large gains achieved by Complementary Sparsity can lead to
unexpected bottlenecks in other areas, such as the initial stem layer. For
dense implementations, the main option is a choice between serial or parallel
implementations. However, for sparse networks, we also have an additional
option. Increasing weight and/or activation sparsity for a given layer
translates into reductions in compute operations per layer, reducing (serial)
latency, and reducing the memory bandwidth required to supply the operands to
the computation.

_Training Accuracy_ : An important issue, outside the focus of this article,
is the ability to train sparse-sparse networks that have sufficient accuracy
while retaining high sparsity. As discussed in Section 2.2 research in
training sparse networks has increased significantly. It is now possible to
create accurate networks with 90% sparsity on ImageNet [17] and Transformers
[13]. Most of that work has focused on weight sparsity with a few papers
focused on activation sparsity. There is relative lack of research on networks
that have both forms of sparsity (exceptions are [1, 86]). In some scenarios
networks trained without explicit activation sparsity end up with highly
sparse activations anyway [19, 33, 7]. This is encouraging because it suggests
that sparse activations may naturally be an optimal outcome. We hope the
performance results shown in this article will help lead to additional
research on sparse-sparse networks.

###  6.4 Future Directions

We have presented an initial set of results on Complementary Sparsity, and
there are a number of areas for future research. One direction is to look
beyond convolutional networks and apply Complementary Sparsity to other
important architectures, such as Transformers [67], and Deep Recommender
systems [84]. This will require a greater focus on linear layers, where it is
possible to overlay multiple rows or columns from a layer’s sparse weight
matrix. A second promising direction is to leverage our FPGA designs to create
hardened IP blocks for a variety of ASICs. A third area is to consider the
application of Complementary Sparsity to existing hardware platforms beyond
FPGAs [62]. Finally, it would be interesting to see if Complementary Sparsity
can be used to accelerate the training of sparse-sparse networks.

##  7 Conclusions

In this article, inspired by the high levels of sparsity in the brain, we
investigate the performance benefits of DNNs that exploit both weight and
activation sparsity. Using a novel technique that we term Complementary
Sparsity we show that it enables highly efficient sparse-dense and sparse-
sparse networks. Using FPGAs we demonstrate that individual sparse-sparse
networks can outperform standard dense DNN networks by over 30X. We further
illustrate that sparse-sparse networks can be implemented using far fewer
hardware resources than their dense counterparts, and that the resource
requirements are inversely proportional to the degree of sparsity. This frugal
use of resources allows 5X more networks to be accommodated on an FPGA,
delivering a full-chip throughput over 110X higher than the corresponding
dense networks. Complementary Sparsity also enables the deployment of DNNs on
smaller embedded platforms than previously possible. To our knowledge, we are
the first to report such dramatic benefits for both sparse-dense and sparse-
sparse networks on FPGAs.

## Acknowledgements

We would like to acknowledge the guidance and feedback from Xilinx, especially
Prasun Raha, Vamsi Nalluri, Mrinal Sarmah, and Mary Low. We thank Greg Maltz
for his critical feedback and help reviewing and editing the article.
Additionally, we would like to acknowledge the help and feedback from Jeff
Hawkins, Luiz Scheinkman, Celeste Baranski, Enno Wein and the Instigate team
(Naira Khurshudyan, Marine Tumasyan, Hmayak Arzumanyan, Hasmik Mantshyan,
Armenuhi Petrosyan, Armen Ohanyan, Davit Petrosyan, Anna Sargsyan, Armen
Hovhannisyan, and Tatul Yeghiazaryan) over the course of this research.

## References

  * Ahmad and Scheinkman [2019] S. Ahmad and L. Scheinkman.  How Can We Be So Dense? The Benefits of Using Highly Sparse Representations.  _arXiv:1903.11257 [cs.LG]_ , 3 2019.  URL http://arxiv.org/abs/1903.11257.
  * Aimar et al. [2019] A. Aimar, H. Mostafa, E. Calabrese, A. Rios-Navarro, R. Tapiador-Morales, I.-A. Lungu, M. B. Milde, F. Corradi, A. Linares-Barranco, S.-C. Liu, and T. Delbruck.  NullHop: A flexible convolutional neural network accelerator based on sparse representations of feature maps.  _IEEE Transactions on Neural Networks and Learning Systems_ , 30(3):644–656, 2019.  doi:10.1109/TNNLS.2018.2852335.
  * Attwell and Laughlin [2001] D. Attwell and S. B. Laughlin.  An energy budget for signaling in the grey matter of the brain.  _Journal of Cerebral Blood Flow and Metabolism_ , 21(10):1133–1145, 10 2001.  ISSN 0271678X.  doi:10.1097/00004647-200110000-00001.  URL http://journals.sagepub.com/doi/10.1097/00004647-200110000-00001.
  * Azghadi et al. [2020] M. R. Azghadi, C. Lammie, J. K. Eshraghian, M. Payvand, E. Donati, B. Linares-Barranco, and G. Indiveri.  Hardware Implementation of Deep Network Accelerators Towards Healthcare and Biomedical Applications.  _IEEE Transactions on Biomedical Circuits and Systems_ , 14(6):1138–1159, 2020.  doi:10.1109/TBCAS.2020.3036081.
  * Bank and Douglas [1992] R. E. Bank and C. C. Douglas.  _Sparse matrix multiplication package (SMMP)_.  IBM Thomas J. Watson Research Division, 1992.
  * Barth and Poulet [2012] A. L. Barth and J. F. a. Poulet.  Experimental evidence for sparse firing in the neocortex.  _Trends in Neurosciences_ , 35(6):345–355, 2012\.  ISSN 01662236.  doi:10.1016/j.tins.2012.03.008.  URL http://dx.doi.org/10.1016/j.tins.2012.03.008.
  * Beaulieu et al. [2020] S. Beaulieu, L. Frati, T. Miconi, J. Lehman, K. O. Stanley, J. Clune, and N. Cheney.  Learning to Continually Learn.  _arXiv:2002.09571_ , 2 2020.  URL http://arxiv.org/abs/2002.09571.
  * Buluç et al. [2009] A. Buluç, J. T. Fineman, M. Frigo, J. R. Gilbert, and C. E. Leiserson.  Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks.  In _Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures_ , pages 233–244, 2009.
  * Changpinyo et al. [2017] S. Changpinyo, M. Sandler, and A. Zhmoginov.  The Power of Sparsity in Convolutional Neural Networks, 2 2017.  URL http://arxiv.org/abs/1702.06257.
  * Chen et al. [2018a] C.-F. Chen, J. Oh, Q. Fan, and M. Pistoia.  SC-Conv: Sparse-complementary convolution for efficient model utilization on cnns.  In _2018 IEEE International Symposium on Multimedia (ISM)_ , pages 97–100, 2018a.  doi:10.1109/ISM.2018.00024.
  * Chen et al. [2020] Q. Chen, Y. Huang, R. Sun, W. Song, Z. Lu, Y. Fu, and L. Li.  An efficient accelerator for multiple convolutions from the sparsity perspective.  _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 28(6):1540–1544, 2020.  doi:10.1109/TVLSI.2020.2976454.
  * Chen et al. [2018b] Y. Chen, D. Paiton, and B. Olshausen.  The Sparse Manifold Transform.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems 31_ , pages 10533–10544. Curran Associates, Inc., 2018b.
  * Cohen [2021] B. Cohen.  Sparsity Without Sacrifice: Accurate BERT with 10x Fewer Parameters, 2021.  URL https://numenta.com/blog/2021/12/13/sparsity-without-sacrifice-accurate-bert-with-10x-fewer-parameters.
  * Cui et al. [2017] Y. Cui, S. Ahmad, and J. Hawkins.  The HTM Spatial Pooler – a neocortical algorithm for online sparse distributed coding.  _Frontiers in Computational Neuroscience_ , 11:111, 2017\.  ISSN 1662-5188.  doi:10.3389/FNCOM.2017.00111.  URL https://www.frontiersin.org/articles/10.3389/fncom.2017.00111/abstract.
  * Davies et al. [2018] M. Davies, N. Srinivasa, T. H. Lin, G. Chinya, Y. Cao, S. H. Choday, G. Dimou, P. Joshi, N. Imam, S. Jain, Y. Liao, C. K. Lin, A. Lines, R. Liu, D. Mathaikutty, S. McCoy, A. Paul, J. Tse, G. Venkataramanan, Y. H. Weng, A. Wild, Y. Yang, and H. Wang.  Loihi: A Neuromorphic Manycore Processor with On-Chip Learning.  _IEEE Micro_ , 38(1):82–99, 2018.  ISSN 02721732.  doi:10.1109/MM.2018.112130359.
  * Dey et al. [2018] S. Dey, D. Chen, Z. Li, S. Kundu, K.-W. Huang, K. M. Chugg, and P. A. Beerel.  A highly parallel FPGA implementation of sparse neural network training.  In _2018 International Conference on ReConFigurable Computing and FPGAs (ReConFig)_ , pages 1–4, 2018.  doi:10.1109/RECONFIG.2018.8641739.
  * Evci et al. [2020] U. Evci, T. Gale, J. Menick, P. S. Castro, and E. Elsen.  Rigging the lottery: Making all tickets winners.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 2943–2952. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/evci20a.html.
  * Farabet et al. [2009] C. Farabet, C. Poulet, J. Han, and Y. LeCun.  CNP: An FPGA-based processor for convolutional networks.  FPL 09: 19th International Conference on Field Programmable Logic and Applications, 2009.  ISBN 9781424438921.  doi:10.1109/FPL.2009.5272559.
  * Fowers et al. [2014] J. Fowers, K. Ovtcharov, K. Strauss, E. S. Chung, and G. Stitt.  A high memory bandwidth FPGA accelerator for sparse matrix-vector multiplication.  In _2014 IEEE 22nd Annual International Symposium on Field-Programmable Custom Computing Machines_ , pages 36–43, 2014.  doi:10.1109/FCCM.2014.23.
  * Gale et al. [2020] T. Gale, M. Zaharia, C. Young, and E. Elsen.  Sparse GPU Kernels for Deep Learning, 2020.  URL http://arxiv.org/abs/2006.10901.
  * Gao et al. [2021] C. Gao, T. Delbrück, and S. Liu.  Spartus: A 9.4 top/s fpga-based LSTM accelerator exploiting spatio-temporal sparsity.  _CoRR_ , abs/2108.02297, 2021.  URL https://arxiv.org/abs/2108.02297.
  * Ghosh-Dastidar and Adeli [2009] S. Ghosh-Dastidar and H. Adeli.  Spiking neural networks.  _International journal of neural systems_ , 19(4):295–308, 8 2009.  ISSN 0129-0657.  URL http://www.ncbi.nlm.nih.gov/pubmed/19731402.
  * Gray et al. [2017] S. Gray, A. Radford, and D. P. Kingma.  GPU kernels for block-sparse weights.  _OpenAI preprint_ , 2017.  URL http://openai-assets.s3.amazonaws.com/blocksparse/blocksparsepaper.pdf.
  * Hawkins and Ahmad [2016] J. Hawkins and S. Ahmad.  Why Neurons Have Thousands of Synapses, a Theory of Sequence Memory in Neocortex.  _Frontiers in Neural Circuits_ , 10(23):1–13, 2016.  ISSN 1662-5110.  doi:10.3389/fncir.2016.00023.
  * He et al. [2015] K. He, X. Zhang, S. Ren, and J. Sun.  Deep Residual Learning for Image Recognition.  _http://arxiv.org/abs/1512.03385_ , 12 2015.  URL http://arxiv.org/abs/1512.03385.
  * Hoefler et al. [2021] T. Hoefler, D. Alistarh, T. Ben-Nun, N. Dryden, and A. Peste.  Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks.  _CoRR_ , abs/2102.00554, 2021.  URL https://arxiv.org/abs/2102.00554.
  * Holmgren et al. [2003] C. Holmgren, T. Harkany, B. Svennenfors, and Y. Zilberter.  Pyramidal cell communication within local networks in layer 2/3 of rat neocortex.  _The Journal of Physiology_ , 551(1):139–153, 8 2003.  ISSN 0022-3751.  doi:10.1113/jphysiol.2003.044784.  URL http://www.jphysiol.org/cgi/doi/10.1113/jphysiol.2003.044784.
  * Hooker [2020] S. Hooker.  The Hardware Lottery, 2020.  URL http://arxiv.org/abs/2009.06489.
  * Intel [2021a] Intel.  OneAPI: A new era of heterogeneous computing.  https://www.intel.com/content/www/us/en/developer/tools/oneapi/overview.html#gs.gysnnu, 2021a.
  * Intel [2021b] Intel.  Intel® distribution of OpenVINO™ toolkit.  https://www.intel.com/content/www/us/en/developer/tools/openvino-toolkit/overview.html, 2021b.
  * Jain et al. [2020] A. K. Jain, H. Omidian, H. Fraisse, M. Benipal, L. Liu, and D. Gaitonde.  A domain-specific architecture for accelerating sparse matrix vector multiplication on FPGAs.  In _2020 30th International Conference on Field-Programmable Logic and Applications (FPL)_ , pages 127–132, 2020.  doi:10.1109/FPL50879.2020.00031.
  * Jamro et al. [2014] E. Jamro, T. Pabis, P. Russek, and K. Wiatr.  The algorithms for FPGA implementation of sparse matrices multiplication.  _Comput. Informatics_ , 33:667–684, 2014.
  * Javed and White [2019] K. Javed and M. White.  Meta-Learning Representations for Continual Learning.  5 2019.  URL http://arxiv.org/abs/1905.12588.
  * Jiang et al. [2021] C. Jiang, D. Ojika, B. Patel, and H. Lam.  Optimized FPGA-based deep learning accelerator for sparse CNN using high bandwidth memory.  In _2021 IEEE 29th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)_ , pages 157–164, 2021.  doi:10.1109/FCCM51124.2021.00026.
  * Kendall and Kumar [2020] J. D. Kendall and S. Kumar.  The building blocks of a brain-inspired computer.  _Applied Physics Reviews_ , 7(1):11305, 2020.  doi:10.1063/1.5129306.  URL https://doi.org/10.1063/1.5129306.
  * Kim and Panda [2021] Y. Kim and P. Panda.  Optimizing Deeper Spiking Neural Networks for Dynamic Vision Sensing.  _Neural Networks_ , 144:686–698, 2021.  ISSN 0893-6080.  doi:https://doi.org/10.1016/j.neunet.2021.09.022.  URL https://www.sciencedirect.com/science/article/pii/S0893608021003841.
  * Knuth [1998] D. E. Knuth.  _The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching_.  Addison Wesley Longman Publishing Co., Inc., USA, 1998.  ISBN 0201896850.
  * Kung et al. [2019] H. Kung, B. McDanel, and S. Q. Zhang.  Packing sparse convolutional neural networks for efficient systolic array implementations: Column combining under joint optimization.  In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ , ASPLOS ’19, page 821–834, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450362405.  doi:10.1145/3297858.3304028.  URL https://doi.org/10.1145/3297858.3304028.
  * Kurtz et al. [2020] M. Kurtz, J. Kopinsky, R. Gelashvili, A. Matveev, J. Carr, M. Goin, W. Leiserson, S. Moore, N. Shavit, and D. Alistarh.  Inducing and exploiting activation sparsity for fast inference on deep neural networks.  In _Proceedings of the 37th International Conference on Machine Learning_ , 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/kurtz20a.html.
  * Lagunas et al. [2021] F. Lagunas, E. Charlaix, V. Sanh, and A. M. Rush.  Block pruning for faster transformers.  _CoRR_ , abs/2109.04838, 2021.  URL https://arxiv.org/abs/2109.04838.
  * Lee et al. [2008] H. Lee, C. Ekanadham, and A. Y. Ng.  Sparse deep belief net model for visual area V2.  _Advances In Neural Information Processing Systems_ , 2008.
  * Lennie [2003] P. Lennie.  The Cost of Cortical Computation.  _Current Biology_ , 13(6):493–497, 3 2003.  ISSN 0960-9822.  doi:10.1016/S0960-9822(03)00135-0.  URL https://doi.org/10.1016/S0960-9822(03)00135-0.
  * Majani et al. [1989] E. Majani, R. Erlanson, and Y. S. Abu-Mostafa.  On the k-winners-take-all network.  In _Advances in neural information processing systems_ , pages 634–642, 1989.
  * Makhzani and Frey [2013] A. Makhzani and B. Frey.  k-Sparse Autoencoders.  _http://arxiv.org/abs/1312.5663_ , 12 2013.  URL http://arxiv.org/abs/1312.5663.
  * Makhzani and Frey [2015] A. Makhzani and B. Frey.  Winner-take-all autoencoders.  _Advances in Neural Information Processing_ , 2015.  URL http://papers.nips.cc/paper/5783-winner-take-all-autoencoders.
  * Malik and Golnari [2019] S. Malik and P. A. Golnari.  Sparse matrix to matrix multiplication: A representation and architecture for acceleration.  In _2019 IEEE 30th International Conference on Application-specific Systems, Architectures and Processors (ASAP)_ , volume 2160-052X, pages 67–70, 2019.  doi:10.1109/ASAP.2019.00-28.
  * Miller et al. [2014] J. K. Miller, I. Ayzenshtat, L. Carrillo-Reid, and R. Yuste.  Visual stimuli recruit intrinsically generated cortical ensembles.  _Proceedings of the National Academy of Sciences_ , 111(38):4053–4061, 9 2014.  ISSN 0027-8424.  doi:10.1073/pnas.1406077111.
  * Mishra et al. [2021] A. K. Mishra, J. A. Latorre, J. Pool, D. Stosic, D. Stosic, G. Venkatesh, C. Yu, and P. Micikevicius.  Accelerating sparse deep neural networks.  _CoRR_ , abs/2104.08378, 2021.  URL https://arxiv.org/abs/2104.08378.
  * Mocanu et al. [2018] D. C. Mocanu, E. Mocanu, P. Stone, P. H. Nguyen, M. Gibescu, and A. Liotta.  Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science.  _Nature Communications_ , 9(1):2383, 12 2018.  ISSN 2041-1723.  doi:10.1038/s41467-018-04316-3.  URL http://www.nature.com/articles/s41467-018-04316-3.
  * Neural Magic [2021a] Neural Magic.  Neural Magic deepsparse.  https://github.com/neuralmagic/deepsparse, 2021a.
  * Neural Magic [2021b] Neural Magic.  YOLOv3: Sparsifying to improve object detection performance.  https://docs.neuralmagic.com/source/model-pages/cv-detection-yolov3.html, 2021b.
  * Olshausen and Field [1996] B. A. Olshausen and D. J. Field.  Emergence of simple-cell receptive field properties by learning a sparse code for natural images.  _Nature_ , 381(6583):607–609, 6 1996.  ISSN 0028-0836.  doi:10.1038/381607a0.  URL http://www.nature.com/doifinder/10.1038/381607a0.
  * Olshausen and Field [2004] B. A. Olshausen and D. J. Field.  Sparse coding of sensory inputs, 2004.  ISSN 09594388.
  * ONNX Runtime developers [2021] ONNX Runtime developers.  ONNX runtime.  https://onnxruntime.ai/, 2021.
  * Paiton et al. [2020] D. M. Paiton, C. G. Frye, S. Y. Lundquist, J. D. Bowen, R. Zarcone, and B. A. Olshausen.  Selectivity and robustness of sparse coding networks.  _Journal of Vision_ , 20(12):10, 2020.  ISSN 1534-7362.  doi:10.1167/jov.20.12.10.  URL https://doi.org/10.1167/jov.20.12.10.
  * Pulido and Ryan [2021] C. Pulido and T. A. Ryan.  Synaptic vesicle pools are a major hidden resting metabolic burden of nerve terminals.  _Science Advances_ , 7(49):9027, 12 2021.  ISSN 2375-2548.  doi:10.1126/SCIADV.ABI9027.  URL https://www.science.org/doi/abs/10.1126/sciadv.abi9027.
  * Rawat and Wang [2017] W. Rawat and Z. Wang.  Deep Convolutional Neural Networks for Image Classification: A Comprehensive Review.  _Neural Computation_ , 29(9):2352–2449, 9 2017\.  ISSN 0899-7667.  doi:10.1162/neco_a_00990.  URL http://www.mitpressjournals.org/doi/abs/10.1162/neco_a_00990.
  * Reuther et al. [2020] A. Reuther, P. Michaleas, M. Jones, V. Gadepally, S. Samsi, and J. Kepner.  Survey of machine learning accelerators.  _2020 IEEE High Performance Extreme Computing Conference (HPEC)_ , Sep 2020.  doi:10.1109/hpec43674.2020.9286149.  URL http://dx.doi.org/10.1109/HPEC43674.2020.9286149.
  * Roy et al. [2019] K. Roy, A. Jaiswal, and P. Panda.  Towards spike-based machine intelligence with neuromorphic computing.  _Nature_ , 575(7784):607–617, 2019.  ISSN 1476-4687.  doi:10.1038/s41586-019-1677-2.  URL https://doi.org/10.1038/s41586-019-1677-2.
  * Sainath and Parada [2015] T. N. Sainath and C. Parada.  Convolutional neural networks for small-footprint keyword spotting.  In _Sixteenth Annual Conference of the International Speech Communication Association_ , 2015.
  * Sandler et al. [2018] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen.  MobileNetV2: Inverted Residuals and Linear Bottlenecks, 1 2018.  URL http://arxiv.org/abs/1801.04381.
  * Spracklen et al. [2021] L. Spracklen, K. Hunter, and S. Ahmad.  Poster: “how can we be so slow?” realizing the performance benefits of sparse networks.  In _Sparsity in Neural Networks: Advancing Understanding and Practice_ , July 2021.  URL https://tinyurl.com/so-slow.
  * Strubell et al. [2019] E. Strubell, A. Ganesh, and A. McCallum.  Energy and policy considerations for deep learning in NLP.  _CoRR_ , abs/1906.02243, 2019.  URL http://arxiv.org/abs/1906.02243.
  * Tang and Lin [2017] R. Tang and J. Lin.  Deep Residual Learning for Small-Footprint Keyword Spotting.  _https://arxiv.org/abs/1710.10361_ , 10 2017.  URL https://arxiv.org/abs/1710.10361.
  * Tavanaei et al. [2019] A. Tavanaei, M. Ghodrati, S. R. Kheradpisheh, T. Masquelier, and A. Maida.  Deep learning in spiking neural networks.  _Neural Networks_ , 111:47–63, 2019.  ISSN 0893-6080.  doi:https://doi.org/10.1016/j.neunet.2018.12.002.  URL https://www.sciencedirect.com/science/article/pii/S0893608018303332.
  * Thompson et al. [2020] N. C. Thompson, K. H. Greenewald, K. Lee, and G. F. Manso.  The Computational Limits of Deep Learning.  _CoRR_ , abs/2007.0, 2020.  URL https://arxiv.org/abs/2007.05558.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention Is All You Need.  In _31st Conference on Neural Information Processing Systems (NIPS 2017)_ , Long Beach, 12 2017.  URL http://arxiv.org/abs/1706.03762.
  * Vinje and Gallant [2000] W. E. Vinje and J. L. Gallant.  Sparse coding and decorrelation in primary visual cortex during natural vision.  _Science_ , 287(5456):1273–6, 2000.  ISSN 0036-8075.  doi:10.1126/science.287.5456.1273.
  * Wang et al. [2019] D. Wang, J. Shen, M. Wen, and C. Zhang.  Efficient implementation of 2D and 3D sparse deconvolutional neural networks with a uniform architecture on fpgas.  _Electronics_ , 8(7), 2019.  ISSN 2079-9292.  doi:10.3390/electronics8070803.  URL https://www.mdpi.com/2079-9292/8/7/803.
  * Wang et al. [2020] X. Wang, C. Wang, J. Cao, L. Gong, and X. Zhou.  WinoNN: Optimizing FPGA-based convolutional neural network accelerators using sparse winograd algorithm.  _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 39(11):4290–4302, 2020.  doi:10.1109/TCAD.2020.3012323.
  * Wang [2021] Z. Wang.  SparseDNN: Fast sparse deep learning inference on cpus.  _CoRR_ , abs/2101.07948, 2021.  URL https://arxiv.org/abs/2101.07948.
  * Warden [2018] P. Warden.  Speech commands: A dataset for limited-vocabulary speech recognition.  _CoRR_ , abs/1804.03209, 2018.  URL http://arxiv.org/abs/1804.03209.
  * Weliky et al. [2003] M. Weliky, J. Fiser, R. H. Hunt, and D. N. Wagner.  Coding of natural scenes in primary visual cortex.  _Neuron_ , 37:703–718, 2003.  ISSN 08966273.  doi:10.1016/S0896-6273(03)00022-9.
  * Wikipedia contributors [2021] Wikipedia contributors.  Special structure matrix.  https://en.wikipedia.org/wiki/Sparse_matrix#Special_structure, 2021.
  * Xie et al. [2017] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He.  Aggregated residual transformations for deep neural networks.  In _Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017_ , volume 2017-Janua, pages 5987–5995. Institute of Electrical and Electronics Engineers Inc., 11 2017.  ISBN 9781538604571.  doi:10.1109/CVPR.2017.634.
  * Xilinx [2020] Xilinx.  Vivado design suite user guide, high-level synthesis.  https://www.xilinx.com/support/documentation/sw_manuals/xilinx2020_1/ug902-vivado-high-level-synthesis.pdf, 2020\.
  * Xilinx [2021a] Xilinx.  Vitis high-level synthesis user guide : HLS pragmas.  https://docs.xilinx.com/r/en-US/ug1399-vitis-hls/HLS-Pragmas, 2021a.
  * Xilinx [2021b] Xilinx.  Alveo U200 and U250 data center accelerator cards data sheet.  https://www.xilinx.com/support/documentation/data_sheets/ds962-u200-u250.pdf, 2021b.
  * Xilinx [2021c] Xilinx.  Xilinx Vitis AI.  https://www.xilinx.com/products/design-tools/vitis/vitis-ai.html, 2021c.
  * Xilinx [2021d] Xilinx.  Zynq UltraScale+ MPSoC data sheet.  https://www.xilinx.com/support/documentation/data_sheets/ds891-zynq-ultrascale-plus-overview.pdf, 2021d.
  * Yamaguchi and Busato [2021] T. Yamaguchi and F. Busato.  Accelerating matrix multiplication with block sparse format and NVIDIA tensor cores.  https://developer.nvidia.com/blog/accelerating-matrix-multiplication-with-block-sparse-format-and-nvidia-tensor-cores/, 2021\.
  * Yao et al. [2018] Z. Yao, S. Cao, W. Xiao, C. Zhang, and L. Nie.  Balanced sparsity for efficient DNN inference on GPU.  _CoRR_ , abs/1811.00206, 2018.  URL http://arxiv.org/abs/1811.00206.
  * Yousefzadeh and Sifalakis [2021] A. Yousefzadeh and M. Sifalakis.  Training for temporal sparsity in deep neural networks, application in video processing.  _CoRR_ , abs/2107.0, 2021.  URL https://arxiv.org/abs/2107.07305.
  * Zhang et al. [2019] S. Zhang, L. Yao, A. Sun, and Y. Tay.  Deep learning based recommender system: A survey and new perspectives.  _ACM Comput. Surv._ , 52(1), feb 2019.  ISSN 0360-0300.  doi:10.1145/3285029.
  * Zhu et al. [2020] C. Zhu, K. Huang, S. Yang, Z. Zhu, H. Zhang, and H. Shen.  An efficient hardware accelerator for structured sparse convolutional neural networks on FPGAs.  _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , 28(09):1953–1965, sep 2020.  ISSN 1557-9999.  doi:10.1109/TVLSI.2020.3002779.
  * Zyarah et al. [2020] A. M. Zyarah, K. Gomez, and D. Kudithipudi.  Neuromorphic System for Spatial and Temporal Information Processing.  _IEEE Transactions on Computers_ , pages 1–1, 6 2020.  ISSN 0018-9340.  doi:10.1109/tc.2020.3000183.