1.   Introduction

In recent years, deep learning over graph data has achieved great success in a broad range of applications, such as traffic prediction^[1], object detection^[2], and disease classification^[3]. One of the most successful models is Graph Convolutional Neural Network (GCN)^[4] that re-defines the notion of convolution for graph data, and has been widely used in data centers of Google, Alibaba^[5], and Facebook^[6].

Just like traditional neural networks, training and inference of GCNs are both compute- and memory-intensive, which poses a major challenge to the hardware platforms. Typically, the graph convolutional layers occupy the majority of execution time in GCNs^{[7, 8]} through two primary phases: aggregation and combination. The computation in the combination phase is similar to that in conventional neural networks. However, the aggregation phase relies on the graph structure, which is often sparse and irregular. This difference imposes new requirements on the design of GCN architectures.

The key computation pattern in GCNs can be abstracted as chain sparse-dense matrix multiplications (SpMMs)^[9]. It involves six loops that result in a large design space for GCN accelerators in terms of parallelism, computation partitioning and scheduling. These problems can be handled by the existing loop optimization techniques^[10], such as loop tiling, loop unrolling, loop interchange and loop fusion. Recently, a few customized GCN accelerators^{[9, 11, 12]} have leveraged these techniques to deliver gains in performance and energy efficiency. However, none of them has systematically studied the impact of these techniques on system efficiency in terms of latency, on-chip SRAM accesses and off-chip DRAM accesses. Instead, they either employ limited loop optimization techniques, or determine the design variables based on random sampling. As a result, they can hardly exploit data reuse efficiently, leading to increased memory accesses. As memory access is much more expensive than computation^[13], it will significantly degrade the energy efficiency.

To this end, this paper proposes GShuttle, a GCN acceleration scheme that maximizes memory access efficiency to improve energy efficiency. First, we provide an in-depth analysis of the four loop optimization techniques for GCN computation and use corresponding design variables to characterize different acceleration schemes. We then build analytical models to quantitatively estimate the design objectives of GCN accelerators, such as on-chip SRAM accesses and off-chip DRAM accesses. Based on the analytical models, we formulate the accelerator design as an optimization problem, which aims to find the best combination of design variables that maximizes the design objectives under certain design constraints, such as on-chip storage size and the number of processing elements (PEs). We further propose two algorithms, namely pruned search space sweeping (PSSS) and greedy search (GS), to address the problem. PSSS prunes the search space to make the search practically manageable, while GS leverages empirical rules concluded from simulation results to further reduce the time complexity of the search. To demonstrate the efficacy of the proposed framework, we simulate the corresponding hardware accelerators based on the design variables derived from GShuttle. The experimental simulations show that our approach reduces DRAM accesses by a factor of 1.5 and saves energy by a factor of 1.7 on average compared with the state-of-the-art approaches.

In summary, this paper makes the following contributions.

• Problem Definition. We define an optimization problem for GCN accelerator designs to maximize memory access efficiency based on an in-depth analysis of the loop optimization techniques and analytical models.

• Search Algorithms. We develop two search algorithms to solve the optimization problem to find a solution within a reasonable amount of time.

• Framework Validation. We build an accelerator simulator based on the design variables obtained from GShuttle, and performed simulation studies to demonstrate the efficacy of the proposed framework.

This paper is a significantly extended and revised version of [12]. In [12], we proposed a flexible and energy-efficient accelerator for GCNs. However, [12] mainly focuses on the dataflow optimization and has not systematically explored the optimization of memory accesses. In this paper, we propose GShutte which maximizes memory access efficiency (including both DRAM and SRAM accesses) to achieve high performance and energy efficiency.

The rest of the paper is organized as follows. Section 2 summarizes the key design variables that characterize the loop optimization techniques for GCN acceleration. Section 3 describes the optimization problem that maximizes the memory access efficiency under certain constraints based on the analytical models that estimate the on-chip SRAM and off-chip DRAM accesses, and presents two approaches to solve the optimization problem to find the best combination design variables within a reasonable amount of time. Section 4 describes the experimental methodology, and presents the experimental results in comparison with prior work. Section 5 introduces related work and Section 6 concludes the paper.

2.   GCN Acceleration

2.1   GCN Computation

