# SGCN: Exploiting Compressed-Sparse Features in
Deep Graph Convolutional Network Accelerators

Mingi Yoo2,1, Jaeyong Song2,1, Jounghoo Lee2, Namhyung Kim3, Youngsok Kim2,*,
and Jinho Lee4,* 4Department of Electrical and Computer Engineering, Seoul
National University
2Department of Computer Science, Yonsei University
3Samsung Electronics {skys7297, jaeyong.song<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph convolutional networks (GCNs) are becoming increasingly popular as they
overcome the limited applicability of prior neural networks. One recent trend
in GCNs is the use of deep network architectures. As opposed to the
traditional GCNs, which only span only around two to five layers deep, modern
GCNs now incorporate tens to hundreds of layers with the help of residual
connections. From such deep GCNs, we find an important characteristic that
they exhibit very high intermediate feature sparsity. This reveals a new
opportunity for accelerators to exploit in GCN executions that was previously
not present.

In this paper, we propose _SGCN_ , a fast and energy-efficient GCN accelerator
which fully exploits the sparse intermediate features of modern GCNs. SGCN
suggests several techniques to achieve significantly higher performance and
energy efficiency than the existing accelerators. First, SGCN employs a GCN-
friendly feature compression format. We focus on reducing the off-chip memory
traffic, which often is the bottleneck for GCN executions. Second, we propose
microarchitectures for seamlessly handling the compressed feature format.
Specifically, we modify the aggregation phase of GCN to process compressed
features, and design a combination engine that can output compressed features
at no extra memory traffic cost. Third, to better handle locality in the
existence of the varying sparsity, SGCN employs sparsity-aware cooperation.
Sparsity-aware cooperation creates a pattern that exhibits multiple reuse
windows, such that the cache can capture diverse sizes of working sets and
therefore adapt to the varying level of sparsity. Through a thorough
evaluation, we show that SGCN achieves 1.66$\times$ speedup and 44.1% higher
energy efficiency compared to the existing accelerators in geometric mean.

###### Keywords:

Graph Convolutional Networks, Sparsity, Compressed Format, Accelerators

11footnotetext: Co-first authors.**footnotetext: Co-corresponding authors.

##  I Introduction

Graph convolutional networks (GCNs) are becoming an increasingly popular type
of deep neural networks (DNNs) as they can process highly irregular data [37].
They have been successfully adopted to achieve high quality in applications
such as node/edge classification [93], molecular structure analysis [16], and
classic DNN applications including natural language processing [75] or scene
understanding [83].

Even though GCNs fall into a kind of DNN, it is widely known to exhibit a
distinct computational characteristic compared to classic DNNs in that they
require dedicated accelerator architectures [80, 6, 46, 51, 17, 18, 88, 9,
47]. The early challenge of GCNs has been to deal with the high sparsity of
input graph topology. It is known that the graph topology data exhibit
near-100% sparsity [41]. Driven by the high topology sparsity, several
proposals have been made to take advantage of the hybrid nature in the
execution [80, 6], handle load imbalance [51, 17], explore dataflow [47, 88],
or reorder the topology [18].

Figure 1: Average sparsity of intermediate features in traditional and modern
GCNs with a various number of layers.

In contrast to the topology data, the per-vertex feature data has often been
treated with dense array representation by existing GCN accelerators because
the sparsity of the features is far lower than that of the graph topology
[17]. Prior efforts targeting the feature accesses were often focused on input
features [17] or relied on the fact that the feature width shrinks towards the
output layer [17, 46]. Those approaches were attractive with traditional GCNs,
especially when the number of layers is small ($\leq$ 5) and each layer width
is carefully tuned.

However, recent advances in the GCN are leading to different circumstances.
With the introduction of residual connections, modern GCNs [44, 45, 43, 10,
49] now have tens to hundreds, or even a thousand layers, where the feature
width remains constant throughout the entire network.

Fortunately, we make an observation that the modern GCNs exhibit much higher
intermediate feature sparsity, providing an excellent opportunity for
throughput and energy efficiency. As shown in Fig. 1, the intermediate feature
sparsity has been very low in traditional shallow GCNs (up to 20% sparsity).
However, with deep GCNs with residual connections [44, 45, 43], the
intermediate feature sparsity sharply rises up to 70% as the network becomes
deeper. When fully exploited, this intermediate feature sparsity can provide
higher performance and energy efficiency. Considering that the majority of the
GCN execution is memory-intensive and shows repetitive random accesses, the
expected benefit is significant.

There are several key challenges, however, when it comes to fully exploiting
the sparsity of the features. First, we need a special format for the GCN
intermediate features. Naïvely employing existing sparse formats such as
compressed sparse row (CSR) for the features may result in lower performance.
Even though CSR is considered a de facto standard for sparse data
representation, it is not very efficient for the level of sparsity we observe
and the dynamic level of sparsity caused from intermediate features.

Second, existing sparse DNN accelerators do not fit well for handling sparse
features of GCNs. There have been several DNN accelerators, often targeting
convolutional neural networks (CNNs) [56, 33, 97]. However, their objectives
are usually oriented toward reducing the computational workload. Such a
strategy could be promising to CNNs because they are computationally
intensive, and reducing the number of computations (i.e., MACs) easily
translates to performance benefits. However, the computational complexity of
GCNs is relatively low, because it usually involves only one MAC operation per
each feature element. In such circumstances, the focus should be on reducing
the memory traffic volume, not on reducing the amount of computation.

Lastly, the varying level of sparsity makes it difficult to handle locality
with tiling techniques. Recent work on GCN acceleration [47, 88] splits the
graph topology as well as the feature matrix to reduce the feature working set
to fit into cache memory. With such techniques, however, the dynamic level of
sparsity cannot be estimated at a static time and makes it difficult to
determine the right tile size.

In this paper, we present _SGCN_ , a fast and energy-efficient GCN accelerator
which minimizes off-chip DRAM accesses by fully exploiting the intermediate
feature sparsity of modern GCNs. First, we present _Bitmap-index Embedded In-
place CSR_ (BEICSR) format that is tailored for GCN execution. Targeting
sparsity of roughly around 50%, we find that using bitmaps as indices result
in a good compression rate. In addition, by embedding indices in the same row
with the content, the accesses can exhibit a much better locality.
Furthermore, BEICSR performs an in-place compression because it suits the
parallel writes and random reads from GCN execution. Second, we provide
microarchitectures and the pipeline structure for executing the sparsity-aware
GCNs. We design a sparse aggregator unit that performs the aggregation phase
of GCN from features in a compressed format. In addition, we add an in-place
compressor with the ReLU unit in the combination phase, such that the
compression can be done without having to pay for extra memory access
overhead. Third, we propose sparsity-aware cooperation for handling the
varying working set size due to the dynamic level of sparsity. We alter the
multiple engines to create access patterns containing various-sized working
sets. As a result, even when the working set size is larger than expected, the
cache memory can capture a slightly smaller working set that fits into the
cache and reuse some portion of the features.

In summary, this paper makes the following contributions:

  * •

We identify the opportunity for utilizing the sparsity of the intermediate
features in modern deep GCN execution.

  * •

We present BEICSR, a compressed format designed for sparsity-aware aggregation
in GCN executions.

  * •

We present an SGCN accelerator microarchitecture that benefits from sparse
feature data in GCN execution.

  * •

We propose sparsity-aware cooperation to handle the varying working set size
induced by dynamic levels of sparsity.

  * •

We provide a thorough evaluation for SGCN to show the speedup and energy
efficiency gain compared to prior work.

##  II Motivation

###  II-A Intermediate Feature Sparsity

Figure 2: (a) Effect of residual connection and number of layers on average
intermediate feature sparsity and (b) intermediate feature sparsities in
layers of modern GCN.

In this section, we study the intermediate feature sparsity of deep GCNs. Fig.
2a shows the average feature sparsity of traditional GCNs [37] and modern deep
GCNs [45] whose difference is the existence of the residual connections. We
chose 3, 5, and 28 layers which are common choices for traditional (3, 5
layers) and modern (28 layers) GCNs.

As previously shown in Fig. 1, traditional GCNs with less than five layers
(Fig. 2a-Traditional) show low sparsity, which roughly ranges around 5-30%.
Note that 28-layer traditional GCN does not converge for all datasets. On the
other hand, with modern deep GCNs (Fig. 2a-Modern), we can make two
observations that are distinct from conventional GCNs. First, the addition of
residual connection immediately increases the sparsity to a much higher level
[66]. As displayed in Fig. 2a-Modern, even in shallow conventional GCNs,
adding a residual connection yields over 50% sparsity. When a network is
learning well, having around 50% sparsity is normal behavior, and the low
sparsity in the traditional GCNs implies that the network struggles to learn a
meaningful set of features. Second, deeper networks have more sparsity in
general. Although there are some exceptions, there is a clear trend in Fig.
2a-Modern that deeper networks exhibit higher sparsity. In Fig. 2b, we plot
the per-layer sparsity measured from the ‘28 w/ residual’ network. The results
reveal that the sparsity varies per dataset, and is generally sparser towards
the output layer. This aligns with findings from [63], and can be interpreted
as that the network is trying to find disentangled representations [25] for
classification tasks.

From the two observations, we found that the higher intermediate feature
sparsity exists in modern GCNs across datasets, and is likely to exist in
future GCNs too. The goal of SGCN is to utilize this characteristic to design
an accelerator with better performance and energy efficiency.

Figure 3: Comparison of various sparse data representations for GCN
intermediate features.

###  II-B Need for a New Accelerator Architecture

In this section, we highlight the need for a new accelerator. The goal is to
exploit the ample amount of intermediate feature sparsity for performance
benefits. In Fig. 3, we compare the off-chip memory traffic and the
performance of GCN accelerators where dense representation, CSR, COO, BSR,
Blocked Ellpack and the proposed sparse format (BEICSR) are used for the
intermediate features, respectively. We used deep GCNs with 28 layers trained
for nine datasets, which exhibit around 40 to 70% sparsity as studied in
Section II-A. In the plot, we sorted the datasets in the order of increasing
average sparsity for clarity. Please refer to Section VI-A for the detailed
setup.

Despite the large potential from the intermediate features, the results show
that naïvely supporting sparse features on a GCN accelerator results in little
or negative speedup. The colored bars show the number of off-chip memory
accesses caused during the execution, and the curves represent the
corresponding speedups. From the baseline ‘Dense’ which regards the features
as a dense matrix, a naïve approach would be to adopt a CSR data structure for
the features as done for sparse graph topology [80, 17, 47, 18, 88] or for CNN
intermediate features [57, 2].

Because the GCN executions are known to be highly memory-intensive, the amount
of memory traffic is critical to the performance. However, CSR requires an
extra element per non-zero value, and fails to provide memory traffic
reduction around the provided sparsity range. As a result, the naïve CSR
approach experiences a small or negative speedup from the baseline. The COO
format has even more index overheads because it stores both row and column
indices for each non-zero element. The problem persists with other sparse
formats with block sparsity. Block Compressed Row (BSR) and Blocked Ellpack
are popular blocked sparse representations. However, they are beneficial only
when there are many empty blocks (e.g., 2$\times$2). Because GCN intermediate
activations seldom exhibit such patterns, they are not suitable for GCNs.

On the other hand, the bars denoted ‘BEICSR’ represent our scheme, which
utilizes BEICSR for the feature matrix. With an efficient compression format
designed for the observed level of sparsity, our scheme successfully converts
the sparsity into a reduction in the memory access count. Furthermore, the
addition of ‘SAC’ (sparsity-aware cooperation) technique further improves the
efficiency of BEICSR. This demonstrates the need for a new accelerator, whose
speedup cannot be achieved by existing approaches.

##  III Background

###  III-A Graph Convolutional Networks

Given a graph topology and a set of incoming features, a conventional graph
convolutional network (GCN) produces its outgoing features by performing the
operations of its layers on the incoming features. In a basic GCN, the
outgoing features of the $\mathit{l}$-th layer, $\mathit{X^{l+1}}$, is
computed as:

$\mathit{X^{l+1}=\sigma(\tilde{A}\cdot X^{l}\cdot W^{l})}$ (1)

where $\mathit{\sigma}$ is a non-linear activation function (e.g., ReLU),
often preceded by a normalization function. $\mathit{\tilde{A}}$ is the
adjacency matrix of the graph, and $\mathit{X^{l}}$ and $\mathit{W^{l}}$
denote the incoming features and weights of the $\mathit{l}$-th layer,
respectively.

In the past, it was believed that GCNs deeper than five layers would lead to
very low accuracy, a phenomenon is widely known as over-smoothing [82, 49].
Because of this, the design efforts on GCNs were mostly paid to carefully
configuring the feature width of a few layers, usually in a shrinking manner.
In this circumstance, one promising approach was to adjust the order of
aggregation and combination [17, 47, 46]. Because changing the order of those
two phases did not affect the correctness of Eq. 1, the combination was done
first on a shrinking layer, and aggregation was done first on an expanding
layer to reduce the amount of computation and memory accesses [46]. In
addition, sometimes specially handling the first layer was found beneficial
[17]. Because the first layer’s input features (i.e., $X^{1}$) are not
calculated but included in the dataset itself, those can be super-sparse,
especially when one-hot encoding is used.

However, as the technology advances, GCNs have evolved to employ residual
connections, which alters Eq. 1 to:

$\displaystyle S^{l+1}$ $\displaystyle=S_{res}^{l+1}+S^{l},$ $\displaystyle
S_{res}^{l+1}$ $\displaystyle=\tilde{A}\cdot X^{l}\cdot W^{l},$ $\displaystyle
X^{l}$ $\displaystyle=\sigma(S^{l}).$ (2)

Figure 4: Operations of a modern GCN layer.

Fig. 4 illustrates the operation. The calculation of
$\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ and its variants are usually called
_aggregation_ , which does not involve trainable weights. It is the process of
collecting the features from neighboring vertices and aggregating them. The
calculation of $\mathit{X^{l}}\cdot\mathit{W^{l}}$ and its variants are often
called _combination_ as it computes the next layer’s features by linearly
combining the incoming features and the weight parameters.

With the introduction of residual connections, it was found that GCNs can be
as deep as convolutional neural networks, and tens [10, 44, 45] to even a
thousand layers [43] are being used for state-of-the-art GCNs. With deep
layers, these designs now have uniform feature widths, which invalidates the
phase ordering technique. Furthermore, the sparsity of the input features now
does not have much impact on the total execution time, as the speedup would be
amortized over the tens of layers. Fortunately, this use of residual
connections dramatically increases the sparsity of the intermediate features,
which enables another opportunity for performance improvement of GCNs.

###  III-B Hardware Acceleration of GCNs

Often, the key to the GCN accelerators is supporting the hybrid nature of
aggregation and combined phases. Some architectures implement shared units
that support varying datapath for both phases [17, 47, 51], and others
implement separate units and pipeline two phases [80, 9, 18, 88].

Table I summarizes the characteristics of the existing GCN accelerators. GCN
accelerators can be further classified into two types depending on which of
the aggregation and combination phases get performed first. _Aggregation-
first_ accelerators perform the aggregation phase followed by the combination
phase. That is, an aggregation-first accelerator first computes
$\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ followed by
$\mathit{(\tilde{A}}\cdot\mathit{X^{l}})\cdot\mathit{W^{l}}$. _Combination-
first_ accelerators, on the other hand, compute
$\mathit{X^{l}}\cdot\mathit{W^{l}}$ followed by
$\mathit{\tilde{A}}\cdot(\mathit{X^{l}}\cdot\mathit{W^{l}})$. The advantage of
each path lies in whether the width of the features increases or decreases
after the combination phase, and some approaches suggest utilizing the
differences [47, 46]. However, with the introduction of deep GCNs [10, 44, 45,
43], the intermediate feature widths usually remain the same throughout the
network, and the differences disappear.

TABLE I: Comparison of GCN Accelerators Accelerator |  Compressed Feature? |  Target Layers |  Residual |  Execution Order
---|---|---|---|---
AWB-GCN [17] | ✗ | 2 | ✗ | Comb. first
EnGN [51] | ✗ | 2 | ✗ | Comb. first
HyGCN [80] | ✗ | 1-2 | ✗ | Aggr. first
Bidirectional [46] | ✗ | 3 | ✗ | Both
GCNAX [47] | ✗ | 2 | ✗ | Both
I-GCN [18] | ✗ | 2 | ✗ | Comb. first
SGCN (Ours) | ✓ BEICSR (§V-A) |  $>$5 | ✓ | Aggr. first
Figure 5: Our GCN accelerator architecture exploits the high sparsity of
graphs. Green modules are added for SGCN.

Fig. 5 shows the baseline GCN accelerator architecture, similar to prior art
[80, 9, 88], where the green shaded units have been added for SGCN. The
aggregation unit uses SIMD MAC cores to process the accumulation of features
from multiple vertices. The topology matrix $\mathit{\tilde{A}}$ is assumed to
be in a CSR format to employ the high sparsity. Similar to graph processing
accelerators [21, 55, 40], a graph reader reads the indices vertex indices and
the corresponding edges. From the edge information, the feature reader fetches
the feature vectors of the edge destinations. Together, these modules feed the
SIMD cores to continuously process the aggregation without being stalled. Each
module has a small buffer to temporarily store prefetched values to avoid
stalls from upstream backpressure.

As accesses to the feature vectors from neighboring vertices exhibit a highly
randomized pattern over a wide range of data, a sizable on-chip memory is used
as a global cache resembling a last-level cache in modern CPUs. However, the
working set size often far exceeds the capacity of the global cache,
prohibiting an efficient use of the inherent locality in the feature vector
accesses, leaving the aggregation phase highly memory intensive.

The combination engine contains a systolic array for matrix multiplications at
its core, similar to conventional DNN accelerators [32, 38]. The input feature
and weight buffers provide input matrices, $X$ and $W$, respectively, to the
systolic array. The output is written back to the off-chip DRAM, usually
becoming the input to the next layer.

##  IV Design Goals

(a) CSR format.

(b) BEICSR format.

(c) BEICSR with feature tiling support.

Figure 6: Compression formats of the feature matrix.

From the motivation, our objective is to devise a sparse format for the
features and design an accelerator microarchitecture that efficiently process
them. For the objective, the following design goals were set in deriving the
schemes for SGCN.

First, the primary target should be the memory access reduction, not the
computation or the capacity. The primary bottleneck of GCN execution is known
to be the aggregation phase, which is extremely memory intensive [9, 18]. This
indicates that solely optimizing the amount of computation without memory
traffic reduction (e.g., zero skipping) would not be an optimal choice.

Second, the format and the resulting access pattern should be cache- and DRAM-
friendly. In contrast to CNNs where the feature accesses can be done
sequentially, GCN aggregation features incur random accesses of small per-
vertex features (i.e., a few cachelines). When dealing with sparse formats,
special care must be taken that each access is aligned to the cacheline and/or
the DRAM burst length to optimize off-chip traffic. Furthermore, because the
intermediate features are dynamically created as a result of the previous
layer, the format should allow parallel writes as well as reads. Especially
with variable length rows as a result of compression, it is easy for the
access pattern to exhibit many unaligned accesses or bank conflicting
accesses. Such a problem appears more often for modern memory systems such as
HBM that do not support multi-rank channels. Thus, the compression format and
its execution should be aware of the memory subsystem and exploit it.

Third, the execution should embrace existing GCN accelerators. For example,
existing accelerators employ overlapping between phases [80, 47] or
topology/feature tiling [47, 88]. Naïvely applying compressed format and
execution flow could potentially disable such techniques, especially with
variable sparsity levels that cannot be estimated statically. With the
sparsity-aware GCN execution, such techniques must be embraced to achieve
maximum performance.

##  V SGCN Architecture

###  V-A Compression Format

The ultimate purpose of compression from SGCN is to reduce off-chip memory
access. This is obviously sensitive to the compression format which we employ
for the feature matrix. Compared to the conventional sparse DNN accelerators
[56, 33], the difference is that the feature matrix of GCNs exhibit a highly
randomized pattern due to the extremely sparse nature of the topology matrix
$\mathit{\tilde{A}}$. For each random access, a portion of a vertex feature
array is accessed, which usually spans a few cachelines.

A naïve choice for dealing with sparse data is a compressed sparse row (CSR).
However, applying a naïve CSR will not result in off-chip traffic reduction.
With CSR, every non-zero element requires two values: one for the column
index, and the other for the value itself. Thus, at sparsity below 50%, there
is only capacity overhead instead of reduction, as exemplified in Section II.

To tackle the above issues, we propose BEICSR (Bitmap-index Embedded In-place
CSR) format for the intermediate GCN features. Fig. 6 illustrates the
conventional CSR format (6a) and the compression format proposed for SGCN (6b)
against the same set of data. We make the following design choices for the
format:

Embedded Bitmap Index. Instead of column indices, we use _bitmap indices_ for
each vertex. For example, if an example array of size four is $(0,0.3,0.5,0)$,
we place $0110^{\prime}b$ followed by the non-zero array $(0.3,0.5)$. Assuming
the feature vector has elements with 50% sparsity, and each element occupies
32 bits, we can calculate the overhead of the bit vector index. when the
feature vector width is $n$, the bitmap index size is $n$ bits, and the non-
zero feature data size is $32n\times 0.5=16n$. Therefore, it leads to a total
index overhead of only 6.25% in that case ($n/16n$), which would be much lower
than that of the naïve CSRs that require one integer index per non-zero
element. On the other hand, if we use CSR for the same 50% sparsity, we have
$32n\times 0.5$ overhead for the column indices plus the row pointers to
indicate the starting location of the arrays. Combined with the non-zero
feature data size, it would result in an increased size instead of
compression.

In addition, we pose to _embed the bitmap index_ at the head of the same array
which stores the non-zero values. In compressed formats, indices are commonly
placed in an independent array. However, such a choice would result in a poor
memory access pattern. When a bit vector index for a row is accessed, the
surrounding cache line containing indices for other rows is always accessed
together in single memory access. Unless reused before eviction, they are
considered overhead. Observing the access pattern, the accesses to the bit
vector index are almost always followed by the non-zero values. The only
exception is when the bit vector index contains all zeros. (i.e., no non-zero
element in the row). However, considering that the sparsity is around 50% and
each element has little dependence on the other, such an occasion is unlikely.
Therefore, the choice of embedding the bitmap index in the same array with the
non-zero values yields a better memory access pattern. Note that there exist
some formats using bitmap indices [74, 91], but they rely on entirely empty
rows [74] or blocks [91] and hence are inappropriate for GCN features.

In-place Compression. A common problem with using compressed formats for
performance is the variable lengths. Not only this would necessitate an
indirection array similar to a row pointer, but also result in frequent
misaligned memory accesses that lead to traffic volume overhead. To store the
offsets for each row, some indirection array equivalent to a row pointer would
be needed. Instead, we compress the data row-by-row and store each row at the
same reserved place in the memory as if the row was left uncompressed. Even
though this would give no benefit to the memory capacity, we argue that such a
choice is almost necessary for the following reasons. First, it would provide
reduced off-chip traffic aligned to the cacheline boundaries. The alignment is
especially important, since the access granularity only spans a few
cachelines. Much of the space reserved for a row would be empty, and therefore
not accessed from the memory. Furthermore, the beginning of each row can be
cacheline-aligned, such that the loss from misalignment can be minimized.
Second, it allows parallel writes at the output of each layer. Naively using a
variable length storage format requires serialization, because we do not know
the size of the compressed feature array from each vertex. Such a choice would
incur an intolerable overhead to the execution time. Lastly, because the sizes
of the rows are uniform, there is no need for an indirection array. Locating
the compressed data just involves a multiplication with the vertex id, which
eliminates the need for accessing indirection arrays. This scheme reduces the
memory access count and contributes towards row-buffer locality, and achieves
better memory bandwidth utilization.

###  V-B Supporting Feature Matrix Slicing

Many modern GCN accelerators propose slicing the feature matrix for better
data reuse [87, 88, 47]. When compressing the entire row together, accessing a
slice of the feature matrix involves the following sequence: 1) Read the bit
vector index to find the range of non-zero values corresponding to the slice,
2) read multiple cachelines that contain non-zero values from the slice, and
3) perform aggregation.

