[GNN]Understanding and Bridging
论文题目：Understanding and Bridging the Gaps in Current GNN Performance Optimizations
文章时间：
会议/期刊：PPoPP 2021-02-17
作者背景：清华大学，阿里巴巴
笔记时间：2021年09月14日周二
论文地址：ppopp
作者视频：chinasys21
作者对图神经网络的系统特性进行了分析，发现了五个性能瓶颈，对此针对性的进行了改进。
性能瓶颈：
- 图算子操作较差的locality
- 不同节点有不同数量的边，会造成严重的负载不均衡 30%的空闲，数据集的差异也有非常大的影响
- 图操作和神经操作是交互进行的，热点的操作会造成不均衡
- 图结构中一些算子的重复冗余
- 不同的特征大小也会对性能造成很大的影响
解决方案
1，任务调度，调整图结构
调整图结构
细粒度分配任务
2，阶段间细粒度数据共享
数据可见范围
3，稀疏访问和冗余消除
绕过冗余
4，自动调参
最后做了一个综合的调参
这些工作目前是手动的工作，未来会做编译器层面的自动优化
目前工作聚焦于静态图，对动态图的支持非常有限。
更新
Abstract
GNN 最近很火，他在图上的学习很快。
优化他的性能很重要，但是我们目前对他只有粗浅的认识。
本文，我们对当前比较流行的GNN框架进行深度的检验，提出五个性能提升问题。尤其是针对GNN处理传统图/DNN时的复杂性问题。
基于我们的发现，我们提出一系列的优化方案。
优化方案使用了最新的GPU优化技术，并且针对GNN量身定做。
实验结果证明可以达到不错的性能提升。
第一章
intro
第一段：GNN最近在很多方面表现好
第二段：GNN的性能问题。越深越大的模型效果越好，但是计算效率限制了模型的发展。人们从算法角度做了一些改进
第三段：GNN包含两部分，图计算和神经网络计算，单纯把二者放在一起是不靠谱的。GNN中两者是相互交错的。二者的计算模式有很大区别，图计算是计算稀疏的，而神经网络是计算密集的。GNN框架中会有复杂的算子融合调度的问题。
第四段：上诉问题导致人们开始开发针对GNN的编程框架。出现了数十种框架，但是我们的实验发现他们在v100上用了不到10%的计算和不到50%带宽。
第五段：本文提出了五大问题。
第六段：我们针对问题提出了解决方案。
第七段：实验结果
第八段：贡献总结
第二章 GNN优化的复杂性
2.1 GNN的流程
2.2 优化的复杂性
常规问题：
1.图计算带来的随机性，2.内存开销大，神经网络的计算量大
图节点变化多端，对负载均衡和内存优化影响很大。
大规模的内存footprint 和计算开销，随着图规模的增长而指数增长
特殊问题：
GNN中图计算和神经网络的复杂依赖关系以及复杂的交互
GNN无法使用DNN中的优化算法，如最常见的算子融合技术。
因为graph operations in GNN have irregular thread mapping patterns, unpredictable memory accesses, and complex dependencies between operations, a clear contrast to regular element-wise and dense operations in DNNs
2.神经网络计算以图的模式运行
比如GNN中有很多center-neighbor的模式，和传统的DNN很不同。
特征向量的长度一直变化
第三章 现有GNN框架中的问题
3.1 方法论
我们选了四个框架，三个GNN模型，8个不同的图数据集。
硬件设备V100
cuda10.1
pytorch 1.5.1
3.2 观察到的性能瓶颈
见上文。
第四章 优化瓶颈
利用已有的GPU优化技术，针对性的优化data locality, load balance, and kernel fusions
4.1 图操作的任务分配器
locality-aware task scheduling and neighbor grouping
原则：将相似的任务放在一起
相似度度量衡：Jaccard