The typical structure of a graph convolutional layer is illustrated in Fig.1. The main computation of the GCN models^[14-16] can be abstracted as a chain SpMM:

Figure  1.  Illustration of a GCN layer. The graph contains six nodes. A: adjacency matrix, ${{\boldsymbol{X}}}^{(l)}$: feature vectors of layer $l$, ${{\boldsymbol{W}}}^{(l)}$: weight matrix of layer $l$, and ${{\boldsymbol{X}}}^{(l+1)}$: feature vectors of layer $l+1$.

下载: 全尺寸图片 幻灯片

where ${{\boldsymbol{X}}}^{(l)}$ is the matrix of input features in layer $l$; each column of ${{\boldsymbol{X}}}$ represents a feature vector while each row denotes a node. ${{\boldsymbol{W}}}^{(l)}$ is the weight matrix of layer $l$. $\sigma(\cdot)$ denotes the non-linear activation function such as ReLU. $\hat{{{\boldsymbol{A}}}}$ is a transformed matrix from the graph adjacency matrix. The transformation function varies across different GCN models. Since $\hat{\boldsymbol A}$ can be computed offline from A, we hereafter use A to denote the normalized $\hat{\boldsymbol A}$.

The chain SpMM in GCNs consists of six loops as shown in the pseudocode in Fig.2. We assume that $\boldsymbol A\in \mathbb{R}^{M\times N}$, $\boldsymbol X\in \mathbb{R}^{N\times K}$, $\boldsymbol W\in \mathbb{R}^{K\times C}$. Matrix B $\in \mathbb{R}^{N\times C}$ is the intermediate result of $\boldsymbol X\cdot \boldsymbol W$ and $\boldsymbol O$ $\in \mathbb{R}^{M\times C}$ is the final output matrix. We assume we use the execution order of $\boldsymbol A\cdot (\boldsymbol X \cdot \boldsymbol W)$ as it reduces the number of computations for most graph datasets^[9].

Figure  2.  Pseudocode of the chain SpMM in GCNs.

下载: 全尺寸图片 幻灯片

2.2   GCN Accelerators

Recently, a few GCN accelerators have been proposed, delivering substantial gains in performance and energy efficiency compared with generic CPU- and GPU-based solutions. Specifically, HyGCN^[11] exploits two dedicated compute engines, i.e., an aggregation engine and a combination engine, to accelerate the aggregation and combination phases, respectively. AWB-GCN^[9] is an architecture for accelerating GCNs and Sparse-dense Matrix Multiplication (SpMM) kernels, and addresses the issue of workload imbalance in processing real-world graphs. GCNAX^[12] proposes a flexible dataflow for GCNs that simultaneously improves resource utilization and reduces data movement.

These accelerators can be illustrated by the typical architecture shown in Fig.3. It consists of an accelerator chip and off-chip memory (usually DRAM). The accelerator chip is primarily composed of a processing unit (PU), a global buffer (GLB) and a scheduler. The PU can support high compute parallelism to perform the matrix multiplications, consisting of either two separate engines (HyGCN) or one uniform engine (AWB-GCN, GCNAX). The scheduler is used to map the GCNs onto the proposed accelerator using the computation sequences defined by the loop optimization techniques. GLB is usually a uniform software-controlled SRAM scratchpad memory that can be used to exploit input data reuse and hide DRAM access latency, or for the storage of intermediate data. The accelerator provides three levels of the memory hierarchy, including DRAM, GLB and local registers in PEs. Accessing data from a different level implies a different energy cost^[13]. In this paper, we focus on the expensive off-chip DRAM accesses (between off-chip DRAM and GLB) and on-chip SRAM accesses (between GLB and registers in PEs).

Figure  3.  A typical GCN accelerator architecture.

下载: 全尺寸图片 幻灯片

2.3   Loop Optimization and Design Variables

The chain SpMMs can be transformed in numerous ways to capture different reuse patterns to map the computation to a hardware accelerator implementation. In this paper, we will investigate four loop optimization techniques, namely loop unrolling, loop tiling, loop interchange and loop fusion, to optimize the memory access patterns with the three levels of the memory hierarchy.

2.3.1   Loop Unrolling