The pitfall from the above sequence is the overhead of unaligned accesses. For
example, when there are 16 non-zero values (64 bytes) in a slice, unaligned
access would almost always require two 64B cachelines, which neutralizes the
benefit from the sparsity.

Therefore, we employ _sliced BEICSR_ as depicted in Fig. 6 (c). Instead of a
single set of bit vector indices for the entire row, we partition the bit
vector and embed it in the head of each corresponding unit slice. Then we
align the slices to the burst boundaries. Using the in-place compression from
Section V-A for each slice, we allocate the memory space that can hold the
maximum number of non-zeros within them (i.e., a dense slice). With the right
choice of the unit slice size $C$, the wasted amount of memory access can be
minimized because the number of non-zero elements has a small variance and
there are only a few outliers. When a larger slice size is desired, we can
simply combine multiple unit slices to form a large logical slice, which
incurs almost no difference compared to having a large slice in the first
place. In the default design of SGCN, we empirically set $C=96$, which would
occupy 384 bytes in single precision features, and with around 50% sparsity it
fits into two or three cachelines along with the embedded bitmap indices.

Figure 7: (a) Conventional method, (b) density heatmap from adjacency matrices
of the NELL and DBLP graph, and (c) sparsity-aware cooperation assuming
2$\times$2 tiling.

