GCN文章总结
有没有可能出现新的数据压缩方式适配GCN的处理模式
[TOC]
UWB-GCN: Hardware Acceleration of Graph-Convolution-Network through Runtime Workload Rebalancing
最早的一篇文章，提出了GCN推理加速的一个最早的设计。主要关注点在数据稀疏以及load balance。
首先是baseline 设计：这个设计也是最早的GCN加速器，然后在baseline的基础上进行workload rebalancing.成为最终设计。
首先在计算模式上，先计算AXW的时候分为两种方式，(AX)W或者A(XW),由于不同的稀疏度，A十分稀疏，X一般稀疏，W比较密集，这里选用A(XW)的计算模式，这样两步计算中都会是SPMM(Sparse Dense Matrix Multiplication), 计算workload会比较小。
SPMM具体的计算方式：由$A\times B = C$变换得到：
$C=\left[\sum_{j=0}^{n-1} A_{j} b_{(j, 0)}, \sum_{j=0}^{n-1} A_{j} b_{(j, 1)}, \ldots, \sum_{j=0}^{n-1} A_{j} b_{(j, k-1)}\right]$
具象表示：()
workload的分配，在假设数据按照行均匀分布的前提下，每两行的数据(3个非0数据)分配到一个PE。
并行化处理的一个划分:
同时他这个一次处理一列带来的效果是：
- 很好地提高并行度，可以流水线操作，一次一列交替执行。
- 减少片上存储，不需要同时存储整个图，而只需要其中的一列。
主要的架构设计如下：
主要包含以下几个部分：
sparse-matrix-memory (SP-MMeM)
SPMMeM buffers the input sparse matrix A
dense-column-memory (DCM)
DCM buffers the input dense matrix B .
task-distributor & Queue (TDQ)
PE-array
accumulation-buffers-array (ACC).
ACC buffers the partial results of the resulting matrix C for accumulation.
其中根据稀疏程度TDQ分为两类，在通常稀疏的时候(50%左右)，为TDQ1，上图左边。在十分稀疏的时候（90%以上）为TDQ2。
TDQ2采用多级Omega路由网络，同时考虑到MAC可能需要多个周期进行计算，可能会产生RaW冒险，因此两者都配备RaW检查其和Stall Buffer，其处理思路类似于处理器中的scoreboard。
主要的处理顺序是：
- 首先计算$X\times W$的时候，是一个一般稀疏矩阵跟密集矩阵相乘，使用TDQ1。
- $X\times W$计算的结果中，每计算好一列就可以送到下一个计算序列中，也就是$A\times (X \times W)$这个时候A是极度稀疏矩阵，采用TDQ2进行分发。
由于以上处理方式是建立在load balance的基础上，现在作者主要解决的问题是load imbalance。其中有两种主要的imbalance方式,如下图所示：
- Local imbalance 主要是相邻的两行之间会有跳跃，也就是波动。
- Remote imbalance 或者可以说波动的特别大，集中在某些特殊行
两者的稀疏统计直方图可以显示如下：
为此作者进一步改善，提出两种方式解决这个不平衡问题：
Dynamic Local Sharing
因为这个解决的思路就是将一个比较多的区域平均分到邻域，这也是无法处理Remote Imbalance的原因，
Dynamic Remote Switching
Remote Imbalance的这个因素需要提前调整一下，加上一个switch操作也就是将特别密集的图调整到其他空白的区域，由此形成local imbalance，进而可以使用上一种方式进一步调整。
过程如下：
HyGCN: A GCN Accelerator with Hybrid Architecture
主要点是在GCN的推理阶段，分成两个阶段专门进行优化，一个是Aggregation，另一个是Combine，这两个阶段可以以流水线方式执行。
首先是在Aggregation，一个节点的邻节点(相隔k个元素，k一般为1,2.)会将他自己的feature聚集给这个节点，这一部分的数据往往是依赖于图的结构，非常irregular和dynamic。而在Combine阶段，则主要执行MLP(Multi-Layer Multiplication )操作,也就是CNN中的全连接操作。主要进行矩阵向量相乘。这部分数据模式是static和regular的，与Aggregation完全相反。
从并行度角度出发：
- feature vector 长度更长且多变，可以实现更好的intra-vertex parallalism.
- GCN中参数可以共享，进而可以在Combination阶段实现inter-vertex parallelism.
整体架构：
分为四大块：
- Aggregation Engine
- Combination Engine
- Coordinator
- Memory Access Handler
Aggregation Engine
interval shade graph partitioning
通过数据复用来减少数据的不规律性。
window sliding-shrinking methods
利用稀疏特性来减少数据访存。
这一部分主要是因为Aggregation阶段数据极度不规律已经动态变化，在DRAM中的读取比较杂乱，数据读取耗能大。
使用了gather-based methods
相比scatter-based methods，这一方法主要是在同步耗能更少。然后结合Edge-Centric PM来增加并行度处理。
vertex-disperse processing mode
相比vertex-concentrated，一个顶点的工作负载都分配给单独的SIMD core。这样的方式延迟大同时负载不均衡，效率低以及浪费了并行度。因此选用vertex disperse。
图划分和稀疏减少
这一部分主要是包括图a的划分，然后进行滑窗操作（顶行对应有数据的地方）然后进行window shrinking(底行回缩到有数据的地方)
Combine Engine
- Multi granular systolic array
- 复用参数
这一部分数据比较规律，主要问题是不同线程之间数据复用和同步耗时长。
- 然后使用MVM-Centric PM 来并行处理MVM计算。
提出了两种模式：
Independent Working Mode
图a这种方式对应了低延时，
Cooperative Working Mode
图b这种方式对应了低能耗
Coordinator
这一设计主要在优化从DRAM中的读取，最开始是混乱的读取，数据地址不规律，不利用cache等发挥作用。
将顺序更改为：
edges > input features > weights > output features
不过这个不跨越batch，也就是后面的batch里高优先级数据不比当前batch里低优先级的数据提前。
GraphACT: Accelerating GCN Training on CPU-FPGA Heterogeneous Platforms
这文章的专注点不同于上两篇文章，这个是在进行训练加速，以上两者是在推理阶段的加速。
核心思想是：
算法
算法选择上是在选择合适的算法，其能够得到合适的minibatch, 资源上能够适配BRAM，作者总结了三类算法：
Minibatch by sampling GCN layers
最后一层抽取b个nodes，前一层抽取a·b个nodes，第一层抽取 $a^L \times b$个nodes
Minibatch by sampling training graph
直接从图中抽样，抽样的图更小
Remark on notation
最后通过比较computation to communication ratio得到一个合适的训练算法：
H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna. 2019. Accurate, Efficient and Scalable Graph Embedding. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 462–471. https://doi.org/10.1109/IPDPS.2019.00056
消除冗余(有点类似VLSI课程里算法强度缩减)
消除冗余核心思想是提前计算后面复用较高的单元，根据图的特性有一些具体的算法，这里没有细看。
并行化加速
架构设计：
- CPU performs graph sampling, and then converts Gs to Gs，softmax loss ; FPGA performs the forward and backward pass.
- 通过合适的参数配置，一些图数据在读取到BRAM之后就能够供FPGA一直使用从第一层计算到最后一层。
- 分为两大块，Feature Aggregation Module & Weight Transformation Module
CPU和FPGA之间的调度：