Loop unrolling determines the parallelization strategy of the GCN loops, which then determines the PE array scale and organization as well as the size of registers in each PE. It can be used to increase the utilization of massive computation resources. Researchers have extensively studied the methods to unroll SpMM for parallel computations. As illustrated in Fig.4 which takes SpMM1 as an example, unrolling different loops directs parallelization of different computations, which affects the optimal PE array architecture with respect to the data reuse opportunities and memory access patterns.

Figure  4.  Loop unrolling. (a) Unroll loop-1. (b) Unroll loop-2. (c) Unroll loop-3.

下载: 全尺寸图片 幻灯片

• Loop-1 Unrolled (Fig.4(a)). In this case, a column vector of $Pn$ pixels from X is multiplied with a pixel from $\boldsymbol W$ in each cycle, and generates a column vector of $P_n$ pixels which will be accumulated to matrix B. If data reuse in local registers is not enabled, it will involve $2\times P_n+1$ SRAM reads and $P_n$ SRAM writes in each cycle.

• Loop-2 Unrolled (Fig.4(b)). In this case, a row vector of $P_c$ pixels from $\boldsymbol W$ is multiplied with a pixel from X in each cycle, and generates a row vector of $P_c$ pixels which will be accumulated to matrix B. If data reuse in local registers is not enabled, it will involve $2\times P_c+1$ SRAM reads and $P_c$ SRAM writes in each cycle.

• Loop-3 Unrolled (Fig.4(c)). In this case, the inner product of a row vector of $P_k$ pixels from X and a column vector of the same size from $\boldsymbol W$ is computed in each cycle, and generates one pixel which will be accumulated to matrix B. If data reuse in local registers is not enabled, it will involve $2\times P_k+1$ SRAM reads and 1 SRAM write in each cycle.

These unrolling factors ($P_n, P_k, P_c$) will determine the total number of parallel multiple-and-accumulation (MAC) operations as well as the number of required multipliers.

2.3.2   Loop Tiling

Loop tiling can be applied for each SpMM to leverage data locality and it determines the required capacity and the partitioning of GLB. As the on-chip GLB capacity is usually not large enough to hold all the data in GCNs, loop tiling can be used to divide the entire data and only fit a small portion of the data into the on-chip GLB. By properly selecting the loop tile sizes, the data reuse can be maximized to reduce off-chip DRAM access, which will significantly improve the overall energy efficiency as the energy cost of off-chip memory accesses is orders of magnitude higher than that of arithmetic operations. The tile sizes set the lower bound of the required GLB capacity. In other words, the GLB should be sized large enough to hold the data tiles.

2.3.3   Loop Interchange

Loop interchange^[17] determines the computation order of the loops and it can be used to enable different types of data reuse to reduce external memory traffic by exchanging the order of the nested loops. There are two types of loop interchange in the GCN loops, namely intra-tiling and inter-tiling loop orders. The intra-tiling loop order determines the pattern of data movements from on-chip GLB to register files. The inter-tiling loop order determines the data movement from external memory to on-chip GLB. Loop interchange along with local memory promotion can reduce the data movements. Specifically, if the innermost loop is irrelevant to a matrix, i.e., the loop iterator does not appear in the access function of the matrix^[18], there will be redundant memory operations between different loop iterations which can be eliminated to reduce memory access operations.

2.3.4   Loop Fusion

Loop fusion optimization^[19] can be leveraged to reduce data transfer of intermediate data. Specifically, we can fuse the processing of SpMM1 and SpMM2 to reduce the data transfer of matrix B between off-chip DRAM and on-chip GLB. As shown in Fig.2, if the two SpMMs are executed sequentially without fusion, the elements of matrix B are stored back to DRAM in SpMM1, and they are again fetched from DRAM to on-chip in SpMM2. Therefore, we can reduce the data transfer of these intermediate data by fusing the execution of SpMM1 and SpMM2. When SpMM1 finishes the computation of loop $k$ and generates a B chunk, we can pause the execution of SpMM1 and proceed to the execution of SpMM2. By doing so, the data transfer of the intermediate matrix (B) is eliminated. Notably, although loop fusion reduces data transfer of intermediate results, it somehow sacrifices the freedom of loop interchange. Specifically, the iteration $k$ in SpMM1 must be the innermost loop to ensure that matrix B finishes all its computations (not a PartialMat) before being forwarded to SpMM2. Moreover, as $m$ becomes the innermost loop in the communication part of SpMM2, matrix O has to be frequently transferred between on-chip and off-chip. Since O is the result matrix, the volume of data transfer is doubled compared with the input matrix such as matrix A because the result matrix has to be written back to the main memory when being replaced, whereas the input matrix can be directly replaced without being written back.

