# Slice-and-Forge: Making Better Use of Caches for
Graph Convolutional Network Accelerators

Mingi Yoo  0000-0003-0215-5092 Yonsei UniversitySeoulSouth Korea
<EMAIL_ADDRESS>,  Jaeyong Song  0000-0001-9976-7487 Yonsei
UniversitySeoulSouth Korea<EMAIL_ADDRESS>,  Hyeyoon Lee
0000-0003-3130-7921 Yonsei UniversitySeoulSouth Korea<EMAIL_ADDRESS>,
Jounghoo Lee  0000-0002-0463-7717 Yonsei UniversitySeoulSouth Korea
<EMAIL_ADDRESS>,  Namhyung Kim  0000-0002-2030-6010 Samsung
ElectronicsHwaseongSouth Korea<EMAIL_ADDRESS>,  Youngsok Kim
0000-0002-1015-9969 Yonsei UniversitySeoulSouth Korea<EMAIL_ADDRESS>and  Jinho Lee  0000-0003-4010-6611 Seoul National UniversitySeoulSouth Korea
<EMAIL_ADDRESS>
(2022)

###### Abstract.

Graph convolutional networks (GCNs) are becoming increasingly popular as they
can process a wide variety of data formats that prior deep neural networks
cannot easily support. One key challenge in designing hardware accelerators
for GCNs is the vast size and randomness in their data access patterns which
greatly reduces the effectiveness of the limited on-chip cache. Aimed at
improving the effectiveness of the cache by mitigating the irregular data
accesses, prior studies often employ the vertex tiling techniques used in
traditional graph processing applications. While being effective at enhancing
the cache efficiency, those approaches are often sensitive to the tiling
configurations where the optimal setting heavily depends on target input
datasets. Furthermore, the existing solutions require manual tuning through
trial-and-error or rely on sub-optimal analytical models.

In this paper, we propose _Slice-and-Forge (SnF)_ , an efficient hardware
accelerator for GCNs which greatly improves the effectiveness of the limited
on-chip cache. SnF chooses a tiling strategy named feature slicing that splits
the features into vertical slices and processes them in the outermost loop of
the execution. This particular choice results in a repetition of the identical
computational patterns over irregular graph data over multiple rounds. Taking
advantage of such repetitions, SnF dynamically tunes its tile size. Our
experimental results reveal that SnF can achieve 1.73$\times$ higher
performance in geomean compared to prior work on multi-engine settings, and
1.46$\times$ higher performance in geomean on small scale settings, without
the need for off-line analyses.

Graph Convolutional Networks, Accelerators, Caches

This is an author preprint version of a paper which will appear in the
proceedings of PACT’22.
∗ Equal contribution
† Corresponding author.

††submissionid: 520††journalyear: 2022††copyright: acmcopyright††conference:
International Conference on Parallel Architectures and Compilation Techniques;
October 10–12, 2022; Chicago, IL, USA††booktitle: International Conference on
Parallel Architectures and Compilation Techniques (PACT ’22), October 10–12,
2022, Chicago, IL, USA††price: 15.00††doi: 10.1145/3559009.3569693††isbn:
978-1-4503-9868-8/22/10††ccs: Computer systems organization Neural
networks††ccs: Computer systems organization Single instruction, multiple data

##  1\. Introduction

Graph convolutional networks (GCNs) are considered the next-generation deep
neural networks (DNNs) as they can be applied to a variety of data which
exhibit irregular patterns. Despite their wide applicability spanning from
traditional graph problems (Zhang and Chen, 2018; Fout et al., 2017) to modern
DNN tasks (Vashishth, 2019), conventional DNN accelerators cannot efficiently
accelerate GCNs. Different from traditional DNNs, graphs exhibit highly sparse
structures and demand fundamentally different acceleration schemes. Although
some hardware accelerators which exploit the sparsity in DNNs (Parashar et
al., 2017; Judd et al., 2017; Zhang et al., 2016) may cope with the highly
sparse structures of graphs, such accelerators are still not well-suited for
GCNs as the portion of non-zero values in graphs ($<$0.01%) is significantly
lower than sparse DNNs (10%–90%).

Aimed at the efficient acceleration of GCNs, prior studies propose new
hardware accelerators which exploit various unique characteristics of GCNs. In
particular, as GCNs incur large working set sizes and highly irregular memory
access patterns, the hardware accelerators should efficiently utilize their
limited on-chip caches. Viewing GCNs as cascaded sparse-dense matrix
multiplications, one popular technique is loop tiling and reordering, as
demonstrated in (Li et al., 2021a; Liang et al., 2020; Geng et al., 2020).
Loop tiling partitions a given GCN into multiple tiles, as performed in sparse
matrix-vector multiplication (SpMV) approaches (Zhu et al., 2015; Hong et al.,
2019). By confining the working set to a specific region, the loop tiling
result in better cache efficiency at the expense of increased repetition
counts.

However, the difficulty of loop tiling lies in the fact that configuring the
tile size is non-trivial. Especially for GCNs which exhibit abundant random
accesses, the optimal setting for tiling varies per dataset and cannot be
decided statically. Thus, the current existing solution to obtain the optimal
tiling configuration is manual tuning through trial-and-error. While there
exists an approach to restrictively apply analytical search for tiling
configuration (Li et al., 2021a), it ignores the fact that the graph is sparse
and often falls into an inferior solution.

In this work, we propose _Slice-and-Forge (SnF)_ , a technique for enabling
on-line tuning for the GCN configuration. The proposed scheme is conceptually
illustrated in Figure 1. SnF sits on top of _feature slicing_ , which splits
the feature matrix into multiple vertical strips and puts its loop at the
outermost level. This creates a repeated access pattern over the random graphs
and allows for gradually tuning the configurations such that it can settle at
a near-optimal configuration within a few rounds.

Exploiting the repetitive patterns, we propose a method for efficiently tuning
the vertex tiling configurations with _automatic tile morphing_. In vertex
tiling, the adjacency matrix is partitioned into multiple tiles where the
performance is sensitive to tile size. With automatic tile morphing, we search
for the optimal tile size using a method similar to a convex optimization.

Although the feature slicing itself is a kind of loop tiling technique that
has been long studied in the context of SpMM (Aktulga et al., 2014; Zheng et
al., 2016) or GCNs (Li et al., 2021a), exploiting the repetitive pattern from
feature slicing for dynamic configuration has not been studied yet, to the
best of our knowledge. In addition to enabling the repetitive dynamic
configuration, we also show that feature slicing itself is often a favorable
choice for loop tiling.

Our contributions can be summarized as follows:

  * •

We identify that feature slicing creates repetitive patterns over a random
graph data and propose Slice-and-Forge (SnF) which exploits the pattern for
efficient dynamic tuning.

  * •

We suggest automatic tile morphing that dynamically tunes the number of vertex
tiles at runtime.

  * •

We provide a strategy for extending SnF to multi-chip module scaling.

  * •

We provide a thorough evaluation of SnF which composes the above techniques,
and we discuss the benefits.

##  2\. Background

###  2.1. Graph Convolutional Networks

Figure 1. Conceptual diagram of the slice-and-forge scheme. Figure 2. Baseline
GCN accelerator architecture.

With numerous variations (Kipf and Welling, 2016; Hamilton et al., 2017b; Xu
et al., 2018), inference of a GCN layer $l$ can be formulated as follows:

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

In the above equation, $\tilde{A}\in\mathbb{R}^{|V|\times|V|}$ is a normalized
Laplacian111Normalized Laplacian refers to a form of adjacency matrix defined
as $\tilde{A}=I-D^{-1/2}AD^{-1/2}$ where $D$ is a degree matrix..
$X^{(l)}\in\mathbb{R}^{|V|\times|F^{(l)}|}$ is a feature matrix for the $l$-th
layer where each row represents the features associated with a vertex.
$W^{(l)}\in\mathbb{R}^{|F^{(l)}|\times|F^{(l+1)}|}$ is a trainable weight
matrix for layer $l$ and is the trainable part of GCNs. $\sigma(\cdot)$ is an
activation function where the rectified linear unit (ReLU) is commonly used.
Typically, three to five layers comprise a GCN (Li et al., 2019, 2018a) as
having too many layers is known to be difficult to train.

Eq. 1 has two matrix multiplications in it. The first, matrix multiplication
between $\tilde{A}$ and $X^{(l)}$ or $\tilde{A}$ and $X^{(l)}\cdot W^{(l)}$,
is called the _aggregation_ phase. Because each row of $\tilde{A}$ represents
the neighbor list of a vertex, multiplying the row with matrix $X^{(l)}$
essentially ‘aggregate’s features of neighboring vertices. While summation is
the most popular aggregation function, many aggregation functions other than
summation is possible (e.g., max). Nonetheless, the underlying computation
pattern is identical to matrix multiplication. The second, matrix
multiplication between $\tilde{A}\cdot X^{(l)}$ and $W$ or $X^{(l)}$ and $W$,
is called the _combination_ phase. Because the elements within an entire row
represents features belonging to a single vertex, the multiplication does not
incur any information transfer between the vertices, but just ‘combine’s the
features contained within the vertex. In other words, it does not require
inter-vertex communication. To each vertex, it can be thought as the feature
vector being passed through a fully connected layer, where each vertex shares
an identical weight matrix.

As analyzed in (Yan et al., 2020), aggregation phase usually becomes the main
bottleneck of the GCN execution. Unlike the combination which is essentially a
dense-dense matrix multiplication, the high sparsity of the graph topology
($\tilde{A}$) and the low arithmetic density of the aggregation phase yields
an extremely memory-intensive characteristics. Together with the reason that
it is hard to optimize, many work mainly focus on the aggregation phase. It is
also worth noting that as depicted in Eq. 1, the order between aggregation and
combination does not affect the result of a GCN layer. However, depending on
the shape of $W$, the width of the feature vector could increase or decrease,
which can be used to reduce the execution time of aggregation (Li et al.,
2021b).

###  2.2. Baseline GCN Accelerator

1248163264$0$$0.5$$1$$1.5$$2$Number of Vertex Tiles (Pokec)Norm.
Speedup$|F|=32$$|F|=128$1248163264$0$$0.5$$1$$1.5$Number of Vertex Tiles
(Citation)Norm. Speedup Figure 3. Sensitivity of GCN to number of vertex
tiles. The best performing number of vertex tiles are marked with red circles.
Figure 4. Row product based GCN processing (left) and feature slicing (right).
Figure 5. Column product based execution (left) and its tiling (right).