###  V-C Sparsity-Aware Cooperation for Graph Topology Tiling

Another promising technique for GCN execution is graph topology tiling [99,
47, 17]. Partitioning the adjacency matrix into multiple tiles helps reduce
the working set size of the intermediate features such that it fits into the
cache size. Existing approaches usually find the optimal tile size based on an
off-line analysis, often by statically calculating the working set size [88,
47]. However, with SGCN, the level of sparsity varies dynamically depending on
each vertex, dataset, and layer. Because of this, estimating the optimal tile
size is very difficult, and a working set size exceeding the cache capacity
results in significant performance degradation.

Fig. 7a shows how conventional graph tiling works on an example of $2\times 2$
tiling. On the right side, it shows vertex IDs of the features that are
accessed for the first 300 reads. When a graph is partitioned into tiles, the
working set size is confined to the features of the vertices included in a
tile, which can fit into the cache. However, when the sparsity of the features
is lower than expected, the effective working set size increases because there
are more non-zeros per vertex. This has the risk of exceeding the cache
capacity, and the performance would quickly drop due to the thrashing pattern
[61, 95, 78].

To address this issue, we propose _sparsity-aware cooperation_ , a method that
alters the access pattern such that there are variously sized working sets
that can be captured by the caches. It is known that graphs often form
community clusters [19], and there exists a neighbor similarity between
adjacent vertices [7]. For example, the example density map from NELL [8] and
DBLP [72] displayed in Fig. 7b shows that adjacent rows tend to exhibit the
same patterns, and have strong clustering around the diagonals.

Sparsity-aware cooperation takes advantage of this, and each engine accesses a
small strip of vertices in an interleaved manner as illustrated in Fig. 7c.
For the height of strips, we empirically use 32. Because of the neighbor
similarity and clustering, the access distances tend to be shorter, and there
are multiple working sets with diverse sizes that can be captured. As a
result, when the sparsity level is high, the cache will capture the larger
working set window (denoted as ‘large window’), and when the sparsity is low,
the cache can capture a smaller working set window to avoid thrashing (denoted
as ‘small window’).

Figure 8: SGCN sparse aggregator unit microarchitecture.

###  V-D Sparse Aggregation