Table 1 lists the parameters in GCNs and the design variables used by the four loop optimization techniques, where variables with a prefix of capital T denotes the tile size, and P for unrolling factors. Since both SpMM1 and SpMM2 contain the loops $n$ and $c$, we hereafter use $n0,c0$ as the loop iterator in SpMM1, and $n1,c1$ as the loop iterator in SpMM2.

Table  1.  GCN Loop Parameters and Design Variables

	GCN Loop	Dimen- sion	Without Loop Fusion			With Loop Fusion
			Loop Tiling	Loop Unrolling		Loop Tiling	Loop Unrolling
SpMM1 (B = XW)	Loop-1	N	Tn0	Pn0		Tn0	Pn0
	Loop-2	C	Tc0	Pc0		Tc0	Pc0
	Loop-3	K	Tk	Pk		Tk	Pk
SpMM2 (O = AB)	Loop-4	M	Tm	Pm		Tm	Pm
	Loop-5	C	Tc1	Pc1		–(equal to Tc0)	Pc1
	Loop-6	N	Tn1	Pn1		–(equal to Tn0)	Pn1

下载: 导出CSV 

| 显示表格

3.   GShuttle: Optimization Framework

Although we have concluded the key factors that determine the memory accesses, it is not easy to decide which combination of design variables is optimal for a given GCN layer. Simply using static design variables by random sampling for all layers as a lot of prior work did^{[9, 11]} is far from optimal due to the dimension and sparsity variance across different layers. Therefore, in this section, we introduce how to determine the design variables for a given graph convolutional layer. We first formulate the selection of design variables as an optimization problem, which aims to find the best combination of design variables that maximizes the design objectives (e.g., the number of off-chip DRAM and on-chip SRAM accesses) under certain design constraints (e.g., the on-chip storage size and the number of PEs). We find that it is an NP-hard problem because of the large design space, thus requiring heuristic solutions in practice. Therefore, we further propose two algorithms, namely Pruned Search Space Sweeping, and Greedy Search to address this problem.

3.1   Problem Formulation

3.1.1   Design Objectives

As our aim is to optimize memory access efficiency, we will primarily target at two design objectives: to minimize the following two metrics.

• Number of Off-Chip DRAM Accesses. It primarily relies on the size of GLB and the degree of data reuse, which are determined by the tiling size, inter-tiling loop order, and loop fusion strategy.

• Number of On-Chip SRAM Accesses. It is determined by the loop unrolling strategies and intra-tiling loop order, since they determine the reuse patterns of the data transfer from GLB to local registers.

To simultaneously achieve both design objectives might be infeasible as the best combination of design variables for off-chip DRAM accesses may not be optimal for on-chip SRAM accesses, and vice versa. Therefore, to optimize the overall memory access efficiency, we combine the two design objectives into one by calculating their weighted total as follows:

where $\mathbb{X}={\cal{X}}^t\cup{\cal{X}}^{oo}\cup{\cal{X}}^f\cup{\cal{X}}^u\cup{\cal{X}}^{oi}$ denotes the entire search space, and ${\cal{X}}^t, {\cal{X}}^{oo}, {\cal{X}}^f, {\cal{X}}^u, {\cal{X}}^{oi}$ denote the parameter spaces of the tile size, inter-tiling loop order, loop fusion strategy, unrolling factors, and intra-tiling loop order, respectively. $V_d$ and $V_s$ denote the number of off-chip DRAM accesses and on-chip SRAM accesses, respectively. $S_{\boldsymbol X},S_{\boldsymbol W}, S_{\boldsymbol B1}, S_{\boldsymbol A}, S_{\boldsymbol O}, S_{\boldsymbol B2}$ denote the required on-chip storage sizes of the corresponding matrices, which are determined by the tile size. $\omega$ is an adjustment parameter that reflects the difference in the energy cost between basic DRAM access and SRAM access. According to [13], we set $\omega=0.007\;8$ indicating a basic DRAM access operation consumes 128x more energy than a basic SRAM access does. To solve this optimization problem, we first need to measure $V_d$ and $V_s$ given a combination of design variables and a GCN layer. To this end, we build analytical models for the estimation of $V_d$ and $V_s$.