Figure 2 presents a baseline GCN accelerator comprising aggregation engines
and combination engines, similar to previous work (Yan et al., 2020; Auten et
al., 2020; Liang et al., 2020; Kiningham et al., 2020), where the green
component has been newly added that will be discussed in Section 4.3. The core
of combination engine is a systolic array to support efficient matrix
multiplication. Similar to previous systolic array based DNN accelerators
(Jouppi et al., 2017; Lym et al., 2019), there are two local memories in a
double buffering manner that continuously provide input to the core. The
property buffer $X$, and the weight reader provide $W$, respectively. The
output of the combination engine is read by the aggregation engine such that
it can be processed in the aggregation function.

The aggregation phase is similar to classic graph processing, but each access
to the edge contains a wide row of $X$ that has to be multiplied to the
corresponding edge weight (i.e., $\tilde{A}_{i,j}$) and accumulated. The SIMD
cores process the multiply-accumulation. To feed the SIMD cores without stall,
the two prefetch modules runs ahead in the graph topology such that the
feature reader can always have on-the-fly reads to the feature matrix $X$.

The graph topology is stored in a compressed sparse row (CSR) format to
exploit the sparsity of the data. The vertex prefetch unit reads row pointers
and passes it to edge prefetch and feature reader. Then the edge prefetch unit
reads column indices of CSR and sends them to the feature reader and SIMD
cores. When the feature reader receives an edge, it collects the rows of the
feature matrix $X$. Because edges are sparse, the reads exhibit highly
randomized pattern, making the aggregation phase memory-intensive and hard to
optimize.

One way to mitigate the memory bottleneck in the aggregation phase is to use a
large on-chip global cache. Shared by multiple engines in the accelerator, it
temporarily stores the recently accessed features. However, because of the
wide feature matrix whose width often spans over hundreds to thousands, the
working set usually well exceeds the size of the global cache, making it
difficult to exploit localities.

##  3\. Motivational Example

In GCN execution, the most commonly used loop tiling technique to reduce
memory accesses is _vertex tiling_ as adopted from (Li et al., 2021a; Liang et
al., 2020; Geng et al., 2020). With vertex tiling, the adjacency matrix is
split into multiple tiles and processed sequentially. This way, the range of
features being accessed is restricted within a tile to have a much smaller
cache working set (and therefore exhibit more cache hits). However, a better
cache hit ratio incurs at the expense of multiple accesses on vertex features,
either for reading or writing the features. Because of this, choosing the
right number of tiles becomes critical for high performance.

Figure 3 illustrates sensitivity to the number of vertex tiles, according to
graph datasets Pokec and Citation (See Table 1 for details.) with different
feature width per vertex (32 and 128). The Y axis shows speedup, normalized by
the slowest among the number of tiles under consideration.

We make two observations from the plots: the performance is sensitive to the
number of tiles, and the optimal number of vertex tiles differs according to
dataset and feature width. With the default 1$\times$1 vertex tiles, much of
the memory access count is spent reading the vertex features multiple times
due to cache misses. As the number of tiles increases, the working set size
decreases and is better captured by the cache. Simultaneously, the number of
output feature access increases due to the repeated writes222In fact, it is
possible to alter the order of tile traversal to increase the input access
repetition instead. We omit this case as it mandates perfect caching.. It is
shown that the performance discrepancy between the best and the worst
configuration greatly varies, up to 1.9$\times$ in the example (Pokec at
$|F|=32$). Furthermore, the relation between the amount of input access and
number of tiles depends on the random access pattern posed by the adjacency
matrix. Not knowing the optimal setting a priori, one has to make an educated
guess that can easily result in an inferior performance, or undergo several
executions to find the optimal configuration which destroys the purpose of
achieving speedup.

In this paper, we suggest feature slicing as an opportunity for on-line tiling
configuration. By exploiting the repetitive computation pattern found from
feature slicing dataflow, the optimal configuration is gradually found over
multiple rounds. The proposed scheme not only searches for the optimal vertex
tiling, but also the work distribution strategy which is crucial for multi-
engine scaling of the GCN accelerators.

##  4\. Slice-and-Forge

###  4.1. Feature Slicing Dataflow

Much of the prior work on GCN accelerations are based either on the _row
product_ (Yan et al., 2020; Li et al., 2021a; Auten et al., 2020; Liang et
al., 2020) or _column product_ (Geng et al., 2020). In this section, we
describe the dataflow choice of SnF, which places feature slicing as the
outermost loop that embraces vertex tiling.

Figure 4 (left) displays the aggregation based on the basic row product
dataflow (the innermost loop outputs a row). The colored strips of $\tilde{A}$
represent nonzeros in the topology matrix (i.e., edges) and the horizontal
strips of $X$ are the elements of the feature vectors to be aggregated from
the matching colored edges. In the row product execution model, 1 the
outermost loop visits the vertices in $\tilde{A}$. 2 The next level loop
visits the edges and 3 aggregates the corresponding features.

The memory access pattern from this dataflow exhibits the following
characteristics: First, reading $\tilde{A}$ is done sequentially and only
once. Second, features from neighboring vertices are read randomly over the
entire feature matrix $X^{(l)}$, where a row of the feature matrix is read for
each of the edges in $\tilde{A}$. Lastly, writing the output feature
$X^{(l+1)}$ to the memory is also sequential and performed only once. From the
above characteristics, the performance bottleneck is at reading the feature
matrix $X^{(l)}$. With a global cache, the memory access can be reduced if the
cache is large enough to capture the features, where the hit rate depends on
the pattern of the edges.

When the feature matrix is significantly larger than the global cache size,
the miss rate approaches 100% and loop tiling is a popular solution for
mitigating this. While there are many possible configurations, Figure 4
(right) shows the choice of SnF named _feature slicing_. It partitions
$\tilde{A}$ into $B_{V}\times B_{V}$ vertex tiles, and splits the feature
matrix $X$ into multiple _slices_ of vertical strips. As depicted in the
figure, the two outermost loops ( 1 and 2) visit the feature slices and vertex
tiles. The inner loops are identical to that from the Figure 4 (left). As
observed in the dotted red lines, the working set is divided by the number of
feature slices $B_{F}$ and number of tiles $B_{V}$, at the expense of reading
the topology $\tilde{A}$ for $B_{F}$ times and reading the feature matrix $X$
for $B_{V}$ times.

When $B_{V}$ and $B_{F}$ are large enough that all the tiles perfectly fit on
the on-chip memory, only the cold misses remain. In this manuscript, we call
this strategy _perfect tiling_. While perfect tiling can maximize the cache
efficiency, the required value of $B_{V}$ is usually too large. Moreover, it
neglects the sparsity of the graph topology and regards the computation as a
dense matrix multiplication, often resulting in a suboptimal performance.

Column product is another dataflow solution for mitigating the cache miss.
Figure 5 (left) shows the column product execution model. 1 The outermost loop
traverses each element along the feature vectors (i.e., the column of $X$). 2
The next level loop visits the columns of $\tilde{A}$. 3 Lastly, the nonzero
elements in the chosen column of $\tilde{A}$ are accessed, and the multiplied
value is written to the corresponding position of the output matrix.

Because the two dimensions of $X$ are located at the outer loop, X is accessed
only once. However, it requires access to the adjacency matrix by the length
of feature. For mitigating this, there is an way that use cache for adjacency
matrix like Figure 5 (right). When $\tilde{A}$ and $O$ are split into $B_{A}$
and $B_{O}$ vertical strips, respectively, a strip of $\tilde{A}$ stored in
the cache is reused multiple times to improve performance. but it needs an
extra cache capacity and adds the cost of repeated access to the output
matrix.

In SnF, we place the feature slice visiting loop at the outermost level ( 1).
Even though the order of the two loops does not pose much difference in the
working set size except for slight change in the pattern, it should be
emphasized that this particular choice creates a recurring pattern over the
random data access 2\- 5. This creates a unique opportunity for GCNs, where
the inner loop configuration can be tuned over iterations of the loop 1
because there is no difference among the feature slices, unlike the vertex
tiles. Please note that this technique is infeasible for classic graph
analytics, because the feature width is usually too narrow (e.g., 1 for
PageRank).

The size of $B_{F}$ has to be decided such that the slice width $|F|/B_{F}$
must be at least over $64\text{\,}\mathrm{B}$, which is the granularity of the
main memory and cache lines to maintain the spatial locality. SnF sets the
slice width to be 64 bytes (e.g., $B_{F}=16$ for $|F|=256$).

Figure 6. Procedure of automatic tile morphing. Figure 7. Configuration
controller architecture to support automatic tile morphing.

###  4.2. Automatic Tile Morphing

As exemplified in Section 3, choosing the right number of tiles is crucial to
achieving high performance, yet there is no efficient method for optimal
selection without an expensive trial-end-error procedure. We propose
_automatic tile morphing_ , an approach that takes advantage of repetitive
computational patterns to gradually configure the vertex tiling at runtime.