Fig. 8 reveals the microarchitecture of the sparse aggregator unit in SGCN and
its execution procedure. Each sparse aggregator of SGCN has 16 multipliers,
which can process a single cache line worth of data together. 1 When a row of
the feature matrix $\mathit{X}$ is selected, its first 64 bytes are fetched to
the aggregation engine, where its head contains the bitmaps and the rest
contains the non-zero values. 2 The non-zero values are multiplied with the
corresponding edge weight of $\mathit{\tilde{A}}$ broadcasted each multiplier.
$\leavevmode\hbox to9.67pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
4.83623pt\lower-4.83623pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}^{\prime}$ In
parallel, the bitmap is processed by a parallel prefix sum unit to convert the
1’s in the bitmap to a reversed index to the non-zero values. 3 The bitmap and
the reversed indices are sent to the accumulator. If the bitmap value is 1,
the accumulators at the corresponding positions load the multiplier outputs
and add them to the current value. 4 When the accumulation for a single vertex
is complete, it is sent to the combination engine for performing combination,
ReLU, and compression. 5 (Optional) When there are still non-zeros remaining
in the next cacheline (identified by the prefix sum result), the next 64 bits
are fetched to perform 1\- 4 again.

Figure 9: SGCN compressor unit microarchitecture.

###  V-E Post-Combination Compression

Fig. 9 illustrates the compressor unit in SGCN and the compression process. To
avoid the extra memory access for the compression, we place the compressor at
the output stage of the combination engine using an output-stationary systolic
array. One compressor entry containing BEICSR buffer and compression logic is
assigned to each row of the systolic array. 1 When the combination phase is
complete, the data are streamed to the compressor after processing the
residual addition and the ReLU activation. 2 The compression logic checks
whether the output value is zero. 3 If the output value is zero, the bitmap
index in the compression entry appends a ‘0’. $\leavevmode\hbox to9.67pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 4.83623pt\lower-4.83623pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.63623pt}{0.0pt}\pgfsys@curveto{4.63623pt}{2.56055pt}{2.56055pt}{4.63623pt}{0.0pt}{4.63623pt}\pgfsys@curveto{-2.56055pt}{4.63623pt}{-4.63623pt}{2.56055pt}{-4.63623pt}{0.0pt}\pgfsys@curveto{-4.63623pt}{-2.56055pt}{-2.56055pt}{-4.63623pt}{0.0pt}{-4.63623pt}\pgfsys@curveto{2.56055pt}{-4.63623pt}{4.63623pt}{-2.56055pt}{4.63623pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}^{\prime}$ When the
output value is non-zero, the bitmap index accumulates a ‘1’, and 4 the output
value is saved to the location pointed by the counter. The compressor
continuously performs 1\- 4 for each output value from the systolic array. 5
After the compressor has processed a unit slice amount of data, the data
stored in the buffer is flushed to the DRAM, and the compressor is re-
initialized.

###  V-F Putting It All Together

Fig. 10 presents the overall procedure of SGCN on top of the baseline
architecture ( Fig. 5). The sparse aggregator unit takes $\mathit{\tilde{A}}$,
the graph topology in CSR format, and $\mathit{X^{l}}$ in BEICSR format from
the output of the previous layer. Similar to [80, 51, 88], we use row-product-
based dataflow, and apply tiling for both the graph topology
$\mathit{\tilde{A}}$ and feature $\mathit{X^{l}}$ as in [51, 88, 47]. The
resulting $\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ will be dense, because each
row of $\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ will be a weighted sum of
several rows from $\mathit{X^{l}}$.

Figure 10: SGCN execution flow for a GCN layer.

After a block of $\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ is calculated from
the sparse aggregator unit, it will be sent to the systolic-array-based
combination engine. The systolic array will multiply
$\mathit{\tilde{A}}\cdot\mathit{X^{l}}$ with $\mathit{W^{l}}$, which is
essentially a GeMM operation. To perform the residual addition, the registers
at the systolic arrays are initialized with $S^{l}$ instead of zero. When a
sliced row of $\mathit{\tilde{A}}\cdot\mathit{X^{l}}\cdot\mathit{W^{l}}$ is
calculated, it is fed to the compressor unit after being activated by ReLU.
The output of ReLU activation is the next layer’s input feature $X^{l+1}$.
Before being written to the memory, the post-combination compression unit
converts the row of $X^{l+1}$ into the BEICSR format. In modern GCN
architectures, the input and output feature widths are often the same [10,
43]. In such cases, $\mathit{X}^{\prime}$ consumes the same capacity with
$\mathit{\tilde{A}}\cdot\mathit{X}$, and compressed $\mathit{X}^{\prime}$ is
written in place of $\mathit{\tilde{A}}\cdot\mathit{X}$ to reduce the memory
requirement.

Optionally, when the input feature ($X^{1}$) is extremely sparse, the
combination of the first layer is performed on the sparse aggregator engine
instead to take advantage of the sparse input features. Even though this
technique only applies to the first layer, this brings a meaningful speedup to
some datasets. SGCN does not require much additional implementation cost from
the baseline GCN accelerator. For the sparse aggregator units, only the
additional prefix sum units are required for reading the bitmap index. For the
SGCN compressor units, the global counter and non-zero comparators are added
to the basic combination unit to write the bitmap index in addition to the
features.

##  VI Evaluation

###  VI-A Experimental Setup

TABLE II: Benchmark Dataset Information

Dataset | #Vertices | #Edges |  #Input Features | Topology | Feature |  Sparsity (w/ 28 layers) |  Accuracy (w/ 28 layers)
---|---|---|---|---|---|---|---
Cora (CR) | 0.003 M | 0.01 M | 1,433 | 0.09 MB | 0.01 GB | 66.1 % | 76 %
CiteSeer (CS) | 0.003 M | 0.009 M | 3,703 | 0.08 MB | 0.05 GB | 69.7 % | 66 %
PubMed (PM) | 0.02 M | 0.09 M | 500 | 0.75 MB | 0.04 GB | 70.7 % | 77 %
NELL (NL) | 0.07 M | 0.25 M | 61,278 | 2.17 MB | 15.0 GB | 51.0 % | 64 %
Reddit (RD) | 232 M | 115 M | 602 | 875 MB | 0.52 GB | 58.4 % | 95 %
Flickr (FK) | 0.09 M | 0.90 M | 500 | 7.21 MB | 0.17 GB | 46.5 % | 48 %
Yelp (YP) | 716 M | 14.0 M | 300 | 109 MB | 0.80 GB | 64.0 % | 54 %
DBLP (DB) | 0.02 M | 0.11 M | 1,639 | 0.87 MB | 0.11 GB | 59.5 % | 86 %
GitHub (GH) | 0.04 M | 0.58 M | 128 | 4.55 MB | 0.02 GB | 44.6 % | 86 %

TABLE III: System Configuration Accelerator Engine | Frequency | 1GHz
---|---|---
Combination | 32$\times$32 Syst. Array
Aggregation | 16-Way SIMD
#Engines | Aggregation | 8
Combination | 8
Global Cache | Capacity | 512KB
Ways | 16
Replacement | LRU
Off-chip Memory | Spec. | HBM2
Peak Bandwidth | 256 GB/s
Channels | 8
Banks | 4$\times$4
Figure 11: Performance comparison of GCN accelerators.

We chose nine real-world graph datasets from various sources, listed in Table
II. As sparsity of the actual trained model is essential for SGCN, we trained
28-layer GCNs with residual connection and 256 features per vertex by these
datasets based on practices of [44, 45].

Cora (_CR)_ , CiteSeer (_CS_), PubMed (_PM_), DBLP (_DB_) are citation network
graphs from [68, 72]. Each node (document) is linked with others and has a
feature vector consisting of bag-of-words. NELL (_NL)_ [8] is a knowledge
graph from the Never-Ending Language Learning project. Each node has a one-hot
vector of length 61,278. Reddit (_RD_) [81] is a graph often used for GCN
kernel evaluation. Flickr (_FK)_ [42] is an image relationship graph, and each
node has the description and properties of an image as features. Yelp (_YP_)
is a social relationship graph that has customer reviewers as nodes and their
relationships as a link. For YP, we followed [90] while preprocessing. GitHub
(_GH_) [64] is a code hosting relationship graph. We used original features
from these datasets.

We performed the evaluation using the accelerator architecture explained in
Section III-B, Section V-D and Section V-E. The system configurations are
summarized in Table III. Following [47], we used a 512KB global cache unless
otherwise stated. The accelerator runs at 1 GHz. The accelerator has
32$\times$32 systolic array-based combination engines and the sparse
aggregation engines from Section V-D, with 32bit fixed points for both
features and weights.

We designed the accelerator using Verilog HDL and synthesized it using
Synopsys Design Compiler with the 45 $\text{\,}\mathrm{nm}$ OpenPDK library
and scaled it to 32 $\text{\,}\mathrm{nm}$ to match the tech node of the on-
chip memory model. For the on-chip caches, we used CACTI 6.5 [73] to estimate
the area and power consumption because of the lack of a memory cell library.
The baseline chip area of GCNAX is 3.95 $\text{\,}{\mathrm{mm}}^{2}$, and the
area of the accelerator with SGCN is 4.05 $\text{\,}{\mathrm{mm}}^{2}$, which
has 2.5% overhead on the area, accounting for the increased logic in sparse
aggregation and compression engines. We validated that it functioned correctly
and drew the area and power consumption values. For comparison, our reproduced
AWB-GCN consumed 4.25 $\text{\,}{\mathrm{mm}}^{2}$ due to the complicated
logic.

To measure performance, we designed a cycle-accurate simulator written in C++.
The model is based on SCALE-Sim [67] for the systolic array used in the
combination engine, which we extended with an in-house module for the sparse
aggregation engine and compression engine. The execution cycle of the
computation modules has been validated with the HDL design at the cycle level.
For modeling the DRAM subsystem, we use DRAMsim3 [50] with an HBM2 module.

###  VI-B Fast and Energy-Efficient GCN Executions