3.1.2   Estimation of Off-Chip DRAM Accesses

Since the space of the design variables is polyhedral, we use an example to explain how the analytical models for off-chip DRAM accesses are built. Assuming the inter-tiling loop order is $n_0\rightarrow c_0\rightarrow k, m\rightarrow$ $c_1\rightarrow n_1$ and loop fusion is not enabled, the total number of off-chip DRAM accesses is calculated by:

where

Here $\alpha_{\boldsymbol X},\alpha_{\boldsymbol W},\alpha_{\boldsymbol B},\alpha_{\boldsymbol A}$ and $S_{\boldsymbol X},S_{\boldsymbol W},S_{\boldsymbol B},S_{\boldsymbol A}$ denote the trip counts and buffer sizes of memory accesses to X, W, B, A, respectively. Note that $\alpha_{{\boldsymbol B}1},\alpha_{{\boldsymbol B}2},S_{{\boldsymbol B}1}, S_{{\boldsymbol B}2}$ are used to differentiate the accesses in SpMM1 and SpMM2 respectively. As matrices X and A are sparse^{[9, 12]}, the off-chip DRAM accesses can be reduced by compressed encoding of the matrices. We assume that the zeros in matrices X and A are distributed evenly so we use the overall density of X and A ($\gamma_{\boldsymbol X},\gamma_{\boldsymbol A}$) to represent the density of each chunk when estimating $S_{\boldsymbol X}$ and $S_{\boldsymbol A}$, as shown in (4). Although it does not reflect the actual distribution, we make this assumption for simplicity since considering the sparsity distribution would significantly increase the model complexity. Moreover, we find that the estimated values from the model deviate little from the actual values derived from a cycle-level simulation.

When changing the inter-tiling loop order, we only need to modify the equation of $\alpha's$ in (5). The enumeration of the loop orders and the corresponding equation of $\alpha's$ are omitted for brevity. When enabling loop fusion, the total number of off-chip accesses and the buffer size are also calculated by (3) and (4), but the trip counts are estimated as follows.

We can see that the DRAM accesses of matrix B are eliminated but $\alpha_{\boldsymbol O}$ is much larger than that in (5).

3.1.3   Estimation of On-Chip SRAM Accesses

If data reuse in local registers is not enabled, the total number of read operations from on-chip GLB for SpMM1 will be calculated as follows:

since every multiplication needs three SRAM reads. The total number of write operations from PEs to on-chip buffers for SpMM1 will be calculated as follows:

As mentioned in Subsection 2.3, the number of on-chip SRAM accesses can be reduced by enabling data reuse under different loop unrolling strategies and intra-tiling loop order. For example, given the intra-tiling loop order ($n0\rightarrow c0\rightarrow k$) and loop-3 unrolled for SpMM1, the data elements in matrix B can be reused for $T_k$ times. Therefore, the total number of SRAM reads and writes is:

respectively.

Similarly, we can calculate the SRAM reads and writes give other combinations of design variables.

3.2   Search Algorithms

Given the analytical models, we need to find out which combination of design variables can minimize the design objective described in (2). Clearly, by sweeping all the combinations of design variables, we can find the optimal solution but it takes a lot of time due to the large search space. According to our experiments, it takes tens of hours to fully explore the entire design space on an Intel I7-8650U@1.90GHz, which is infeasible for practical use.

To simplify the search, we use outer-product-based computation architecture^[20] as shown in Fig.4(b) to optimize the SRAM accesses. Although this method would have a negative impact on the reuse of the output matrix, it provides additional input matrix reuse compared with the inner-product-based method. More importantly, it well supports the elimination of zero computations. Since the input pixel from X is the input operand for all the $P_{c0}$ multiplications, these computations can be skipped simultaneously if the input pixel is zero. For DRAM accesses, we tackle the optimization problem by developing two approaches, pruned search space sweeping and greedy search.

