Hypergraph | Info Church X.

Workload

A	B	C	workload(FLOP)
			VC’C(C’=prev)
previous C	E*V		EVC
previous C	diag(E)		E*C
previous C	H V*E		VEC
previous C	diag(V)		V*C
ㅤ	ㅤ	sum

第二项（可以优化）/第一项（不能优化）=2E/C’

根据文献，输入层，隐藏层，输出层

该网络一共两层，计算量分别为

第一层：

一般而言，E/V=4~5，从而第二项（可以优化）/第一项（不能优化）~~80

第二层：

第二项（可以优化）/第一项（不能优化）~~160

💡

baseline的选择：对gpgpu而言完全可以算完整个，作为V*V矩阵存储

是否可以与graph accelerator作比较？

Density

重排前：

ㅤ	uf50-218	uf250-1065
4*4	0.3909	0.0921
8*8	0.8623	0.3222
16*16	0.9627	0.7861

用模拟退火重排边的顺序（未重排节点）后：

ㅤ	uf50-218	uf250-1065
4*4	0.2753	0.0798
8*8	0.5902	0.2519

💡

如果只重排边的顺序，是纯收益，几乎没有tradeoff

uf50-218稀疏度较差。但这里矩阵维度只有100*218，似乎也不是很有优化的必要。对更大规模的稀疏矩阵，稀疏度的优化空间还是很大的

可以考虑在交换次序时采用一些启发式的策略

用贪心重排边的顺序（未重排节点）后：

ㅤ	uf50-218	uf250-1065
4*4	ㅤ	2328/0.0698
8*8	ㅤ	ㅤ

Partition

ReRAM阵列通常比较大，至少128*128，因为需要平衡外部电路如DAC/ADC带来的overhead

然而，并非每次都激活全部的行和列进行运算，每次只会激活一部分行列（比如4*4,8*8）。显然，激活的行列数越多，throughput越大。最好的情况下，激活的规模与block大小一致，比如，将矩阵切分成4*4的block，每次激活也是4*4。但为了设计的统配性，最好支持激活行列数与block大小不匹配的情况

目前做法：采用S形依次摆放block（详见Mapping的第一步），只需要取非零的block对应的输入向量做矩阵乘法并累加即可

Mapping

第一步：从稀疏的矩阵H到密集的矩阵dense_H

经过mapping，最后得到的数据如下：

dense_H 一个二维数组，下标就是以block为单位的二维坐标(row, col)

concise_mapping_row 一共N_row_block个列表，每个列表中存储一行的对应信息。具体而言，每个元素是一个元组，代表一个pair。pair中元素为[ptr, row, col]或者None（代表未能构成pair）。ptr是对应原来稀疏矩阵的col坐标，row和col代表对应dense_H的横纵坐标

concise_mapping_col 一共N_col_block个列表，每个列表中存储一列的对应信息。具体而言，每个元素是一个元组，代表一个pair。pair中元素为[ptr, row, col]或者None（代表未能构成pair）。ptr是对应原来稀疏矩阵的row坐标，row和col代表对应dense_H的横纵坐标

第二步：从密集的矩阵dense_H到memory的地址

💡

通过一种介于行优先和列优先中间的表示方法，无需把H和H^T分别存储。同时无论在列方向（对应H）还是行方向（对应H^T），都可以成对处理数据，提升了一倍的并行度

相比block CSR/CSC的优势？后者会浪费多少空间？是否会把不同行的block放到同一行？

⚠️

在行方向上的pair坐标比较规整，只有(0,1)(2,3)等，不会出现(1,2)，因此等价于支持8BL激活，只需要把原本的4个MUX32变成8个MUX16即可，很容易实现；

但在列方向上的pair坐标可能为任意相邻两个整数，比如(0,1)(1,2)(2,3)，这要求PIM可以支持激活任意“相邻”的两个block，而不仅仅是按8个WL一组切分的“大block”

References

“ReGraphX: Noc-enabled 3D heterogeneous ReRAM architecture for training graph neural networks,” in Proc. Design, Autom. Test Europe Conf.(DATE)

“Crossbar based processing in memory accelerator architecture for graph convolutional networks,” in Proc. IEEE/ACM Int. Conf. Comput. Aided Design (ICCAD)

“PIMGCN: A ReRAM-based PIM design for graph convolutional network acceleration,” in Proc. 58th ACM/IEEE Design Autom. Conf. (DAC)

“CoDG-ReRAM: An algorithm-hardware co-design to accelerate semi-structured GNNs on ReRAM,” in Proc. IEEE 40th Int. Conf. Comput. Design (ICCD)

“Accelerating large-scale graph neural network training on crossbar diet,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst.,(TCAD)

“Performance and accuracy tradeoffs for training graph neural networks on ReRAM-based architectures,” IEEE Trans. Very Large Scale Integr. (TVLSI)

“DaRe: DropLayer-aware manycore ReRAM architecture for training graph neural networks,” in Proc. IEEE/ACM Int. Conf. Comput. Aided Design (ICCAD)

“TaRe: Task-adaptive insitu ReRAM computing for graph learning,” in Proc. 58th ACM/IEEE Design Autom. Conf. (DAC)

“HyGCN: A GCN accelerator with hybrid architecture,” IEEE Int. Symp. High Perform. Comput. Archit

“Characterizing and understanding GCNs on GPU,” IEEE Comput. Archit. Lett

有价值的

特别大的图：W. Hu et al., “Open graph benchmark: Datasets for machine learning on graphs,”

不太相关的

EnGN: A High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks

灌水的

A Task-Adaptive In-Situ ReRAM Computing for Graph Convolutional Networks(TCAD)

GraphA: An efficient ReRAM-based architecture to accelerate large scale graph processing

TODO

在交换边顺序时用一些启发式策略

设计PE（block*vec）使其支持转置

看论文：I-GCN的压缩策略，A compute-in-memory chip based on resistive random-access memory中的转置实现

把H和H^T当成两个不相关的矩阵存两遍

TODO(not now)

如果H无法全部存在片上？

💡

除了利用稀疏度外，存算本身的收益？片外buffer相比片上时延50-100倍

SRAM存算的开销？存储密度小，面积大，一整片的SRAM也只能做到800Mb

不要一上来就找联合最优，只能先定下来一部分然后慢慢迭代，不然永远做不了决定