Performance. Fig. 11 demonstrates that SGCN outperforms existing GCN
accelerators by a great margin. In Fig. 11, the performance of SGCN is
compared with the previous methodologies. HyGCN [80] is based on row product
execution with hybrid engines. EnGN [51] uses vertex tiling and degree-aware
vertex caching (DAVC) to cache high-degree vertices explicitly. AWB-GCN [17]
employs column-product-based execution and applies aggressive load-balancing
techniques. In addition, I-GCN [18] adopts dynamic reordering to enhance the
locality of the graph topology. Moreover, GCNAX [47] is based on perfect
tiling and suggests optimized loop ordering based on off-line analysis. Among
those, we choose GCNAX as the baseline and report normalized speedups because
it shows successful performance over existing accelerators and uses the most
similar tiling approach to SGCN.

The results show that SGCN achieves 1.66$\times$ speedup over baseline GCNAX
in geometric mean, and 2.71$\times$ over HyGCN. Because GCNAX employs
aggressive tiling for both the topology ($\mathit{\tilde{A}}$) and the
intermediate features ($\mathit{X}$), the speedup of SGCN is mostly from
exploiting the feature sparsity. The speedup over HyGCN is mainly coming from
two factors: Reduced amount of DRAM accesses due to the usage of BEICSR
format, and cache efficiency from graph/feature tiling. Because HyGCN does not
perform any tiling/slicing, it suffers from a low cache efficiency for large
graphs. AWB-GCN adopts zero skipping on the features, which is a kind of
sparsity-aware method. However, AWB-GCN stores the features in a dense format
that yields no benefit to the memory traffic. Moreover, it uses the sparsity
of the features only in the combination phase which only takes a small portion
of the total GCN execution. By adopting a sparse format to reduce the memory
traffic, SGCN outperforms AWB-GCN by 1.73$\times$ in geometric mean. SGCN also
achieves 1.85$\times$ speedup compared to EnGN. The degree-aware vertex cache
used in EnGN is effective over HyGCN, but its limited vertex tiling still
makes lower cache efficiency, so SGCN has an extra advantage over EnGN.

Over the baseline, a large speedup was observed on PubMed and NELL dataset
with 1.91$\times$ and 1.99$\times$ improvement over GCNAX, respectively. The
PubMed dataset exhibits high intermediate feature sparsity of almost 70% (see
Fig. 2), which translates to a high speedup in the aggregation phase. On the
other hand, NELL dataset shows relatively lower feature sparsity. However, its
input feature width is exceptionally long (61,278) and is also ultra-sparse
(99.9%) because the input features are one-hot encoded vectors. Thus, this
unique input layer brings additional speedup, besides the speedup from the
intermediate features. On the other hand, speedup numbers from Cora and
CiteSeer are similar to the geomean, despite its relatively high sparsity. The
reason is partially from the small dataset. When the graph topology is small,
the relative portion of the combination phase increases, which amortizes the
gain coming from the sparse aggregation. In addition, the average degrees of
the two graphs are very low with 3.92 for Cora and 2.76 for CiteSeer where
geomean is 10.15 and the maximum is around 500 with Reddit. This means that
the number of random accesses to the features is smaller than the other
datasets, which also contributes to the amortization of the gain in sparse
aggregation.

Ablation Study. Fig. 12 displays how each proposed technique contributes to
the performance gain of SGCN. Using GCNAX as the baseline, we first apply the
non-sliced version of BEICSR. The non-sliced version of BEICSR is already
enough to exploit the intermediate feature sparsity, but settles at suboptimal
dataflow due to the lack of feature matrix slicing. As a result, the
performance gain is often not large enough. The geometric mean performance
gain is 20.8%.

Figure 12: Ablation study.

When the feature matrix slicing is supported with the sliced version of
BEICSR, sparsity is exploited on the optimal dataflow. The geometric mean
speedup is 38.5% from the baseline, which adds 17.7% on top of the non-sliced
BEICSR.

Lastly, we add sparsity-aware cooperation to better capture the varying
locality of the sparse features. This adds the extra 28.0% speedup in the
geometric mean, which results in an overall 1.66$\times$ speedup. Sparsity-
aware cooperation adds more gain in graphs with more clustered topology (DB)
and high neighbor similarity (PM, RD).

Figure 13: SGCN energy consumption breakdown.

Energy Consumption. Fig. 13 shows the advantage of energy consumption. SGCN
consumes 44.1% less energy compared to GCNAX, 44.6%, and 58.1% compared to
AWB-GCN and HyGCN, respectively. The energy savings come from all three parts
of the stack. Much of the energy consumption comes from memory accesses.
Because the aggregation phase requires fewer data due to the sparsity, it
affects both the off-chip memory and cache access counts. In addition, the
reduced number of multiplications in the aggregation contributes to the energy
reduction of the computation. For the peak power, SGCN consumes
6.74$\mathrm{W}$, which is less than AWB-GCN (7.03$\mathrm{W}$) and GCNAX
(7.16$\mathrm{W}$). However, it shows higher peak power consumption compared
to HyGCN (5.94$\mathrm{W}$) which has slow but simple architecture.

Figure 14: Off-chip memory access breakdown of Reddit (RD).

Memory Access Breakdown. Fig. 14 plots the breakdown of the memory accesses
during the execution of the RD dataset. In HyGCN, most of the accesses are to
the feature. Because it does not use tiling nor utilize the feature sparsity,
a lot of duplicate accesses are done to the features which comprise most of
the memory access of HyGCN. EnGN reduced some accesses with its degree-aware
vertex cache (DAVC). On the other hand, AWB-GCN is based on a column-product
dataflow, and it reads each input feature element exactly once. However, the
expense is that it requires reading and writing the partial sums more often,
which becomes dominating for the memory accesses. GCNAX has balanced memory
access with aggressive tiling. I-GCN also shows balanced memory access due to
its well-clustered reordering scheme. In contrast, SGCN dramatically reduces
the amount of memory access. The main reduction comes from the sparse feature
representation, which reduces the feature access by 54.3%.

###  VI-C Sensitivity Studies

Figure 15: Sensitivity on the number of layers and cache size.

Number of GCN Layers. In Fig. 15a we plot the geometric averaged performance
sensitivity to the number of layers in GCN using CR, CT, and PM datasets. In
addition to the default setting of 28 layers, we used 7- to 112-layer GCNs
widely used in [44, 45]. In all settings, the sparsity remains mostly
constant, and the speedup trend persists. This shows that the performance gain
from SGCN is not fine-tuned on a certain number of layers, and can be broadly
used for various specifications.

Cache Size. Fig. 15b plots the trend of a speedup as the cache size increases.
In general, the speedup from the sparsity of features is not greatly affected
by the cache size unless the data entirely fits into the cache. With a small
cache, the benefit of sparsity-aware cooperation becomes marginal because it
becomes harder to capture any locality. However, even with larger caches, the
speedup remains relatively consistent.

Figure 16: Performance on (a) GINConv and (b) GraphSAGE.

GCN Variants. Fig. 16 depicts the performance result comparison on two
additional variants of GCN aggregation: GINConv [79] and GraphSAGE [22]. In
both variants, SGCN achieves similar but slightly different speedup from those
in Fig. 11. Unlike the GCN aggregation [37], the aggregation phase of GINConv
does not require the edge weights. This decreases the size of
$\mathit{\tilde{A}}$, and leads to an increase in the portion of the feature
matrix during the aggregation. Because SGCN can efficiently reduce the
accesses to the feature matrix, the speedup slightly increases compared to
that of the vanilla GCN. On the contrary, GraphSAGE applies random sampling on
the edges to reduce the computational overhead. It reduces the effective edge
count of the graph topology and reduces the portion of aggregation. Thus, SGCN
experiences slightly less, but still significant speedup over the prior arts.
In GINConv, SGCN achieves 1.69$\times$ speedup over GCNAX and 2.57$\times$
against HyGCN. In GraphSAGE, SGCN achieves 1.53$\times$ and 2.27$\times$
speedup over GCNAX and HyGCN, respectively.

Figure 17: SGCN slice unit size sensitivity.

Choice of Slice Size. Another implication of the use of in-place compression
with the support for feature matrix slicing is that the speedup can vary
depending on the choice of the unit slice size $C$. When the slice width is
too large, there is a risk of too many slices occupying the extra cache lines.
Because this would fetch a lot of invalid data together from the region, it
degrades the memory efficiency. On the other hand, if $C$ is too small, the
number of slices increases, which affects the amount of output feature
accesses. Even though the number of extra cache line access will be small,
this could increase the execution time. Nonetheless, Fig. 17 shows that the
performance is not very sensitive to the slice size within the range of $C=32$
to $C=256$. According to the experiment, the best performance overall is at
$C=96$, but a poor choice still provides a great amount of speedup over the
baseline.

Figure 18: SGCN memory type and scalability.

Scalability. Fig. 18 shows how SGCN scale with the varying number of engines,
with different memory modules (HBM1 and HBM2) used. We distributed the
computation to multiple engines. When enough bandwidth is provided, increasing
the number of engines provides an almost linear amount of speedup up to around
eight engines, demonstrating good scalability. The scalability starts
saturating at around 16 engines, which is where the system reaches near the
maximum bandwidth of the memory module.

Figure 19: Performance comparison on various feature sparsity.

##  VII Discussion

###  VII-A Range of Sparsity