3.2.1   Pruned Search Space Sweeping

We discovered that the main reason for the large search space is that ${\cal{X}}^{t}$ (the search space of tiling size) contains every integer value between 1 and the dimension size. Therefore, pruning the search space ${\cal{X}}^{t}$ can significantly shrink the entire search space. Most tile size values cannot be fully divided by the dimension size. In such cases, we need to pad the data block to simplify data movements^[21], which will degrade the GLB space utilization. Clearly, the tile size that causes less padding will utilize the GLB space efficiently, thus reducing unnecessary off-chip DRAM accesses. Among a set of the tile sizes that results in the same number of iterations, the one requires minimum padding has the least data padding. Therefore, from 1 to the dimension size, we only need to consider the smallest tile size values that yield a new number of loop iterations. For example, assuming a value of 10 for dimension $N$, the candidate tile size will be $\{1,2,3,4,5,10\}$ since they yield the number of loop iterations of $\{10,5,4,3,2,1\}$. The number of points to sweep in dimension $N$ will be reduced from $O(N)$ to $O(2\sqrt{N})$, which will significantly shrink the search space, thus reducing the search time from tens of hours to several minutes.

3.2.2   Greedy Search

Alternatively, we also provide a greedy search algorithm that further reduces the search time to several seconds. Table 2 shows how to determine the design variables for off-chip DRAM accesses (${\cal{X}}^t, {\cal{X}}^{oo}, {\cal{X}}^f$). This greedy algorithm leverages the empirical rules concluded from many simulation results.

Table  2.  Greedy Search Algorithm to Determine the Design Variables

Condition	Loop Fusion	Inter-Tiling Loop Order	Tile Size Setting Priority
$N\times C\geqslant$ GLBsize	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	①$T_{n0},\; T_{m}$ ②$T_{c0},\; T_{c1}$ ③$T_{n1},\;T_k$
$N\times C <$ GLBsize	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	①$T_{n0},\;T_{n1}$ ②$T_{c0},\;T_{c1}$ ③$T_{m},\;T_k$

下载: 导出CSV 

| 显示表格

The tile size setting priority indicates which tiling factor has the priority for larger number settings. For example, if $N\times C\geqslant GLBsize$, $T_{n0}$ and $T_m$ have the highest priority for larger number settings, which means they will be set to the maximal number while satisfying other constraints. $T_{c0},T_{c1}$ have the second highest priority. When $T_{n0}$ and $T_m$ are already set as the largest number, then $T_{c0},T_{c1}$ will be set as large as possible.

To better understand the greedy search, Table 3 presents the tile size, loop order and loop fusion choices for five datasets: Cora^[22], CiteSeer^[22], PubMed^[15], Nell^[23] and Reddit^[15]. We constrain GLBsize at 128 KB.

Table  3.  Design Variables (Tile Size, Inter-Tiling Loop Order and Loop Fusion) Derived from Greedy Search

Dataset	Layer	(M-N-K-C)	$\gamma_{\boldsymbol A}$	$\gamma_{\boldsymbol X}$	Loop Fusion	Inter-Tiling Loop Order	Tile Size Tuple ($T_{n0}, T_{c0}, T_{k}, T_{n1}, T_{c1}, T_{m}$)
Cora	L1	(2708-2708-1433-16)	0.001800	0.01270	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	(2708, 16, 1, 2708, 16, 1)
	L2	(2708-2708-16-7)	0.001800	0.78000	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	(2708, 7, 1, 2708, 7, 1)
Citeseer	L1	(3327-3327-3703-16)	0.001100	0.00850	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	(3000, 16, 5, 3000, 16, 1)
	L2	(3327-3327-16-6)	0.001100	0.00850	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	(3000, 6, 1, 3000, 6, 1)
Pubmed	L1	(19717-19717-500-16)	0.000280	0.10000	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(3073, 16, 1, 1, 16, 3073)
	L2	(19717-19717-16-3)	0.000280	0.77600	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(3000, 3, 1, 1025, 3, 3000)