With feature slicing dataflow (Section 4.1, the topology data $\tilde{A}$ is
traversed multiple ($B_{F}$) times in the exact same pattern ( 2\- 5 in Figure
4 (right)). From each round—processing a slice of $X$—of the execution,
automatic tile morphing dynamically tunes the vertex tiling to reach the
nearly optimal point at runtime, without the need for off-line design space
exploration. While a similar dynamic method can be devised by executing vertex
tiling as outer loop and tuning $|F|$ as the parameter, the processing pattern
of each tile would be distinct, making the tuning result from one tile
unusable to the next.

Figure 6 displays an example procedure of automatic tile morphing, comprising
two phases: _coarse morphing_ and _fine morphing_. Coarse morphing (top)
assumes that performance is a convex function of the number of tiles. Starting
from a default setting (2$\times$2 in the figure), the performance is measured
with twice more tiles in each dimension, and then half the number of tiles in
each dimension. In the direction of better performance, the same doubling or
merging continues until a decrease in the performance is observed, the number
of tiles is rolled back to that of the previous iteration (4$\times$4 in the
example), and the coarse morphing terminates.

Then, fine morphing (bottom) starts from the best partitioning of the coarse
morphing phase. The goal of fine morphing is to use heterogeneously sized
tiles, such that the unbalanced graph distribution is considered. Real-world
graphs are sometimes collected by crawling, which is based on a breadth-first
search order. In addition, because of the small-world phenomenon (Leskovec et
al., 2005), dense clusters often exist. These clusters exhibit a larger number
of access instances and likely require a smaller working set compared to the
sparser region of the graph. We confined the tiling to have variable-sized
vertical strips of square tiles to reduce the search space size, which
effectively converts fine morphing to a one-dimensional partitioning problem.

Fine morphing records the hit rates of each tile and uses the rates to
determine the visiting order. In the order of the lowest hit rate (red
$\rightarrow$ orange), the vertical strips of blocks are further split into
half-sized tiles, with one column per iteration. Similar to coarse morphing,
this process is performed until performance degrades, and it rolls back the
change that degraded the performance. Then, similarly, but in the order of the
highest hit rate (blue), two adjacent columns are merged until the performance
decreases. While we can further examine splitting a tile to 4$\times$4 tiles
or merging 4$\times$4 tiles into one, we found no case in our dataset where
such a configuration could further accelerate the execution.

For implementation, we defined a unit tile size and stored the length of each
vertical strip in the units. In practice, the unit tile can be set as the tile
size that perfectly fits the global cache. In this paper, we split the
topology into 64$\times$64 unit tiles. In the worst case, there can be at most
64 unit-width strips, where storing them consumes less than a KB of capacity.

Empirically, automatic tile morphing finds a solution near the static best. To
avoid the decision process from being on the critical path, we decide the next
iteration’s policy based on the measurements until the penultimate column of
blocks. However, a runtime overhead exists from the few first feature slices
being executed with suboptimal tiling. When $B_{F}$ is too small, the portion
of this overhead grows relatively large, which is another reason to favor a
higher $B_{F}$. Please see Section 6.12 for further discussion.

###  4.3. Slice-and-Forge Architecture

To support automatic tile morphing, SnF adds a hardware component named
_configuration controller_ to the accelerator shown in Figure 2. The detailed
architecture of the controller is illustrated in Figure 7.

The job of the configuration controller overall is to collect statistics given
from the feature reader, make configuration decisions, and pass the decision
to the vertex prefetch unit. For each iteration round of $B_{F}$, the
controller accumulates the number of feature accesses and misses per vertical
strip of unit tiles to calculate miss ratio. When the round is over, the
controller updates these miss ratios and cycles into the _ATM Status Table_.
Based on this information from current round (round_cur) and from the stored
optimal (round_opt), the controller invokes Algorithm 1 to produce next
round’s decision for the vertex tile size.

Figure 8. Two extreme cases of loop tiling for vertex-only tiling (left) and
feature-only tiling (right). Algorithm 1 Automatic Tile Morphing

Input:

$round\\_cur,round\\_opt$: configuration of current/optimal round

$atm\\_direction$: current ATM morphing direction flag ($HALVING/MERGING$)

$phase$: current ATM phase flag ($COARSE/FINE$)

Output:

$new\\_tile\\_width\\_arr$: next tile width array decided by ATM

1:if $round\\_cur.cycles<round\\_opt.cycles$ then // if faster, update to
optimal setting

2: $round\\_opt\leftarrow round\\_cur$

3:else if $phase=COARSE$ then // if slower, enter fine morphing

4: $phase\leftarrow FINE$

5:else // for rest, this setting is optimal we found.

6: return $round\\_opt.tile\\_width\\_arr$

7:if $phase=COARSE$ then

8: if $atm\\_direction=HALVING$ then // increase the number of the tiles.

9: for all tiles of $round\\_cur.tile\\_width\\_arr$ do

10: append halved tiles to $new\\_tile\\_width\\_arr$. // e.g. [4,4]
$\rightarrow$ [2,2,2,2]

11: else if $atm\\_direction=MERGING$ then // decrease the number of the
tiles.

12: for half of tiles in $round\\_cur.tile\\_width\\_arr$ do

13: append merged tile to $new\\_tile\\_width\\_arr$. // e.g. [2,2,2,2]
$\rightarrow$ [4,4]

14:else if $phase=FINE$ then

15: if $atm\\_direction=HALVING$ then // increase the number of the tiles.

16: find worst miss ratio tile and halve.

17: append halved tiles and other tiles to $new\\_tile\\_width\\_arr$.

18: else if $atm\\_direction=MERGING$ then // decrease the number of the
tiles.

19: find best miss ratio tile and merge with adjacent tile.

20: append merged tile and other tiles to $new\\_tile\\_width\\_arr$.

21: $round\\_cur.tile\\_updated\\_idx\leftarrow index$

22:$round\\_cur.tile\\_width\\_arr\leftarrow new\\_tile\\_width\\_arr$

23:return $new\\_tile\\_width\\_arr$

Algorithm 1 shows the simplified procedure of automatic tile morphing. The
controller manages tiling by $\mathit{tile\\_width\\_arr}$, an array that
stores how many unit tiles comprise each vertical strip. For example, it
stores 32 consecutive 2’s to represent 32×32 tiles and 16 consecutive 4’s to
represent 16×16 tiles. Automatic tile morphing starts with updating the
optimal value ($round\\_opt$) in the status table (line 2). The controller
proceeds into the coarse morphing phase. Assuming that the performance-
improving direction $\mathit{atm\\_direction}$ have been found in the previous
rounds to be halving the tile sizes (omitted in the algorithm), the new
$\mathit{tile\\_width\\_arr}$ is populated with twice the original elements
from the array of the current rounds of half the values (line 8-10). The
merging direction functions in a similar manner (line 11-13). In fine morphing
phase, controller finds the target tile ($t\\_id$) that should be merged with
adjacent tile or halved based on the miss-ratio (line 14-21). After
$\mathit{tile\\_width\\_arr}$ is determined, this tiling information is passed
to vertex prefetch unit.

The configuration controller stores access/miss/ratio registers for each of
the 64 unit vertical columns. In addition, $\mathit{tile\\_width\\_arr}$ and
$miss\\_ratio$ of the status table are 64 entry-long arrays for each of
$\mathit{round\\_op}t$, $\mathit{round\\_cur}$, and at the output to the
vertex prefetch. Thus, using 4 byte elements, the total size of the registers
and status table is only about 1.5KB, a negligible size compared to the global
cache.

###  4.4. Dataflow Cost Comparison

The feature slicing dataflow adopted in SnF implicitly prioritizes increasing
the number of slices $B_{F}$ over increasing the vertex tiles $B_{V}$. While
it is true that this choice somewhat puts a restriction on loop tiling, we
analyze the cost model to show that prioritizing is a advantageous strategy in
general.

Using the terms Section 2.1 and $|E|$ as the number of edges, the memory
access cost from the row product execution in Figure 4 (left) can be modeled
as below.

(2) $\displaystyle M_{Row}$
$\displaystyle=(|V|+|E|)+m(|V||F|)\cdot|E||F|+|V||F|.$

The first and third terms account for sequentially reading the topology data
in CSR format and writing the output matrix, respectively. The second term, on
the other hand, models the random reads to the feature matrix. For each edge
($|E|$) in the topology, a row of the feature matrix is read ($|F|$). Under
the assumption that the miss rate $m(x)$ is a function of the working set size
$x$, the second term represents the accesses filtered by the global cache.

Applying loop tiling, the bottleneck at the second term is reduced by reducing
the working set size. Using the tiling from Figure 4 (left), the model
becomes:

(3) $\displaystyle M_{FS}$
$\displaystyle=B_{F}(B_{V}|V|+|E|)+m(\frac{|V||F|}{B_{F}B_{V}})\cdot|E||F|+B_{V}|V||F|.$

The working set size is divided by the product of $|B_{F}|$ and $|B_{V}|$,
where those factor are multiplied to reading the topology data and writing the
output matrix, accounting for the repetitions.

Thus, intuitively, increasing $|B_{F}|$ yields a lower cost if the topology
data are smaller, and increasing $|B_{V}|$ is better if the feature matrix
size is smaller. Because the feature width in GCNs usually reach several
hundreds, it is often beneficial to favor increasing $|B_{F}|$ over $|B_{V}|$.
Consider two extreme cases where we only tile the topology
($|B_{F}|=1,|B_{V}|=B$) as in Figure 8 (left), versus only tiling the feature
matrix ($|B_{F}|=B,|B_{V}|=1$) as in Figure 8 (right), such that the working
set sizes are equal. Substituting the values into Eq. 3 and finding the
condition for the former being smaller than the latter,

(4) $\displaystyle B|V|+|E|+B|V||F|$ $\displaystyle>B(|V|+|E|)+|V||F|,$
$\displaystyle|F|$ $\displaystyle>|E|/|V|.$

In the above equation, $|E|/|V|$ is the average degree of the graph, one of
the representative parameters of graph data. It is widely known that the
average degree of real-world graphs is usually only around 10-20 (Hu et al.,
2020). Comparing this to $|F|$ being several hundreds, favoring increasing
$|B_{F}|$ first can be a rational choice.

##  5\. Multi-Chip Scaling

Figure 9. Multi-chip scaling strategy.

Figure 9 (a) illustrates the multi-chip environment. In multi-chip scaling, we
assume that each chip is packaged with its own memory module such as HBM. With
such an environment, the scaling challenge is that communications need to be
explicit because the memories are not shared. Figure 9 (b) and (c) show the
strategy for scaling. For the combination (b), we duplicate $W$ in the memory
of each chip. This is feasible since $W$ is small. Then $X$ is split
horizontally, such that each chip can produce its own piece of the output
matrix.

For aggregation, the topology $\tilde{A}$ is similarly split into four pieces,
and does not need to be communicated between the chips. However, $X$ needs to
be communicated because each chip only has a part of $X$ but eventually needs
the whole matrix. In our strategy as in Figure 9 (c) similar to all-gather
(Thakur et al., 2005), each chip starts by aggregating only with the current
piece of $X$. At the same time, the same piece is passed to the neighboring
chip in the ring. Next, the data that has been just received piece is being
processed and passed to the neighbor. After $N-1$ steps for $N$ chips, the
aggregation is complete. Note that there is no further communication after
aggregation (Except for the last GCN layer), because the split output will be
directly used as split input to the next layer’s combination.

##  6\. Evaluation

###  6.1. Dataset

Table 1. Benchmark Dataset Information Dataset | #Vertices | #Edges | #Features | Topology | Feature
---|---|---|---|---|---
Products (PD) | 2.45 M | 61.9 M | 100 | 0.24 GB | 0.91 GB
Citation (CT) | 2.93 M | 30.6 M | 128 | 0.12 GB | 2.79 GB
Pokec (PK) | 1.63 M | 30.6 M | 256 | 0.12 GB | 1.56 GB
YouTube (YT) | 1.13 M | 2.99 M | 256 | 0.02 GB | 1.08 GB
LiveJournal (LJ) | 4.85 M | 69.0 M | 256 | 0.28 GB | 4.63 GB
Orkut (OK) | 3.07 M | 117 M | 256 | 0.45 GB | 2.93 GB
Reddit (RD) | 0.23 M | 114 M | 602 | 0.43 GB | 0.52 GB

We use seven large graph datasets from the real world as benchmarks. The
details are listed in Table 1. Products (_PD_) is from Open Graph Benchmark
Collection (Hu et al., 2020). It has 2.45 M vertices that represent Amazon
products with 61.9 M edges which indicates products being purchased together.
Each vertex has word embeddings of width 100 as features, generated from
product descriptions. Citations (_CT_) is also from the Open Graph Benchmark
Collection and represent 2.93M papers as vertices and their citations as 30.6M
edges from Microsoft Academic Graph (Wang et al., 2020). Each vertex is
associated with word embeddings from their titles and abstracts. Pokec (_PK_),
YouTube (_YT_), LiveJournal (_LJ_), Orkut (_OK_) and Reddit (_RD_) are from
Stanford Large Network Dataset Collection (Leskovec and Krevl, 2014). Pokec
(Takac and Zabovsky, 2012) is a social network graph from Slovakia, and
includes 1.63M users as vertices and 30.6M connections as edges. Youtube (Yang
and Leskovec, 2015) is graph from users of a video sharing service, with 1.13M
users and 2.99M connections between them. Livejournal (Leskovec et al., 2009)
and Orkut are from online social network services with 4.85M and 3.07M
vertices, respectively. Reddit (Yanardag and Vishwanathan, 2015) is a social
network service, and 0.23M vertices are collected from the Reddit discussion
forum. The features of the Reddit dataset consist of 302-dimensional post
information, and GloVe CommonCrawl (Pennington et al., 2014) based
300-dimensional word embedding vectors. For others, the node embedding vectors
of width 256 have been generated from node2vec (Grover and Leskovec, 2016) and
used as features.

###  6.2. Methodology

Table 2. System Configuration Common |  Accelerator Engine | Frequency | 1GHz
---|---|---|---
Combination |  32$\times$32 Syst. Array
Aggregation | 16-Way SIMD
Global Cache | Capacity | 16MB
Ways | 16
Replacement | LRU
Multi-engine | #Engines | Aggregation | 8
Combination | 8
Off-chip Memory (Shared) | Spec. | HBM2
Peak Bandwidth | 256 GB/s
Channels | 8
Banks |  4$\times$4
Small scale | #Engines | Aggregation | 1
Combination | 1
Off-chip Memory | Spec. | DDR4-2666
Peak Bandwidth | 21.3 GB/s
Ranks | 4
Banks |  4$\times$4
Multi-Chip Module | #Modules | Accelerator | 1-32
HBM | 1-32
Interconnect | Topology | Ring
Bandwidth | 256 GB/s
Latency | $20\text{\,}\mathrm{ns}$
Table 3. Comparison of Existing GCN Accelerators

Scheme | Dataflow | Loop Tiling | Tiling Configuration
---|---|---|---
Topology | Feature | Method |  Non-perfect Tiling
HyGCN | Row Product | ✗ | ✗ | ✗ | N/A
EnGN | Row Product | ✗ | ✓ | ✗ | N/A
AWB-GCN | Col. Product | ✓ | ✓ | ✗ | N/A
GCNAX | Row Product | ✓ | ✓ | Preproc. | ✗
SnF (Proposed) | Row Product | ✓ | ✓ |  ATM (Runtime) | ✓

We evaluate the performance of SnF architecture with the configuration listed
in Table 2. The accelerator runs in 1GHz frequency, where the combination
engine has 32×32 systolic array and the aggregation engine has 16-way SIMD
cores. Both engines use 32bit fixed point arithmetic operations.

We use HyGCN as baseline architecture, as HyGCN has an easily expandable
architecture for vertex tiling and feature slicing. On the other hand, GCNAX
uses static vertex tiling by pre-profiling the workload and AWB-GCN does not
use caches for exploiting locality. Therefore, applying SnF which uses dynamic
strategy and cache on such architectures would be infeasible.

We conduct the experiments in total of three different settings. In our
default setting, a multi-engine configuration is used, which comprises eight
of both engines, with an HBM2 memory subsystem. In our small scale setting, we
show that SnF is also efficient on a design with small resource budget and low
memory bandwidth. The setting includes one of both engines with a 4-rank DDR4
channel. Lastly, we demonstrate the extension to the multi-chip scaling method
described in Section 5. We use one to 32 chips connected in a ring topology
network. Following other MCM accelerators (Shao et al., 2019; Arunkumar et
al., 2017) we use 256GB/s bandwidth ring interconnect, with
$20\text{\,}\mathrm{ns}$ per-hop latency, where each chip is connected to its
own HBM module. To validate the design, we implemented the accelerator in
Verilog HDL and synthesized it using Cadence Genus with 45
$\text{\,}\mathrm{nm}$ OpenPDK library, which was scaled to 32
$\text{\,}\mathrm{nm}$. To model the on-chip memory, we used CACTI (Thoziyoor
et al., 2008) to draw the power and area under $32\text{\,}\mathrm{nm}$
technology node. The baseline chip resembling HyGCN (Yan et al., 2020)
consumed 11.40 $\text{\,}{\mathrm{mm}}^{2}$, and SnF has an area of 11.55
$\text{\,}{\mathrm{mm}}^{2}$. For comparison we reproduced GCNAX (Li et al.,
2021a) and AWB-GCN (Geng et al., 2020), which consumed 11.23
$\text{\,}{\mathrm{mm}}^{2}$ and 13.80 $\text{\,}{\mathrm{mm}}^{2}$,
respectively.

For performance modeling, we ported SCALE-Sim (Samajdar et al., 2018) to C++,
and extended it to support the SnF’s aggregation unit. The cycles were matched
to that of the RTL model. For modeling the DRAM subsystem, we used DRAMsim3
(Li et al., 2020). We faithfully reproduced the previous work from Table 3.
HyGCN (Yan et al., 2020) is the baseline accelerator with hybrid engines, and
EnGN (Liang et al., 2020) proposes an RER dataflow with DAVC that captures
high-degree vertices. AWB-GCN (Geng et al., 2020) is based on column product
which utilizes same set of PEs for both aggregation and combination with
separate task distributors. Lastly, GCNAX (Li et al., 2021a) perform a static
analysis to find the optimal loop tiling under the assumption of perfect
tiling. For comparison, we also added a ‘VT’ version of the accelerator, to
which we normalized all values.

###  6.3. Multi-Engine Accelerator Results

LJRDPKYTPDCTOKGmean$0$$1$$2$SpeedupVTHyGCNEnGNAWB-GCNGCNAXSnF (Proposed) (a)
Multi-engine setting.

LJRDPKYTPDCTOKGmean$0$$1$$2$Speedup (b) Small-scale setting.

Figure 10. Performance of SnF in (a) multi-engine setting and (b) small-scale
setting.

In this subsection, we analyze the multi-engine performance to show the
proposed SnF outperforms the existing accelerators. We placed eight engines
into the accelerator, with HBM2 memory providing 256 GB/s peak bandwidth. The
results are shown in Figure 10(a). We set ‘VT’ as a baseline which only
performs vertex tiling. ‘SnF ’ is the proposed accelerator with the feature
slicing on top of vertex tiling with automatic tile morphing. Among the
multiple engines, we split the graph workload such that the number of edges
per engine is equal. For all implementations except SnF which is dynamic, we
examined all possible partitioning combinations off-line (i.e., optimal) and
chose the best one.

Comparing SnF with VT gives an insight into how much benefit can be drawn from
choosing the right loop tiling scheme for GCN inference. The performance
improvement of SnF over VT is 73.1%, obtained by reducing the significant
amount overhead of VT’s repetitive feature access cost and dynamically finding
the right configuration. The largest speedup is on PD with 2.76×, coming from
the fact that the optimal setting of VT was at a large $B_{V}=64$. This large
$B_{V}$ makes a huge repetition overhead to the output feature accesses.
Feature slicing can efficiently split these repetition counts, contributing to
the superior speedup.

The proposed technique outperforms loop tiling strategies from the existing
prior designs in all datasets. HyGCN adopts no tiling, and shows a poor cache
efficiency. EnGN is based on vertex tiling, and uses DAVC to capture features
from high-degree vertices. However, we have found that the DAVC has a marginal
effect on the speedup. One reason is that there are too many high-degree
vertices in the large-scale real-world graph datasets for DAVC to capture.
Moreover, when their reuse distances are short enough, they are often already
well-captured by the default LRU replacement policy. AWB-GCN is unique among
the designs under test in that they utilize column product based execution
with an aggressive load balancing. It requires a non-negligibly large output
buffer to function without a separate consideration for spilling, given that
there are a few million vertices in the graph. Even though AWB-GCN splits the
matrix, it adds the repetition counts on the feature accesses, which becomes a
reason to underperform SnF by 35.7%. GCNAX provides an analytic model for
finding the optimal partitioning scheme, and it provides 15.4% speedup over
VT. However, they only consider perfect tiling in their model, missing an
important opportunity for performance enhancements. Moreover, because they
unrealistically assume uniformly distributed sparse graphs, their model is
often distant from the real measurements and this becomes another source of
68.2% performance loss compared to SnF.

Figure 11. Example automatic tile morphing over iterations.

Figure 11 shows how automatic tile morphing performs over the repetitions in
PK dataset. The first four iterations are coarse morphing. It gradually checks
multiple $B_{V}$ values and settles at $B_{V}=8$. The overhead from these non-
optimal executions is amortized over multiple iterations. In the fine
morphing, it ends up further splitting the first column which has the lowest
hit rate, and merging the last two columns which have the highest hit rate in
our experiments, automatic tile morphing was able to obtain over 95% the
performance that could be obtained by the optimal analysis, which is an
unavailable information at runtime.

###  6.4. Smal-Scale Accelerator Results

In this subsection, we analyze the single-engine accelerator performance to
show that feature slicing and automatic tile morphing are also effective for
systems under tight resource budget such as mobile and embedded systems.
Figure 10(b) shows the small scale performance of the GCN execution.

As in multi-engine settings, SnF outperforms all prior designs. One
interesting aspect is that among the prior designs GCNAX performs better than
AWB-GCN in the small scale setting. In this setting, the available memory
bandwidth is quite small, and it becomes crucial to utilize the cache
efficiently. Because AWB-GCN does not have particular caching mechanism, the
benefit of better utilizing the cache becomes more important than load
balancing. SnF still finds better settings on all datasets except for OK and
RD, with 10.8% improvement over GCNAX and 46.4% over VT.

Reddit shows a unique trend for performance speedup because it has the largest
number of edges per vertex (dense topology) among the datasets while having
fewer vertices. The dense topology of RD works well with VT, as illustrated in
Figure 10, in which VT shows superior speedup over HyGCN. Also, fewer vertices
require a smaller feature matrix than other datasets, which diminishes the
output write overhead of VT. GCNAX uses perfect tiling, so it constructs a too
large $B_{V}$ tiling strategy, which makes lower speedup over VT. For SnF, the
dynamic tiling found by the automatic tile morphing is almost equal to that of
the static solution found by GCNAX. Because automatic tile morphing takes some
iterations to settle around the best solution, a slight speedup degradation of
0.82% over GCNAX occurs for SnF as depicted in Figure 10(b). OK is also as
dense as Reddit, but it has many vertices. This environment is not friendly
for VT. So, both GCNAX and SnF outperform VT, unlike the Reddit case. SnF has
a minor speedup degradation of 1.8% over GCNAX, similar to Reddit.

###  6.5. Energy Consumption

PDCTPKYTLJOKRD$0$$0.5$$1$Normalized EnergyComputationCacheDRAMBaselineSnF
Figure 12. Normalized energy consumption breakdown of baseline (shaded) and
SnF (solid).

Figure 12 shows the normalized energy consumption of the aggregation phase
with the breakdown, under the single chip, multi-engine setting. We set the
baseline as the architecture with no partitioning, whose energy consumption is
depicted with shaded bars. The energy consumption of the SnF is represented by
the solid bars. As indicated in the figure, SnF consumes slightly more energy
on computation, but much more energy is saved from the memory and the cache.
These both show the efficient usage of cache in SnF due to the increased cache
hit rate, because less data is read from the DRAM, and less data is written to
the cache. An exception is LJ, where the benefit from cache and DRAM is
slightly less than the increased energy in computation. We can save 53% energy
on RD because it has an extremely dense topology structure that accompanies a
smaller topology access ratio over feature accesses. Therefore, since SnF can
significantly reduce feature accesses, the energy consumption is greatly
reduced.

CTPKYTGmean$0$$0.5$$1$$1.5$$2$$2.5$SpeedupMulti-engineHyGCNI-
GCNSnFSnF+I-GCNCTPKYTGmeanSmall scale Figure 13. Performance of I-GCN
reordering.

###  6.6. Effect of Reordering

Another promising scheme for enhancing cache efficiency for GCNs is graph
reordering as adopted in Rubik (Chen et al., 2020) and I-GCN (Geng et al.,
2021). SnF is able to take further benefit from those reordering schemes, due
to two reasons. First, when a graph is reordered, it forms small, dense
clusters. In consequence, the access pattern becomes similar to that of a
smaller working set. This would change the optimal number of vertex tiles, but
SnF is able to adapt to it thanks to automatic tile morphing. Second,
reordering helps improve the locality of the accesses. Because SnF is a
technique that exploits the locality of accesses using caches, reordering
often strengthens SnF.

Figure 13 plots the performance benefit of SnF implemented with reordering of
I-GCN (Geng et al., 2021) on three datasets. As depicted in the graphs,
combining reordering and SnF consistently add extra speedup over using each
scheme on its own. On multi-engine setting, combination of the reordering and
SnF adds 87.9% improvement on top of I-GCN in geometric mean, and 4.22% over
original SnF in geometric mean. On the small scale setting, the improvement is
55.4% over I-GCN and 9.04% over original SnF.

GCNGraphSAGEGINConv$0$$0.5$$1$$1.5$$2$SpeedupMulti-engineVTHyGCNEnGNAWB-
GCNGCNAXSnFGCNGraphSAGEGINConvSmall scale Figure 14. Performance of variant
GNN application.

###  6.7. Performance on GCN Variants

Although SnF focuses on acceleration of GCNs, there are many variants of GCNs
(Xu et al., 2018; Hamilton et al., 2017b) and SnF can be used to execute them.
We implement two popular GCN variants, GraphSAGE (Hamilton et al., 2017b) and
GINConv (Xu et al., 2018), which pose slight modification to the aggregation
phase. Figure 14 plots the performance of GCNs. Each result shows almost
identical trend, because they share the same aggregation-combination
structure. On GraphSAGE, SnF gets 63.9% speedup over VT in multi-engine
setting and 40.7% in small scale setting. On the other hand, on GINConv, SnF
gets 85.4% in multi-engine and 64.3% in small scale setting. Because GraphSAGE
applies sampling that minimize the number of edge access which reduces the
chance for feature reuse, its performance gain are slightly lower than in GCN.
On the other hand, GINConv uses smaller set of edge weights (that is part of
$\tilde{A}$), and thus speedup from reading the features become more
prominant, leading to a higher speedup than GCN.

###  6.8. Sensitivity to Feature Width

64128192256512$0$$0.5$$1$$1.5$$2$SpeedupVTHyGCNEnGNAWB-GCNGCNAXSnF Figure 15.
Performance of the SnF for various feature widths.

In this subsection, we provide sensitivity analyses of the SnF. One insight
from Eq. 4 is that speedup of feature slicing depends on $B_{F}$. Figure 15
presents performance sensitivity to the feature widths in geometric mean. As
indicated in the figure, the effectiveness of SnF is reduced with the layers
of small feature widths which often appear in the later layers of GCNs.
However, the impact of such layers would be marginal due to short execution
times. Furthermore, the configuration found by SnF can be reused in the
succeeding layers. With the trend of wider feature width and deeper layers,
the benefit of ATM is likely to strengthen over time.

###  6.9. Sensitivity to System

1 2 4 8 16 $5$$10$$15$#EnginesSpeedupSpeedup$25$$50$$75$$100$Mem BW Util.
(%)DDR4-2666 (21.3GB/s)4 $\times$ DDR4-2666 (85.3 GB/s)HBM (128GB/s)HBM2
(256GB/s)MemBW Util. Figure 16. Sensitivity of SnF to the various memory
systems and the number of engines.

Figure 16 shows how SnF performs with various number of engines and various
memory systems, normalized at the performance of a small scale SnF with a
DDR4-2666 channel. With one DDR4-2666 channel peaked at 21.3GB/s, increasing
the number of engines gives diminishing returns, as the execution becomes
memory bound. However, with memory subsystems with higher bandwidth, it
requires more engines to fill the bandwidth. For example, an HBM2 system that
provides 256GB/s can gain from more processing engines, and exhibit almost
linear speedup until eight engines. Afterwards it reaches the saturation
point. Based on the study, we set the number of engines in the default setting
to be eight.

###  6.10. Sensitivity to Cache Size

2MB4MB8MB16MB$0$$0.5$$1$$1.5$$2$$2.5$SpeedupVTHyGCNEnGNAWB-GCNGCNAXSnF Figure
17. Performance (geomean) of the SnF for various cache sizes.

Analyzing the cache size sensitivity is essential because SnF takes advantage
of efficient cache locality. Figure 17 shows the performance of SnF for
various cache sizes. SnF generally outperforms other architectures. SnF is
especially advantageous in a small cache setting, so it works well with a
smaller cache size to reduce silicon area. In a small cache setting, the miss
ratio of feature access, which SnF targets to minimize, increases, so SnF
provides more speedup over other accelerators. For example, in the 2MB
setting, SnF shows 96.7% improvement over VT, while the improvement of the
16MB setting is 73.1% which is still a significant speedup.

###  6.11. Sensitivity to Cache Configuration

PDCTPKYTLJOKRDGmean$0$$0.5$$1$SpeedupDefaultRandomRRIP8-ways32-ways32B
block128B block256B block Figure 18. Sensitivity to various cache
configurations.

Figure 18 shows the sensitivity to various cache configurations, including
replacement policies, number of ways, and block size. For replacement, we have
tested random and RRIP (Zhang et al., 2010). Random replacement resulted in an
surprisingly worse speedup, due to its inability to capture the locality. RRIP
was able to gain a marginal amount of speedup, but it was not enough to
justify the additional cost for storing more states. While number of ways did
not provide much changes, block sizes altered much performance. When
decreased, it becomes lower then the size of the DRAM burst, wasting a lot of
the bandwidth. When increased, the size exceeded the trivial spatial locality
of the feature slicing, and the speedup degraded.

###  6.12. Sensitivity on $B_{F}$ and $B_{V}$

Figure 19. Sensitivity on $B_{F}$ and $B_{V}$.

Figure 19 shows the sensitivity of SnF with respect to $B_{F}$ and $B_{V}$ on
three selected datasets. The results exemplify the difficulty of tuning the
number of vertex tiles $B_{V}$. The optimal configuration is usually found on
$B_{F}$=16 (the maximum), which supports our strategy to use feature slicing
and then to adaptively find optimal $B_{V}$. $B_{V}$, on the other side, is
harder to tune since it depends too much on the individual graph topology.
Larger graphs favor larger $B_{V}$ because larger graphs would be harder to
fit into caches.

1 2 4 8 16 32 64 128 $0$ $20$ $40$ $60$ $80$ $100$ $B_{F}\times B_{V}$Cache
Miss (%)VTSnF 1 2 4 8 16 32 64 128 $0$ $10$ $20$ $30$ $B_{F}\times B_{V}$Mem.
Acc.s (GB)VT Topo.VT Feat.SnF Topo.SnF Feat. Figure 20. Miss rate (left) and
memory access (right) according to $B_{F}\times B_{V}$.

Figure 20 (left) shows the cache miss rate, with respect to $B_{F}\times
B_{V}$ observed for PK dataset. The miss rate decreases as $B_{F}\times B_{V}$
becomes larger as the working set size decreases. The miss rate drops for VT
only and SnF are mostly similar, showing that our assumption for the cost
model generally holds in that the miss rate is roughly a function of the
working set size.

Figure 20 (right) shows the memory access count breakdown that explains how
the miss rates and repetition counts are translated into performance. The
green bars represent the feature accesses, and the purple bars represent the
topology data accesses. In vertex tiling, the repetition count being added to
the output feature accesses offsets the gain from the miss rate drop and
results in a diminishing return. However, with SnF, the miss rate drop is
almost directly translated into memory access reduction as the repetition is
added to smaller topology data.

###  6.13. Multi-Chip Module Scaling Results

PDCTPKYTLJOKRDGmean$0$$1$$2$SpeedupVTHyGCNEnGNAWB-GCNGCNAXSnF Figure 21.
Performance of the multi-chip accelerator. Figure 22. Multi-chip scaling
results (left) and execution time breakdown (right).

Figure 21 shows the multi-chip-module (MCM) accelerator performance where 16
chips in total form a module. Following other MCM accelerators (Shao et al.,
2019; Arunkumar et al., 2017) we use 256 GB/s bandwidth ring interconnect,
with $20\text{\,}\mathrm{ns}$ per-hop latency. Even though all accelerators
use the same strategy explained in Section 5, SnF achieves superior speedup
over all others. Further scaling results are provided in Figure 22. On the
left, it plots the scalability according to the interconnect bandwidth. Using
interconnect with high bandwidth, it scales to some degree, but its speedup is
limited for low-bandwidth interconnects. On the right, the figure shows the
breakdown of combination, aggregation and the communication overhead not
hidden by the overlap.

The data with a large average degree such as PD, OK and RD scale well, because
the communication time depends on the features per vertex and the computation
time generally is proportional to the number of edges. On the other hand, low-
degree graph such as YT shows poor scalability due to the low average degree
and thus high communication overhead.

###  6.14. Experiments on Small-Scale Datasets

CoraCiteseerPubmedNellGmean$0$$1$$2$$3$SpeedupVTHyGCNEnGNAWB-GCNGCNAXSnF (a)
Speedup on small-scale datasets.

CoraCiteseerPubmedNellReddit$0$$0.5$$1$$1.5$$2$$\cdot 10^{7}$Cycles (b) Cycles
to process GCN computation.

Figure 23. Results on small-scale datasets.

In addition to the datasets we evaluated, there exist some small-scale
datasets often evaluated in some prior art (Li et al., 2021a; Geng et al.,
2020; Yan et al., 2020): Cora, Citeseer (Sen et al., 2008), Pubmed (Hamilton
et al., 2017a), and Nell (Carlson et al., 2010). To make a fair comparison, we
also report performance on those datasets in Figure 23. We used 512 KB caches
sizes for all architectures following (Li et al., 2021a). The performance
improvement of SnF over the baseline is 106%, which is much larger than the
results SnF gets from large datasets, as depicted in Figure 23(a). The results
align with the observations from previous work (Geng et al., 2020; Li et al.,
2021a). However, we do not use these small-scale datasets for our main
evaluation because these datasets often contain only a few thousands of
vertices and thus consume tiny cycles to compute GCN compared to larger ones,
as illustrated in Figure 23(b).

##  7\. Related Work

###  7.1. Accelerators for GCN and Graph Processing

There are many existing architectural approaches that aim to accelerate GCNs.
HyGCN (Yan et al., 2020) proposed the hybrid computation architecture using
the characteristic difference in the aggregation and the combination phase in
GCNs. GNNA (Auten et al., 2020) used a tiled architecture to accelerate GCN.
EnGN (Liang et al., 2020) adopted a tiled topology data and gathered
information about highly visited vertices to allocate some portion of cache
for them to enhance cache efficiency. Moreover, GCNAX (Li et al., 2021a) uses
a perfect tiling strategy by doing off-line analysis, which finds the best
dataflow and tiling configuration. However, their perfect tiling over-
estimates a required buffer size, leading to suboptimal performance. In
contrast, this paper focuses on cache efficiency and claims that feature
slicing often provides a better efficiency than prior solutions. AWB-GCN (Geng
et al., 2020) used column-based execution and gave insight into distributing
workload. Recent work also supports variants of GCNs that integrate the edge
information or self-attention into GCNs. SnF shows a similar speedup for such
GCN variants because feature slicing and dynamic analysis technology can be
easily applied without much challenge.

Not only GCNs, but classic graph processing has been an important application
for decades, and there were various works which propose dedicated
accelerators. They utilized ASICs (Ham et al., 2016; Ozdal et al., 2016; Yao
et al., 2020), FPGAs (Lee et al., 2017; Dadu et al., 2021; Asiatici and Ienne,
2021), or both (Chen et al., 2021) to implement these accelerators. Focusing
on their memory-intensive nature, there were accelerators that utilize
3D-stacked memories (Pawlowski, 2011) as a processing-in-memory accelerator
(Ahn et al., 2015; Zhuo et al., 2019; Zhang et al., 2018), or modify flash
storage to be friendly for graph processing.

Unfortunately, the computational pattern of such classic graph processing is
distinct from that of the GCNs, because the features associated with each
vertex is often shallow, with one or two elements per vertex. Because GCNs
exhibit hybrid computational pattern and the feature vector associated with
each vertex is relatively long, GCN accelerators require different design from
that of the graph processing accelerators.

###  7.2. Memory Aware Accelerators for DNNs

DNN acceleration often accompanies memory-bound operations, so many works
optimize memory bandwidth for successful speedup (Rhu et al., 2016; Hyun et
al., 2020; Siu et al., 2018). Some works precisely select the dataflow (Du et
al., 2015; Chen et al., 2016; Jouppi et al., 2017) or block data (Yang et al.,
2018) to improve data reuse. On-chip memory management is also crucial for
optimization. Many works try to efficiently deal with on-chip memory by
scheduling, allocation, or sharing (Wei et al., 2019; Li et al., 2018b; Jin
and Hong, 2019). DNNs often include of multiple layers, which can be utilized
to optimize memory usage (Alwani et al., 2016; Huang et al., 2019; Lym et al.,
2019; Jung et al., 2019). This characteristic can be adopted not only for
inference (Alwani et al., 2016; Huang et al., 2019) and training (Lym et al.,
2019) but also for batch normalization (Jung et al., 2019).

These methods apply to the regular access pattern of conventional DNNs, which
is not directly applicable to GCNs. Therefore, GCN accelerator designs are
different from conventional DNN accelerator designs because they target the
irregular accesses.

###  7.3. Sparse DNN Accelerators

Some DNN accelerators attempt to utilize sparsity in DNNs. Computation pruning
(Hua et al., 2019; Niu et al., 2020; Silfa et al., 2019) was a popular target
because it can easily apply to existing hardware designs. Sparse operation
support (Zhu et al., 2019; Wang et al., 2021) or algebraic sparsity
exploration (Huang, 2021) were also studied. There are also zero-value aware
designs , such as removing zero-value weights (Han et al., 2016; Zhang et al.,
2016; Zhou et al., 2018; Albericio et al., 2016; Ding et al., 2017) or
considering zero-value activations (Parashar et al., 2017; Gondimalla et al.,
2019; Judd et al., 2017; Jang et al., 2021). Some designs target SpMV (Sadi et
al., 2019; Asgari et al., 2020) and SpMM (Zhang et al., 2020; Hegde et al.,
2019; Qin et al., 2020), which can be used to exploit sparsity in DNNs. In
addition, some works (Kanellopoulos et al., 2019; Srivastava et al., 2020;
Pentecost et al., 2019; Yang et al., 2021) co-designed software and hardware
for tensor compression. However, the sparsity targeted from these work is
often far below that of the GCNs, because the sparsity of graph topology is
near 100%, which is difficult for pruned DNNs or zero-valued activations to
reach. Therefore, despite the much work on sparse DNN accelerations, there
exists a need for dedicated GCN accelerators.

##  8\. Conclusion

We have proposed slice-and-forge, an accelerator design oriented at
efficiently utilizing the caches for GCN accelerators. With feature slicing,
slice-and-forge greatly improves the effectiveness of the limited on-chip
cache compared to previous work. Taking advantage of the fact that feature
slicing yields multiple exact same computational patterns, we further propose
automatic tile morphing that dynamically configures the tiling for better
cache efficiency. Experimental results show that slice-and-forge achieves
superior performance over the existing designs, and provides relaxation for
the need for off-line analysis.

###### 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, Hyeyoon Lee, Jounghoo Lee, and Youngsok Kim are with the Department of
Computer Science at Yonsei University and have been 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)
  * Ahn et al. (2015) Junwhan Ahn, Sungpack Hong, Sungjoo Yoo, Onur Mutlu, and Kiyoung Choi. 2015.  A scalable processing-in-memory accelerator for parallel graph processing. In _ISCA_.
  * Aktulga et al. (2014) Hasan Metin Aktulga, Aydin Buluç, Samuel Williams, and Chao Yang. 2014.  Optimizing sparse matrix-multiple vectors multiplication for nuclear configuration interaction calculations. In _IPDPS_.
  * Albericio et al. (2016) Jorge Albericio, Patrick Judd, Tayler Hetherington, Tor Aamodt, Natalie Enright Jerger, and Andreas Moshovos. 2016.  Cnvlutin: Ineffectual-Neuron-Free Deep Neural Network Computing. In _ISCA_.
  * Alwani et al. (2016) Manoj Alwani, Han Chen, Michael Ferdman, and Peter Milder. 2016\.  Fused-layer CNN accelerators. In _MICRO_.
  * Arunkumar et al. (2017) Akhil Arunkumar, Evgeny Bolotin, Benjamin Cho, Ugljesa Milic, Eiman Ebrahimi, Oreste Villa, Aamer Jaleel, Carole-Jean Wu, and David Nellans. 2017.  MCM-GPU: Multi-chip-module GPUs for continued performance scalability.  _MICRO_ 45, 2 (2017), 320–332.
  * Asgari et al. (2020) Bahar Asgari, Ramyad Hadidi, Tushar Krishna, Hyesoon Kim, and Sudhakar Yalamanchili. 2020\.  ALRESCHA: A Lightweight Reconfigurable Sparse-Computation Accelerator. In _HPCA_.
  * Asiatici and Ienne (2021) Mikhail Asiatici and Paolo Ienne. 2021.  Large-Scale Graph Processing on FPGAs with Caches for Thousands of Simultaneous Misses. In _ISCA_.
  * Auten et al. (2020) Adam Auten, Matthew Tomei, and Rakesh Kumar. 2020\.  Hardware acceleration of graph neural networks. In _DAC_.
  * Carlson et al. (2010) Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka, and Tom M. Mitchell. 2010.  Toward an Architecture for Never-Ending Language Learning. In _Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence_ (Atlanta, Georgia) _(AAAI’10)_. AAAI Press, 1306–1313.
  * Chen et al. (2021) Xuhao Chen, Tianhao Huang, Shuotao Xu, Thomas Bourgeat, Chanwoo Chung, and Arvind. 2021\.  FlexMiner: A Pattern-Aware Accelerator for Graph Pattern Mining. In _ISCA_.
  * Chen et al. (2020) Xiaobing Chen, Yuke Wang, Xinfeng Xie, Xing Hu, Abanti Basak, Ling Liang, Mingyu Yan, Lei Deng, Yufei Ding, Zidong Du, Yunji Chen, and Yuan Xie. 2020\.  Rubik: A Hierarchical Architecture for Efficient Graph Learning.  _CoRR_ abs/2009.12495 (2020).  arXiv:2009.12495 https://arxiv.org/abs/2009.12495
  * Chen et al. (2016) Yu-Hsin Chen, Tushar Krishna, Joel S Emer, and Vivienne Sze. 2016.  Eyeriss: An energy-efficient reconfigurable accelerator for deep convolutional neural networks.  _JSSC_ (2016).
  * Dadu et al. (2021) Vidushi Dadu, Sihao Liu, and Tony Nowatzki. 2021.  PolyGraph: Exposing the Value of Flexibility for Graph Processing Accelerators. In _ISCA_.
  * Ding et al. (2017) Caiwen Ding, Siyu Liao, Yanzhi Wang, Zhe Li, Ning Liu, Youwei Zhuo, Chao Wang, Xuehai Qian, Yu Bai, Geng Yuan, Xiaolong Ma, Yipeng Zhang, Jian Tang, Qinru Qiu, Xue Lin, and Bo Yuan. 2017\.  CirCNN: Accelerating and Compressing Deep Neural Networks Using Block-Circulant Weight Matrices. In _MICRO_.
  * Du et al. (2015) Zidong Du, Robert Fasthuber, Tianshi Chen, Paolo Ienne, Ling Li, Tao Luo, Xiaobing Feng, Yunji Chen, and Olivier Temam. 2015.  ShiDianNao: Shifting vision processing closer to the sensor. In _ISCA_.
  * Fout et al. (2017) Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. 2017\.  Protein interface prediction using graph convolutional networks. In _NeurIPS_.
  * Geng et al. (2020) Tong Geng, Ang Li, Runbin Shi, Chunshu Wu, Tianqi Wang, Yanfei Li, Pouya Haghi, Antonino Tumeo, Shuai Che, Steve Reinhardt, and Martin C. Herbordt. 2020.  AWB-GCN: A graph convolutional network accelerator with runtime workload rebalancing. In _MICRO_.
  * Geng et al. (2021) Tong Geng, Chunshu Wu, Yongan Zhang, Cheng Tan, Chenhao Xie, Haoran You, Martin Herbordt, Yingyan Lin, and Ang Li. 2021.  I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization. In _MICRO_. Association for Computing Machinery, New York, NY, USA, 1051–1063.  https://doi.org/10.1145/3466752.3480113
  * Gondimalla et al. (2019) Ashish Gondimalla, Noah Chesnut, Mithuna Thottethodi, and T. N. Vijaykumar. 2019.  SparTen: A Sparse Tensor Accelerator for Convolutional Neural Networks. In _MICRO_.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _KDD_.
  * Ham et al. (2016) Tae Jun Ham, Lisa Wu, Narayanan Sundaram, Nadathur Satish, and Margaret Martonosi. 2016.  Graphicionado: A high-performance and energy-efficient accelerator for graph analytics. In _MICRO_.
  * Hamilton et al. (2017a) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017a.  Inductive Representation Learning on Large Graphs. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf
  * Hamilton et al. (2017b) William L Hamilton, Rex Ying, and Jure Leskovec. 2017b.  Inductive representation learning on large graphs. In _NeurIPS_.
  * Han et al. (2016) Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A Horowitz, and William J Dally. 2016.  EIE: Efficient Inference Engine on Compressed Deep Neural Network. In _ISCA_.
  * Hegde et al. (2019) Kartik Hegde, Hadi Asghari-Moghaddam, Michael Pellauer, Neal Crago, Aamer Jaleel, Edgar Solomonik, Joel Emer, and Christopher W Fletcher. 2019\.  ExTensor: An accelerator for sparse tensor algebra. In _MICRO_.
  * Hong et al. (2019) Changwan Hong, Aravind Sukumaran-Rajam, Israt Nisa, Kunal Singh, and P Sadayappan. 2019\.  Adaptive sparse tiling for sparse matrix multiplication. In _PPoPP_.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open graph benchmark: Datasets for machine learning on graphs.  _arXiv preprint_ (2020).
  * Hua et al. (2019) Weizhe Hua, Yuan Zhou, Christopher De Sa, Zhiru Zhang, and G. Edward Suh. 2019.  Boosting the Performance of CNN Accelerators with Dynamic Fine-Grained Channel Gating. In _MICRO_.
  * Huang (2021) Chao-Tsung Huang. 2021\.  RingCNN: Exploiting Algebraically-Sparse Ring Tensors for Energy-Efficient CNN-Based Computational Imaging. In _ISCA_.
  * Huang et al. (2019) Chao-Tsung Huang, Yu-Chun Ding, Huan-Ching Wang, Chi-Wen Weng, Kai-Ping Lin, Li-Wei Wang, and Li-De Chen. 2019.  eCNN: A block-based and highly-parallel CNN accelerator for edge inference. In _MICRO_.
  * Hyun et al. (2020) Bongjoon Hyun, Youngeun Kwon, Yujeong Choi, John Kim, and Minsoo Rhu. 2020.  NeuMMU: Architectural Support for Efficient Address Translations in NPUs. In _ASPLOS_.
  * Jang et al. (2021) Jun-Woo Jang, Sehwan Lee, Dongyoung Kim, Hyunsun Park, Ali Shafiee Ardestani, Yeongjae Choi, Channoh Kim, Yoojin Kim, Hyeongseok Yu, Hamzah Abdel-Aziz, Jun-Seok Park, Heonsoo Lee, Dongwoo Lee, Myeong Woo Kim, Hanwoong Jung, Heewoo Nam, Dongguen Lim, Seungwon Lee, Joon-Ho Song, Suknam Kwon, Joseph Hassoun, SukHwan Lim, and Changkyu Choi. 2021.  Sparsity-Aware and Re-configurable NPU Architecture for Samsung Flagship Mobile SoC. In _ISCA_.
  * Jin and Hong (2019) Tian Jin and Seokin Hong. 2019.  Split-CNN: Splitting window-based operations in convolutional neural networks for memory system optimization. In _ASPLOS_.
  * Jouppi et al. (2017) Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, Rick Boyle, Pierre-luc Cantin, Clifford Chao, Chris Clark, Jeremy Coriell, Mike Daley, Matt Dau, Jeffrey Dean, Ben Gelb, Tara Vazir Ghaemmaghami, Rajendra Gottipati, William Gulland, Robert Hagmann, C. Richard Ho, Doug Hogberg, John Hu, Robert Hundt, Dan Hurt, Julian Ibarz, Aaron Jaffey, Alek Jaworski, Alexander Kaplan, Harshit Khaitan, Daniel Killebrew, Andy Koch, Naveen Kumar, Steve Lacy, James Laudon, James Law, Diemthu Le, Chris Leary, Zhuyuan Liu, Kyle Lucke, Alan Lundin, Gordon MacKean, Adriana Maggiore, Maire Mahony, Kieran Miller, Rahul Nagarajan, Ravi Narayanaswami, Ray Ni, Kathy Nix, Thomas Norrie, Mark Omernick, Narayana Penukonda, Andy Phelps, Jonathan Ross, Matt Ross, Amir Salek, Emad Samadiani, Chris Severn, Gregory Sizikov, Matthew Snelham, Jed Souter, Dan Steinberg, Andy Swing, Mercedes Tan, Gregory Thorson, Bo Tian, Horia Toma, Erick Tuttle, Vijay Vasudevan, Richard Walter, Walter Wang, Eric Wilcox, and Doe Hyun Yoon. 2017\.  In-datacenter performance analysis of a tensor processing unit. In _ISCA_.
  * Judd et al. (2017) Patric Judd, Alberto Delmas, Sayeh Sharify, and Andreas Moshovos. 2017.  Cnvlutin2: Ineffectual-Activation-and-Weight-Free Deep Neural Network Computing.  _arXiv preprint_ (2017).
  * Jung et al. (2019) Daejin Jung, Wonkyung Jung, Byeongho Kim, Sunjung Lee, Wonjong Rhee, and Jung Ho Ahn. 2019\.  Restructuring batch normalization to accelerate CNN training. In _SysML_.
  * Kanellopoulos et al. (2019) Konstantinos Kanellopoulos, Nandita Vijaykumar, Christina Giannoula, Roknoddin Azizi, Skanda Koppula, Nika Mansouri Ghiasi, Taha Shahroodi, Juan Gomez Luna, and Onur Mutlu. 2019\.  Smash: Co-designing software compression and hardware-accelerated indexing for efficient sparse matrix operations. In _MICRO_.
  * Kiningham et al. (2020) Kevin Kiningham, Christopher Re, and Philip Levis. 2020\.  GRIP: A graph neural network accelerator architecture.  _arXiv preprint_ (2020).
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint_ (2016).
  * Lee et al. (2017) Jinho Lee, Heesu Kim, Sungjoo Yoo, Kiyoung Choi, H Peter Hofstee, Gi-Joon Nam, Mark R Nutter, and Damir Jamsek. 2017\.  ExtraV: Boosting graph processing near storage with a coherent accelerator.  _pVLDB_ (2017).
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: Densification laws, shrinking diameters and possible explanations. In _KDD_.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Leskovec et al. (2009) Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney. 2009.  Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters.  _Internet Mathematics_ 6, 1 (2009), 29–123.
  * Li et al. (2019) Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. 2019.  DeepGCNs: Can GCNs go as deep as CNNs?. In _ICCV_.
  * Li et al. (2021b) Han Li, Mingyu Yan, Xiaocheng Yang, Lei Deng, Wenming Li, Xiaochun Ye, Dongrui Fan, and Yuan Xie. 2021b.  Hardware Acceleration for GCNs via Bidirectional Fusion.  _IEEE Computer Architecture Letters_ (2021).
  * Li et al. (2021a) Jiajun Li, Ahmed Louri, Avinash Karanth, and Razvan Bunescu. 2021a.  GCNAX: A flexible and energy-efficient accelerator for graph convolutional neural networks. In _HPCA_.
  * Li et al. (2018b) Jiajun Li, Guihai Yan, Wenyan Lu, Shuhao Jiang, Shijun Gong, Jingya Wu, and Xiaowei Li. 2018b.  SmartShuttle: Optimizing off-chip memory accesses for deep learning accelerators. In _DATE_.
  * Li et al. (2018a) Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018a.  Deeper insights into graph convolutional networks for semi-supervised learning. In _AAAI_.
  * Li et al. (2020) Shang Li, Zhiyuan Yang, Dhiraj Reddy, Ankur Srivastava, and Bruce Jacob. 2020.  DRAMsim3: A cycle-accurate, thermal-capable DRAM simulator.  _CAL_ (2020).
  * Liang et al. (2020) Shengwen Liang, Ying Wang, Cheng Liu, Lei He, LI Huawei, Dawen Xu, and Xiaowei Li. 2020.  EnGN: A high-throughput and energy-efficient accelerator for large graph neural networks.  _TC_ (2020).
  * Lym et al. (2019) Sangkug Lym, Armand Behroozi, Wei Wen, Ge Li, Yongkee Kwon, and Mattan Erez. 2019\.  Mini-batch serialization: CNN training with inter-layer data reuse. In _SysML_.
  * Niu et al. (2020) Wei Niu, Xiaolong Ma, Sheng Lin, Shihao Wang, Xuehai Qian, Xue Lin, Yanzhi Wang, and Bin Ren. 2020\.  PatDNN: Achieving Real-Time DNN Execution on Mobile Devices with Pattern-based Weight Pruning. In _ASPLOS_.
  * Ozdal et al. (2016) Muhammet Mustafa Ozdal, Serif Yesil, Taemin Kim, Andrey Ayupov, John Greth, Steven Burns, and Ozcan Ozturk. 2016\.  Energy efficient architecture for graph analytics accelerators. In _ISCA_.
  * Parashar et al. (2017) Angshuman Parashar, Minsoo Rhu, Anurag Mukkara, Antonio Puglielli, Rangharajan Venkatesan, Brucek Khailany, Joel Emer, Stephen W. Keckler, and William J. Dally. 2017.  SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks. In _ISCA_.
  * Pawlowski (2011) J Thomas Pawlowski. 2011\.  Hybrid memory cube (HMC). In _Hot Chips_.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  GloVe: Global Vectors for Word Representation. In _Empirical Methods in Natural Language Processing (EMNLP)_. 1532–1543.  http://www.aclweb.org/anthology/D14-1162
  * Pentecost et al. (2019) Lillian Pentecost, Marco Donato, Brandon Reagen, Udit Gupta, Siming Ma, Gu-Yeon Wei, and David Brooks. 2019.  MaxNVM: Maximizing DNN Storage Density and Inference Efficiency with Sparse Encoding and Error Mitigation. In _MICRO_.
  * Qin et al. (2020) Eric Qin, Ananda Samajdar, Hyoukjun Kwon, Vineet Nadella, Sudarshan Srinivasan, Dipankar Das, Bharat Kaul, and Tushar Krishna. 2020\.  SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN Training. In _HPCA_.
  * Rhu et al. (2016) Minsoo Rhu, Natalia Gimelshein, Jason Clemons, Arslan Zulfiqar, and Stephen W. Keckler. 2016\.  vDNN: Virtualized Deep Neural Networks for Scalable, Memory-Efficient Neural Network Design. In _MICRO_.
  * Sadi et al. (2019) Fazle Sadi, Joe Sweeney, Tze Meng Low, James C. Hoe, Larry Pileggi, and Franz Franchetti. 2019\.  Efficient SpMV Operation for Large and Highly Sparse Matrices using Scalable Multi-way Merge Parallelization. In _MICRO_.
  * Samajdar et al. (2018) Ananda Samajdar, Yuhao Zhu, Paul Whatmough, Matthew Mattina, and Tushar Krishna. 2018.  SCALE-Sim: Systolic CNN accelerator simulator.  _arXiv preprint_ (2018).
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008\.  Collective Classification in Network Data.  _AI Magazine_ 29, 3 (Sep. 2008), 93\.  https://doi.org/10.1609/aimag.v29i3.2157
  * Shao et al. (2019) Yakun Sophia Shao, Jason Clemons, Rangharajan Venkatesan, Brian Zimmer, Matthew Fojtik, Nan Jiang, Ben Keller, Alicia Klinefelter, Nathaniel Pinckney, Priyanka Raina, Stephen G. Tell, Yanqing Zhang, William J. Dally, Joel Emer, C. Thomas Gray, Brucek Khailany, and Stephen W. Keckler. 2019.  Simba: Scaling deep-learning inference with multi-chip-module-based architecture. In _MICRO_. 14–27.
  * Silfa et al. (2019) Franyell Silfa, Gem Dot, Jose-Maria Arnau, and Antonio Gonazàlez. 2019.  Neuron-Level Fuzzy Memoization in RNNs. In _MICRO_.
  * Siu et al. (2018) Kevin Siu, Dylan Malone Stuart, Mostafa Mahmoud, and Andreas Moshovos. 2018.  Memory Requirements for Convolutional Neural Network Hardware Accelerators. In _IISWC_.
  * Srivastava et al. (2020) Nitish Srivastava, Hanchen Jin, Shaden Smith, Hongbo Rong, David Albonesi, and Zhiru Zhang. 2020\.  Tensaurus: A Versatile Accelerator for Mixed Sparse-Dense Tensor Computations. In _HPCA_.
  * Takac and Zabovsky (2012) Lubos Takac and Michal Zabovsky. 2012.  Data analysis in public social networks. In _DTI_.
  * Thakur et al. (2005) Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005\.  Optimization of Collective Communication Operations in MPICH.  _IJHPCA_ (2005).
  * Thoziyoor et al. (2008) Shyamkumar Thoziyoor, Naveen Muralimanohar, Jung Ho Ahn, and Norman P Jouppi. 2008.  _CACTI 5.1_.  Technical Report. 2008-20, HP Labs.
  * Vashishth (2019) Shikhar Vashishth. 2019\.  Neural graph embedding methods for natural language processing.  _arXiv preprint_ (2019).
  * Wang et al. (2020) Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. 2020\.  Microsoft academic graph: When experts are not enough.  _Quantitative Science Studies_ 1, 1 (2020), 396–413.
  * Wang et al. (2021) Yang Wang, Chen Zhang, Zhiqiang Xie, Cong Guo, Yunxin Liu, and Jingwen Leng. 2021\.  Dual-side Sparse Tensor Core. In _ISCA_.
  * Wei et al. (2019) Xuechao Wei, Yun Liang, and Jason Cong. 2019.  Overcoming Data Transfer Bottlenecks in FPGA-based DNN Accelerators via Layer Conscious Memory Management. In _DAC_.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _arXiv preprint_ (2018).
  * Yan et al. (2020) Mingyu Yan, Lei Deng, Xing Hu, Ling Liang, Yujing Feng, Xiaochun Ye, Zhimin Zhang, Dongrui Fan, and Yuan Xie. 2020.  HyGCN: A gcn accelerator with hybrid architecture. In _HPCA_.
  * Yanardag and Vishwanathan (2015) Pinar Yanardag and SVN Vishwanathan. 2015.  Deep graph kernels. In _KDD_.
  * Yang and Leskovec (2015) Jaewon Yang and Jure Leskovec. 2015.  Defining and evaluating network communities based on ground-truth.  _Knowledge and Information Systems_ 42, 1 (2015), 181–213.
  * Yang et al. (2018) Xuan Yang, Mingyu Gao, Jing Pu, Ankita Nayak, Qiaoyi Liu, Steven Emberton Bell, Jeff Ou Setter, Kaidi Cao, Heonjae Ha, Christos Kozyrakis, and Mark Horowitz. 2018.  DNN dataflow choice is overrated.  _arXiv preprint_ (2018).
  * Yang et al. (2021) Yifan Yang, J. Emer, and Daniel Sánchez. 2021.  SpZip: Architectural Support for Effective Data Compression In Irregular Applications. In _ISCA_.
  * Yao et al. (2020) Pengcheng Yao, Long Zheng, Zhen Zeng, Yu Huang, Chuangyi Gui, Xiaofei Liao, Hai Jin, and Jingling Xue. 2020\.  A locality-aware energy-efficient accelerator for graph mining applications. In _MICRO_.
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen. 2018.  Link prediction based on graph neural networks. In _NeurIPS_.
  * Zhang et al. (2018) Mingxing Zhang, Youwei Zhuo, Chao Wang, Mingyu Gao, Yongwei Wu, Kang Chen, Christos Kozyrakis, and Xuehai Qian. 2018\.  GraphP: Reducing communication for PIM-based graph processing with efficient data partition. In _HPCA_.
  * Zhang et al. (2016) Shijin Zhang, Zidong Du, Lei Zhang, Huiyang Lan, Shaoli Liu, Ling Li, Qi Guo, Tianshi Chen, and Yunji Chen. 2016\.  Cambricon-X: An Accelerator for Sparse Neural Networks. In _MICRO_.
  * Zhang et al. (2010) Xi Zhang, Chongmin Li, Haixia Wang, and Dongsheng Wang. 2010\.  A Cache Replacement Policy Using Adaptive Insertion and Re-reference Prediction. In _2010 22nd International Symposium on Computer Architecture and High Performance Computing_. 95–102.  https://doi.org/10.1109/SBAC-PAD.2010.21
  * Zhang et al. (2020) Zhekai Zhang, Hanrui Wang, Song Han, and William J. Dally. 2020\.  SpArch: Efficient Architecture for Sparse Matrix Multiplication. In _HPCA_.
  * Zheng et al. (2016) Da Zheng, Disa Mhembere, Vince Lyzinski, Joshua T Vogelstein, Carey E Priebe, and Randal Burns. 2016\.  Semi-external memory sparse matrix multiplication for billion-node graphs.  _TPDS_ (2016).
  * Zhou et al. (2018) Xuda Zhou, Zidong Du, Qi Guo, Shaoli Liu, Chengsi Liu, Chao Wang, Xuehai Zhou, Ling Li, Tianshi Chen, and Yunji Chen. 2018\.  Cambricon-S: Addressing Irregularity in Sparse Neural Networks through a Cooperative Software/Hardware Approach. In _MICRO_.
  * Zhu et al. (2019) Maohua Zhu, Tao Zhang, Zhenyu Gu, and Yuan Xie. 2019\.  Sparse Tensor Core: Algorithm and Hardware Co-Design for Vector-wise Sparse Neural Networks on Modern GPUs. In _MICRO_.
  * Zhu et al. (2015) Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015.  GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In _ATC_.
  * Zhuo et al. (2019) Youwei Zhuo, Chao Wang, Mingxing Zhang, Rui Wang, Dimin Niu, Yanzhi Wang, and Xuehai Qian. 2019.  GraphQ: Scalable PIM-based graph processing. In _MICRO_.