Based on the observations of Section II, we designed the BEICSR targeting
sparsity around 50%. In fact, all the real-world datasets we examined exhibit
the intermediate sparsity between 40% and 80%, where we found SGCN to be
highly beneficial. Nonetheless, it should be answered which range of sparsity
BEICSR has an advantage over the existing techniques. Although highly
artificial, we plot the geomean speedup of SGCN over various sparsity levels
in Fig. 19. We randomly generated the synthetic input activations of each
layer with target sparsity. As displayed, SGCN shows better performance on
almost all sparsity ranges. The dense format is better only on sparsity under
5%, because of the additional bitmap indices needed for BEICSR. The break-even
point for CSR is at over 90% sparsity, which is the point where the size of
the column indices in CSRs becomes smaller than the bitmap indices of BEICSR.

###  VII-B Applicability to Future GCNs

As demonstrated in Fig. 19, SGCN is beneficial over a wide range of sparsity.
We would like to argue that the future trend would place the sparsity level in
a similar range. The sparsity of activations is caused by the wide use of ReLU
functions. With normalized values, the after-ReLU distribution will have a
near-zero mean, leading to $\sim$50% sparsity. Therefore, even if GCNs evolve
to have distinct characteristics, the sparsity level is unlikely to change
towards the extreme levels.

One exception is the input layer, which is often human-designed features. If
the input features of the first layer take a one-hot vector format, sparsity
can be extremely high as in NELL [8]. In this case, using CSR format for input
features can be better, and SGCN performs combination using the aggregation
engine which is designed to handle CSR formats. However, the benefit of such a
technique is often amortized over tens of layers and hence does not have a
significant impact.

##  VIII Related Work

###  VIII-A GCN Accelerators

As GCNs become popular as a critical application domain, the hardware
acceleration of GCNs has recently drawn interest from the architecture
community. HyGCN [80] claimed the need for GCN accelerators and discussed a
few crucial characteristics, such as the hybrid computation pattern and
interlayer optimization. Moreover, GNNA [6] proposed a tiled architecture for
GCN acceleration based on such hybrid architectures. EnGN [51] discussed the
need for tiling the topology and proposed efficient tile ordering using a
dedicated cache for high-degree vertices. AWB-GCN [17] proposed using column-
based execution and applied several load-balancing techniques. GCNAX [47] is a
flexible architecture with an optimal dataflow/buffer configuration found
based on perfect tiling. However, perfect tiling overprovisions the required
amount of buffer and leads to suboptimal performance. Moreover, the authors
assumed a uniform random distribution of the sparse data, which often does not
match the actual distribution. SnF [87] addresses the issues of perfect tiling
and offline analysis from GCNAX by using a dynamic tiling strategy. By
exploiting the repetitive access pattern from feature tiling, it proposes
online dynamic and non-perfect topology tiling. I-GCN [18] suggests a dynamic
re-ordering scheme called islandization based on a breadth-first search. In
addition, it reuses the overlapping computations within the aggregation phase
to reduce the computational complexity. A similar approach has been extended
in ReGNN [9], which identifies several redundancies in aggregation and edge
updates to further optimize performance. It is also worth noting GCoD [89],
which is a co-design approach for GCNs. Similar to pruning approaches for DNNs
[39], GCoD prunes, clusters the adjacency matrix, and separately process the
dense region and sparse region. However, such methods require retraining of
the GCN, and thus can be used when the user can afford the training.

###  VIII-B Graph Processing Accelerators

Graph processing forms a vital application domain, and many accelerators have
been proposed, based on ASICs [21, 55, 86], FPGAs [40, 13, 5], or both [11].
Because of their high bandwidth requirements, graph processing often becomes a
primary target for processing-in-memory [1, 92, 100] or processing-in-storage
[53, 34]. Tesseract [1] uses the internal bandwidth of HMCs [58] to boost
graph processing, which was later refined with better partitioning [92] or
execution alignment [100]. GraphSSD is an SSD aware of the graph structures,
and GraFboost [34] puts an FPGA accelerator for sort-and-reduce within the
storage device for graph processing. However, they primarily target classic
graph processing and are not optimized for GCN execution, especially on the
sparsity of the per-vertex features.

###  VIII-C Sparse DNNs

Another stream of related work is on sparse DNN accelerators. Due to pruning
and ReLU activation function, many of the weights or the activations become
zeros, providing opportunities for optimization. Some prior studies design a
computation pruning scheme which is friendly to existing hardware [26, 54,
69]. [98, 76] are extensions to TensorCores that support sparse operations.
There are also some designs that eliminate zero-value weights [23, 94, 97, 2,
14] or consider zero-value activations [56, 20, 33, 30]. Some target sparse
tensor algebra, targeted to SpMV [65, 4] and SpMM [96, 24, 60]. RingCNN [27]
uses ring algebra for algebraic sparsity. In addition, some approaches propose
software-hardware co-design of tensor compression [36, 71, 59, 85]. However,
these methods primarily target the conventional CNNs, or embedding layers
whose characteristics greatly differ from that of GCNs. To the extent of our
knowledge, this is the first work on GCN accelerators that proposes techniques
for exploiting sparsity in the features.

###  VIII-D Memory Bandwidth Optimization for DNN Execution

Memories are known to be important factors of DNN accelerators [62, 29, 70],
and optimizations focused on memory bandwidth are often crucial to
performance. One popular method is to optimize the on-chip memory usage. Many
accelerators adopt different dataflows [15, 12, 32],

and some researchers have claimed that data blocking is more important [84].
In a similar sense, some work has focused on the management of on-chip
memories [77, 48, 31]. Another direction is to take advantage of the multi-
layered nature of DNNs. By keeping inter-layer data in on-chip memory, the
bandwidth for off-chip traffic can be reduced [3, 28, 52, 35]. These methods
have been successfully applied to inference [3, 28], training [52], and batch
normalization [35]. Among many differences, we highlight that these techniques
focus on dealing with on-chip memory management, especially as a manually
managed scratchpad. methods are valid because of the highly regular memory
access pattern in conventional DNNs and fundamentally different from this
work. For GCN execution, irregular accesses from the graphs make it
challenging to adopt those common techniques from existing DNN accelerators.

##  IX Conclusion

We proposed SGCN, a GCN accelerator that exploits the sparsity of intermediate
features. With the advance in GCNs towards deep, residual layers, there
appears a huge potential from the intermediate feature sparsity that was
unavailable from traditional shallow GCNs.

In such circumstances, we present for the first time, exploiting sparsity in
the feature data to optimize the memory traffic from the GCN execution. We
first identify that a naïve attempt to utilize the feature sparsity could
rather result in speed degradation. From the observation, we present BEICSR, a
sparse feature representation format designed for the sparse aggregation phase
of the GCN execution. In addition, we propose sparsity-aware cooperation, a
method for better dealing with the locality in the existence of varying
sparsity, with the change in the access patterns. The key ideas of the format
are using embedded bitmap indices, in-place compression, and supporting
feature slicing technique which is recently used in GCN accelerators. By
conducting a thorough evaluation, We demonstrate that SGCN achieves superior
performance and energy efficiency compared to the previous state-of-the-art
GCN accelerators.

## Acknowledgements

This work was partly supported by the National Research Foundation of Korea
(NRF) grants (2022R1C1C1011307, 2022R1C1C1008131) and Institute of Information
& communications Technology Planning & Evaluation (IITP) grants (2021-0-00853,
2020-0-01361) funded by the Korea government (MSIT). The EDA tool was
supported by the IC Design Education Center (IDEC), Korea. Mingi Yoo, Jaeyong
Song, Jounghoo Lee, and Youngsok Kim were partly supported by the BK21 FOUR
(Fostering Outstanding Universities for Research) funded by the Ministry of
Education (MOE, Korea) and National Research Foundation of Korea (NRF).