Nell	L1	(65755-65755-61278-64)	0.000073	0.00011	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(4096, 1, 33, 1, 1, 4096)
	L2	(65755-65755-64-186)	0.000073	0.86400	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(257, 186, 1, 1, 17, 2817)
Reddit	L1	(232965-232965-602-64)	0.002100	0.51600	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(641, 64, 1, 1, 9, 4096)
	L2	(232965-232965-64-41)	0.002100	0.60000	No	$n_0\rightarrow c_0\rightarrow k$, $m\rightarrow c_1\rightarrow n_1$	(1153, 41, 1, 1, 17, 2817)

下载: 导出CSV 

| 显示表格

4.   Evaluation

4.1   Experimental Setup

Accelerator Implementation. To evaluate GShuttle, we built a cycle-level simulator in C++ to model the behavior of the hardware described in Section 2 when using the design variables derived from GShuttle. The simulator models the microarchitectural behaviors of each module, and supports different combinations of design variables. The simulator counts the exact amount of DRAM reads and writes, on-chip SRAM reads and writes and the number of execution cycles, which is used for estimation of performance and energy efficiency.

Design Constraints. We constrain the number of PEs no more than 128, and the on-chip GLB is no more than 128 KB. The off-chip DRAM bandwidth is 128 GB/s.

Baselines. We compare GShuttle with three GCN accelerators (HyGCN^[11], AWB-GCN^[9] and GCNAX^[12]). GShuttle has two variants, one is GShuttle-PSSS which uses pruned search space sweeping to find the combination of design variables, and the other is GShuttle-GS which uses greedy search. Table 4 summarizes the characteristics of the baselines and GShuttle. The baseline accelerators are scaled to be equipped with the same number of multipliers and DRAM bandwidth as GShuttle. Since HyGCN and AWB-GCN use single-precision floating-point numbers (32-bit) whereas GCNAX uses double-precision (64-bit), we uniformly use double-precision numbers for all accelerators to provide a fair comparison. We also resize the baseline accelerators to be equipped with the on-chip storage capacity. For example, we simulate the HyGCN accelerator with 128 KB on-chip storage rather than the original 16 MB. The DRAM bandwidth for all the accelerators is scaled to 128 GB/s. Note that as HyGCN uses an edge-centric programming model for the aggregation phase, their computation in the aggregation phase is not matrix multiplication. Our simulator takes this into account and estimates the execution cycles and DRAM accesses according to HyGCN's dataflow.

Table  4.  Characteristics of Baselines

Baseline	Execution Order	Loop Fusion	Inter-Tiling Loop Order	Tile Size
HyGCN[11]	$(\boldsymbol A\boldsymbol X)\boldsymbol W$	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	Static
AWB-GCN[9]	$\boldsymbol A(\boldsymbol X\boldsymbol W)$	Yes	$n_0\rightarrow c_0\rightarrow k\rightarrow m$	Static
GCNAX[12]	$\boldsymbol A(\boldsymbol X\boldsymbol W)$	Adaptive	Adaptive	Static
GShuttle	$\boldsymbol A(\boldsymbol X\boldsymbol W)$	Adaptive	Adaptive	Adaptive

下载: 导出CSV 

| 显示表格

Benchmarks. We use the graph datasets listed in Table 3 as the benchmarks to test the efficiency of GShuttle and the baselines. These datasets vary in the number of edges, vertices and sparsity levels, which provides sufficient diversity to evaluate the effectiveness of these methods.

4.2   Experimental Results

4.2.1   Number of DRAM Accesses

We firstly make the comparison on the total number of DRAM accesses, as shown in Fig.5. GShuttle provides a tremendous DRAM access advantage over the baselines. Specifically, GShuttle-GS reduces DRAM accesses by a factor of 11.1x, 3.3x and 1.4x compared with HyGCN, AWB-GCN and GCNAX, respectively. Moreover, GShuttle-PSSS reduces DRAM accesses by a factor of 11.7x, 3.4x and 1.5x over the three baselines. The high DRAM access efficiency of GShuttle mainly stems from the followings. 1) GShuttle uses adaptive loop order and fusion strategy for different graph datasets. 2) The adaptive tiling sizes of GShuttle can make the best use of the global buffer. Since HyGCN uses inefficient execution order, it involves more computations that result in more DRAM accesses. AWB-GCN optimizes the reuse of the intermediate matrix. However, it sacrifices the reuse of the output matrix due to the limited on-chip storage size. Moreover, the tile sizes are not carefully tailored in the AWB-GCN accelerator.

Figure  5.  DRAM accesses of GShuttle and the baseline approaches. (a) Cora. (b) Citeseer. (c) Pubmed. (d) Nell. (e) Reddit.

下载: 全尺寸图片 幻灯片

4.2.2   Energy Consumption

For energy evaluation, we primarily focus on three parts: 1) energy consumed by arithmetic operations, 2) energy consumed by on-chip SRAM accesses, and 3) energy consumed by off-chip DRAM accesses. As the simulator counts the number of arithmetic operations and data accesses at different levels, we use these numbers to estimate the total energy consumption by multiplying them with the energy cost of basic arithmetic and memory operations in a 45 nm CMOS process^[13]. Fig.6 shows the normalized energy consumption of these accelerator designs. Overall, GShuttle-GS achieves 9.5x, 3.1x, and 1.4x energy savings on average over HyGCN, AWB-GCN, and GCNAX, respectively, while GShuttle-PSSS saves energy by a factor of 12.1x, 3.9x, and 1.7x compared with the three baseline accelerators respectively.

Figure  6.  Energy savings of GShuttle over the baselines.

下载: 全尺寸图片 幻灯片

4.2.3   Sensitivity to Hardware Parameters

The optimization framework in Section 3 indicates that GLBsize is an important specification for the number of off-chip DRAM accesses. Moreover, as we scale the baseline accelerators to be equipped with the same global buffer size, which would potentially hurt the efficiency of the baseline accelerators, we conduct a sensitivity analysis on the Reddit dataset to quantify the effects of global buffer size. In Fig.7, we sweep the on-chip buffer size from 128 KB up to 8 MB to investigate how it influences the number of DRAM accesses. The $y$ axis denotes the total number of DRAM accesses of the two layers. All schemes achieve DRAM access reduction with larger GLB provisioning, especially when GLBsize is small ($GLBsize<1$ MB). With GLBsize going larger, the benefit gains slower. For specific schemes, GShuttle-GS and GShuttle-PSSS outperform the baselines in all GLB settings.

Figure  7.  Number of DRAM accesses w.r.t. the variation on-chip buffer size (tested on the Reddit dataset).

下载: 全尺寸图片 幻灯片

5.   Related Work

Besides the GCN accelerators mentioned in Section 2, there are also a few other GNN (graph neural network) accelerators in the literature. Auten et al.^[24] proposed a GNN accelerator to efficiently execute the irregular data movement required for graph computation in GNNs, while also providing a high compute throughput required by GNN models. EnGN^[25] is designed to accelerate the three key stages of GNN propagation, which is abstracted as common computing patterns shared by typical GNNs. GRIP^[26] is designed for low-latency inference of GNNs, which splits GNN inference into a fixed set of edge- and vertex-centric execution phases that can be implemented in hardware, and then specializes each unit for the unique computational structure found in each phase. GraphACT^[27] is dedicated for the acceleration of training GCNs on CPU-FPGA heterogeneous systems, which incorporates multiple algorithm-architecture co-optimizations. VersaGNN^[28] is systolic-array-based versatile GNN accelerator that unifies dense and sparse matrix multiplication in GNNs.

Since the loop optimization techniques proposed in this paper can significantly improve memory access efficiency, which is of paramount importance for GCN acceleration, we believe that our approach can be easily applied to the other accelerators.

6.   Conclusions

Motivated by the observation that most of the energy is consumed by memory accesses for state-of-the-art GCN accelerators, this paper presented GShuttle to optimize memory access efficiency for such accelerators. GShuttle employs two algorithms to solve the memory access optimization problem raised in GCN accelerators, both of which can find the optimal design variables of GCN dataflow under certain design constraints. Our results showed that GShuttle could significantly reduce the number of DRAM and SRAM accesses for GCN accelerators. Since the optimizations on DRAM accesses are orthogonal to those on computation, we expect that GShuttle can be applied to many existing GCN accelerators such as HyGCN and AWB-GCN.