## References

  * [1] J. Ahn, S. Hong, S. Yoo, O. Mutlu, and K. Choi, “A scalable processing-in-memory accelerator for parallel graph processing,” in _ISCA_ , 2015.
  * [2] J. Albericio, P. Judd, T. Hetherington, T. Aamodt, N. E. Jerger, and A. Moshovos, “Cnvlutin: Ineffectual-neuron-free deep neural network computing,” in _ISCA_ , 2016.
  * [3] M. Alwani, H. Chen, M. Ferdman, and P. Milder, “Fused-layer CNN accelerators,” in _MICRO_ , 2016.
  * [4] B. Asgari, R. Hadidi, T. Krishna, H. Kim, and S. Yalamanchili, “ALRESCHA: A lightweight reconfigurable sparse-computation accelerator,” in _HPCA_ , 2020\.
  * [5] M. Asiatici and P. Ienne, “Large-scale graph processing on FPGAs with caches for thousands of simultaneous misses,” in _ISCA_ , 2021.
  * [6] A. Auten, M. Tomei, and R. Kumar, “Hardware acceleration of graph neural networks,” in _DAC_ , 2020.
  * [7] P. Boldi and S. Vigna, “The webgraph framework I: Compression techniques,” in _WWW_ , 2004.
  * [8] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. Hruschka, and T. M. Mitchell, “Toward an architecture for never-ending language learning,” in _AAAI_ , 2010.
  * [9] C. Chen, K. Li, Y. Li, and X. Zou, “ReGNN: A Redundancy-Eliminated Graph Neural Networks Accelerator,” in _HPCA_ , 2022.
  * [10] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, “Simple and deep graph convolutional networks,” in _ICML_ , 2020.
  * [11] X. Chen, T. Huang, S. Xu, T. Bourgeat, C. Chung, and Arvind, “FlexMiner: A pattern-aware accelerator for graph pattern mining,” in _ISCA_ , 2021.
  * [12] Y.-H. Chen, T. Krishna, J. S. Emer, and V. Sze, “Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks,” _JSSC_ , 2016.
  * [13] V. Dadu, S. Liu, and T. Nowatzki, “PolyGraph: Exposing the value of flexibility for graph processing accelerators,” in _ISCA_ , 2021.
  * [14] C. Ding, S. Liao, Y. Wang, Z. Li, N. Liu, Y. Zhuo, C. Wang, X. Qian, Y. Bai, G. Yuan, X. Ma, Y. Zhang, J. Tang, Q. Qiu, X. Lin, and B. Yuan, “CirCNN: Accelerating and compressing deep neural networks using block-circulant weight matrices,” in _MICRO_ , 2017.
  * [15] Z. Du, R. Fasthuber, T. Chen, P. Ienne, L. Li, T. Luo, X. Feng, Y. Chen, and O. Temam, “ShiDianNao: Shifting vision processing closer to the sensor,” in _ISCA_ , 2015.
  * [16] A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, “Protein interface prediction using graph convolutional networks,” in _NeurIPS_ , 2017.
  * [17] T. Geng, A. Li, R. Shi, C. Wu, T. Wang, Y. Li, P. Haghi, A. Tumeo, S. Che, S. Reinhardt, and M. C. Herbordt, “AWB-GCN: A graph convolutional network accelerator with runtime workload rebalancing,” in _MICRO_ , 2020.
  * [18] T. Geng, C. Wu, Y. Zhang, C. Tan, C. Xie, H. You, M. C. Herbordt, Y. Lin, and A. Li, “I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization,” in _MICRO_ , 2021.
  * [19] M. Girvan and M. E. Newman, “Community structure in social and biological networks,” _Proceedings of the national academy of sciences_ , 2002.
  * [20] A. Gondimalla, N. Chesnut, M. Thottethodi, and T. N. Vijaykumar, “SparTen: A sparse tensor accelerator for convolutional neural networks,” in _MICRO_ , 2019.
  * [21] T. J. Ham, L. Wu, N. Sundaram, N. Satish, and M. Martonosi, “Graphicionado: A high-performance and energy-efficient accelerator for graph analytics,” in _MICRO_ , 2016.
  * [22] W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _NeurIPS_ , 2017.
  * [23] S. Han, X. Liu, H. Mao, J. Pu, A. Pedram, M. A. Horowitz, and W. J. Dally, “EIE: Efficient inference engine on compressed deep neural network,” in _ISCA_ , 2016.
  * [24] K. Hegde, H. Asghari-Moghaddam, M. Pellauer, N. Crago, A. Jaleel, E. Solomonik, J. Emer, and C. W. Fletcher, “ExTensor: An accelerator for sparse tensor algebra,” in _MICRO_ , 2019.
  * [25] I. Higgins, D. Amos, D. Pfau, S. Racaniere, L. Matthey, D. Rezende, and A. Lerchner, “Towards a definition of disentangled representations,” _arXiv preprint_ , 2018.
  * [26] W. Hua, Y. Zhou, C. D. Sa, Z. Zhang, and G. E. Suh, “Boosting the performance of CNN accelerators with dynamic fine-grained channel gating,” in _MICRO_ , 2019.
  * [27] C.-T. Huang, “RingCNN: Exploiting algebraically-sparse ring tensors for energy-efficient CNN-based computational imaging,” in _ISCA_ , 2021.
  * [28] C.-T. Huang, Y.-C. Ding, H.-C. Wang, C.-W. Weng, K.-P. Lin, L.-W. Wang, and L.-D. Chen, “eCNN: A block-based and highly-parallel CNN accelerator for edge inference,” in _MICRO_ , 2019.
  * [29] B. Hyun, Y. Kwon, Y. Choi, J. Kim, and M. Rhu, “NeuMMU: Architectural support for efficient address translations in NPUs,” in _ASPLOS_ , 2020\.
  * [30] J.-W. Jang, S. Lee, D. Kim, H. Park, A. S. Ardestani, Y. Choi, C. Kim, Y. Kim, H. Yu, H. Abdel-Aziz, J.-S. Park, H. Lee, D. Lee, M. W. Kim, H. Jung, H. Nam, D. Lim, S. Lee, J.-H. Song, S. Kwon, J. Hassoun, S. Lim, and C. Choi, “Sparsity-aware and re-configurable NPU architecture for Samsung flagship mobile SoC,” in _ISCA_ , 2021.
  * [31] T. Jin and S. Hong, “Split-CNN: Splitting window-based operations in convolutional neural networks for memory system optimization,” in _ASPLOS_ , 2019.
  * [32] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, R. Boyle, P.-l. Cantin, C. Chao, C. Clark, J. Coriell, M. Daley, M. Dau, J. Dean, B. Gelb, T. V. Ghaemmaghami, R. Gottipati, W. Gulland, R. Hagmann, C. R. Ho, D. Hogberg, J. Hu, R. Hundt, D. Hurt, J. Ibarz, A. Jaffey, A. Jaworski, A. Kaplan, H. Khaitan, D. Killebrew, A. Koch, N. Kumar, S. Lacy, J. Laudon, J. Law, D. Le, C. Leary, Z. Liu, K. Lucke, A. Lundin, G. MacKean, A. Maggiore, M. Mahony, K. Miller, R. Nagarajan, R. Narayanaswami, R. Ni, K. Nix, T. Norrie, M. Omernick, N. Penukonda, A. Phelps, J. Ross, M. Ross, A. Salek, E. Samadiani, C. Severn, G. Sizikov, M. Snelham, J. Souter, D. Steinberg, A. Swing, M. Tan, G. Thorson, B. Tian, H. Toma, E. Tuttle, V. Vasudevan, R. Walter, W. Wang, E. Wilcox, and D. H. Yoon, “In-datacenter performance analysis of a tensor processing unit,” in _ISCA_ , 2017.
  * [33] P. Judd, A. Delmas, S. Sharify, and A. Moshovos, “Cnvlutin2: Ineffectual-activation-and-weight-free deep neural network computing,” _arXiv preprint_ , 2017.
  * [34] S.-W. Jun, A. Wright, S. Zhang, S. Xu, and Arvind, “GraFBoost: Using accelerated flash storage for external graph analytics,” in _ISCA_ , 2018\.
  * [35] D. Jung, W. Jung, B. Kim, S. Lee, W. Rhee, and J. H. Ahn, “Restructuring batch normalization to accelerate CNN training,” in _SysML_ , 2019.
  * [36] K. Kanellopoulos, N. Vijaykumar, C. Giannoula, R. Azizi, S. Koppula, N. M. Ghiasi, T. Shahroodi, J. G. Luna, and O. Mutlu, “Smash: Co-designing software compression and hardware-accelerated indexing for efficient sparse matrix operations,” in _MICRO_ , 2019.
  * [37] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint_ , 2016.
  * [38] H. Kwon, A. Samajdar, and T. Krishna, “Maeri: Enabling flexible dataflow mapping over dnn accelerators via reconfigurable interconnects,” in _ASPLOS_ , 2018.
  * [39] Y. LeCun, J. Denker, and S. Solla, “Optimal brain damage,” _NIPS_ , 1989.
  * [40] J. Lee, H. Kim, S. Yoo, K. Choi, H. P. Hofstee, G.-J. Nam, M. R. Nutter, and D. Jamsek, “ExtraV: Boosting graph processing near storage with a coherent accelerator,” _pVLDB_ , 2017.
  * [41] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graphs over time: Densification laws, shrinking diameters and possible explanations,” in _KDD_ , 2005.
  * [42] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford large network dataset collection,” http://snap.stanford.edu/data, 2014.
  * [43] G. Li, M. Müller, B. Ghanem, and V. Koltun, “Training graph neural networks with 1000 layers,” in _ICML_ , 2021.
  * [44] G. Li, M. Muller, A. Thabet, and B. Ghanem, “DeepGCNs: Can GCNs go as deep as CNNs?” in _ICCV_ , 2019.
  * [45] G. Li, C. Xiong, A. Thabet, and B. Ghanem, “Deepergcn: All you need to train deeper gcns,” _arXiv preprint_ , 2020.
  * [46] H. Li, M. Yan, X. Yang, L. Deng, W. Li, X. Ye, D. Fan, and Y. Xie, “Hardware acceleration for gcns via bidirectional fusion,” _IEEE CAL_ , 2021.
  * [47] J. Li, A. Louri, A. Karanth, and R. Bunescu, “GCNAX: A flexible and energy-efficient accelerator for graph convolutional neural networks,” in _HPCA_ , 2021.
  * [48] J. Li, G. Yan, W. Lu, S. Jiang, S. Gong, J. Wu, and X. Li, “SmartShuttle: Optimizing off-chip memory accesses for deep learning accelerators,” in _DATE_ , 2018.
  * [49] Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” in _AAAI_ , 2018.
  * [50] S. Li, Z. Yang, D. Reddy, A. Srivastava, and B. Jacob, “DRAMsim3: A cycle-accurate, thermal-capable DRAM simulator,” _IEEE CAL_ , 2020.
  * [51] S. Liang, Y. Wang, C. Liu, L. He, L. Huawei, D. Xu, and X. Li, “EnGN: A high-throughput and energy-efficient accelerator for large graph neural networks,” _TC_ , 2020.
  * [52] S. Lym, A. Behroozi, W. Wen, G. Li, Y. Kwon, and M. Erez, “Mini-batch serialization: CNN training with inter-layer data reuse,” in _SysML_ , 2019\.
  * [53] K. K. Matam, G. Koo, H. Zha, H.-W. Tseng, and M. Annavaram, “GraphSSD: Graph semantics aware SSD,” in _ISCA_ , 2019.
  * [54] W. Niu, X. Ma, S. Lin, S. Wang, X. Qian, X. Lin, Y. Wang, and B. Ren, “PatDNN: Achieving real-time DNN execution on mobile devices with pattern-based weight pruning,” in _ASPLOS_ , 2020.
  * [55] M. M. Ozdal, S. Yesil, T. Kim, A. Ayupov, J. Greth, S. Burns, and O. Ozturk, “Energy efficient architecture for graph analytics accelerators,” in _ISCA_ , 2016.
  * [56] A. Parashar, M. Rhu, A. Mukkara, A. Puglielli, R. Venkatesan, B. Khailany, J. Emer, S. W. Keckler, and W. J. Dally, “SCNN: An accelerator for compressed-sparse convolutional neural networks,” in _ISCA_ , 2017.
  * [57] A. Parashar, M. Rhu, A. Mukkara, A. Puglielli, R. Venkatesan, B. Khailany, J. Emer, S. W. Keckler, and W. J. Dally, “Scnn: An accelerator for compressed-sparse convolutional neural networks,” _ISCA_ , 2017.
  * [58] J. T. Pawlowski, “Hybrid memory cube (HMC),” in _Hot Chips_ , 2011.
  * [59] L. Pentecost, M. Donato, B. Reagen, U. Gupta, S. Ma, G.-Y. Wei, and D. Brooks, “MaxNVM: Maximizing DNN storage density and inference efficiency with sparse encoding and error mitigation,” in _MICRO_ , 2019.
  * [60] E. Qin, A. Samajdar, H. Kwon, V. Nadella, S. Srinivasan, D. Das, B. Kaul, and T. Krishna, “SIGMA: A sparse and irregular GEMM accelerator with flexible interconnects for DNN training,” in _HPCA_ , 2020.
  * [61] M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, and J. Emer, “Adaptive insertion policies for high performance caching,” in _ISCA_ , 2007.
  * [62] M. Rhu, N. Gimelshein, J. Clemons, A. Zulfiqar, and S. W. Keckler, “vDNN: Virtualized deep neural networks for scalable, memory-efficient neural network design,” in _MICRO_ , 2016.
  * [63] M. Rhu, M. O’Connor, N. Chatterjee, J. Pool, Y. Kwon, and S. W. Keckler, “Compressing dma engine: Leveraging activation sparsity for training deep neural networks,” in _HPCA_ , 2018.
  * [64] B. Rozemberczki, C. Allen, and R. Sarkar, “Multi-Scale Attributed Node Embedding,” _Journal of Complex Networks_ , 2021.
  * [65] F. Sadi, J. Sweeney, T. M. Low, J. C. Hoe, L. Pileggi, and F. Franchetti, “Efficient SpMV operation for large and highly sparse matrices using scalable multi-way merge parallelization,” in _MICRO_ , 2019.
  * [66] S. Salman and X. Liu, “Sparsity as the implicit gating mechanism for residual blocks,” in _IJCNN_ , 2019.
  * [67] A. Samajdar, Y. Zhu, P. Whatmough, M. Mattina, and T. Krishna, “SCALE-Sim: Systolic CNN accelerator simulator,” _arXiv preprint_ , 2018.
  * [68] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” _AI magazine_ , 2008.
  * [69] F. Silfa, G. Dot, J.-M. Arnau, and A. Gonazàlez, “Neuron-level fuzzy memoization in RNNs,” in _MICRO_ , 2019.
  * [70] K. Siu, D. M. Stuart, M. Mahmoud, and A. Moshovos, “Memory Requirements for Convolutional Neural Network Hardware Accelerators,” in _IISWC_ , 2018.
  * [71] N. Srivastava, H. Jin, S. Smith, H. Rong, D. Albonesi, and Z. Zhang, “Tensaurus: A versatile accelerator for mixed sparse-dense tensor computations,” in _HPCA_ , 2020.
  * [72] J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su, “Arnetminer: Extraction and mining of academic social networks,” in _KDD_ , 2008.
  * [73] S. Thoziyoor, N. Muralimanohar, J. H. Ahn, and N. P. Jouppi, “CACTI 5.1,” 2008-20, HP Labs, Tech. Rep., 2008.
  * [74] K. Ueno, T. Suzumura, N. Maruyama, K. Fujisawa, and S. Matsuoka, “Extreme scale breadth-first search on supercomputers,” in _Big Data_ , 2016.
  * [75] S. Vashishth, “Neural graph embedding methods for natural language processing,” _arXiv preprint_ , 2019.
  * [76] Y. Wang, C. Zhang, Z. Xie, C. Guo, Y. Liu, and J. Leng, “Dual-side sparse Tensor Core,” in _ISCA_ , 2021.
  * [77] X. Wei, Y. Liang, and J. Cong, “Overcoming Data Transfer Bottlenecks in FPGA-based DNN Accelerators via Layer Conscious Memory Management,” in _DAC_ , 2019.
  * [78] C.-J. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. C. Steely Jr, and J. Emer, “SHiP: Signature-based hit predictor for high performance caching,” in _MICRO_ , 2011.
  * [79] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” _arXiv preprint_ , 2018.
  * [80] M. Yan, L. Deng, X. Hu, L. Liang, Y. Feng, X. Ye, Z. Zhang, D. Fan, and Y. Xie, “HyGCN: A gcn accelerator with hybrid architecture,” in _HPCA_ , 2020\.
  * [81] P. Yanardag and S. Vishwanathan, “Deep graph kernels,” in _KDD_ , 2015.
  * [82] C. Yang, R. Wang, S. Yao, S. Liu, and T. Abdelzaher, “Revisiting over-smoothing in deep gcns,” _arXiv preprint_ , 2020.
  * [83] J. Yang, J. Lu, S. Lee, D. Batra, and D. Parikh, “Graph r-cnn for scene graph generation,” in _ECCV_ , 2018.
  * [84] X. Yang, M. Gao, J. Pu, A. Nayak, Q. Liu, S. E. Bell, J. O. Setter, K. Cao, H. Ha, C. Kozyrakis, and M. Horowitz, “DNN dataflow choice is overrated,” _arXiv preprint_ , 2018.
  * [85] Y. Yang, J. Emer, and D. Sánchez, “SpZip: Architectural support for effective data compression in irregular applications,” in _ISCA_ , 2021.
  * [86] P. Yao, L. Zheng, Z. Zeng, Y. Huang, C. Gui, X. Liao, H. Jin, and J. Xue, “A locality-aware energy-efficient accelerator for graph mining applications,” in _MICRO_ , 2020.
  * [87] M. Yoo, J. Song, H. Lee, J. Lee, N. Kim, Y. Kim, and J. Lee, “Slice-and-Forge: Making Better Use of Caches for Graph Convolutional Network Accelerators,” in _PACT_ , 2022.
  * [88] M. Yoo, J. Song, J. Lee, N. Kim, Y. Kim, and J. Lee, “Making a Better Use of Caches for GCN Accelerators with Feature Slicing and Automatic Tile Morphing,” _IEEE CAL_ , 2021.
  * [89] H. You, T. Geng, Y. Zhang, A. Li, and Y. Lin, “Gcod: Graph convolutional network acceleration via dedicated algorithm and accelerator co-design,” _arXiv preprint_ , 2021.
  * [90] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna, “GraphSAINT: Graph sampling based inductive learning method,” in _ICLR_ , 2020.
  * [91] J. Zhang and L. Gruenwald, “Regularizing irregularity: Bitmap-based and portable sparse matrix multiplication for graph data on gpus,” in _GRADES-NDA_ , 2018.
  * [92] M. Zhang, Y. Zhuo, C. Wang, M. Gao, Y. Wu, K. Chen, C. Kozyrakis, and X. Qian, “GraphP: Reducing communication for PIM-based graph processing with efficient data partition,” in _HPCA_ , 2018.
  * [93] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” in _NeurIPS_ , 2018.
  * [94] S. Zhang, Z. Du, L. Zhang, H. Lan, S. Liu, L. Li, Q. Guo, T. Chen, and Y. Chen, “Cambricon-X: An accelerator for sparse neural networks,” in _MICRO_ , 2016.
  * [95] X. Zhang, C. Li, H. Wang, and D. Wang, “A cache replacement policy using adaptive insertion and re-reference prediction,” in _ISCA_ , 2010.
  * [96] Z. Zhang, H. Wang, S. Han, and W. J. Dally, “SpArch: Efficient architecture for sparse matrix multiplication,” in _HPCA_ , 2020.
  * [97] X. Zhou, Z. Du, Q. Guo, S. Liu, C. Liu, C. Wang, X. Zhou, L. Li, T. Chen, and Y. Chen, “Cambricon-S: Addressing irregularity in sparse neural networks through a cooperative software/hardware approach,” in _MICRO_ , 2018.
  * [98] M. Zhu, T. Zhang, Z. Gu, and Y. Xie, “Sparse Tensor Core: Algorithm and hardware co-design for vector-wise sparse neural networks on modern GPUs,” in _MICRO_ , 2019.
  * [99] X. Zhu, W. Han, and W. Chen, “GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning,” in _USENIX ATC_ , 2015.
  * [100] Y. Zhuo, C. Wang, M. Zhang, R. Wang, D. Niu, Y. Wang, and X. Qian, “GraphQ: Scalable PIM-based graph processing,” in _MICRO_ , 2019.