图知识库

知识框架

图的存储

CSR和PWA

PMA将整个边数组分成一系列叶段，并保留一棵隐式树以快速定位边更新的位置。

CSC

AL

临界列表

EL

边列表

图处理场景

滑动窗口图流模型

$(u,v)_t$，一条$(u->v)$的边在$t$到达，滑动窗口在不断向前滑动，新的边被加入，旧的边被作废

手动删边和增边

用户手动增删

图的异步和同步处理

基于顶点为中心的图大多为同步处理，即循环迭代，计算效率不高

异步处理绕过同步障碍并利用最新状态直观地导致更有效的迭代；异步迭代可能需要更多的通信并执行无用的计算。可否采用局部并行的思想？

GPU图处理

Subway论文

由于GPU内存不足，可以采用两种优化策略，主要包括基于分区的方法和基于统一内存寻址的方法。

Subway是一种子图生成技术，其主要内容为：

1、根据活跃点集动态生成subcsr

2、分区异步，思想类似于Layph

TODO：研究一下Layph关于PageRank的正确性研究

知识点

基于分区的方法

将图进行分区并且每个分区需要时调入GPU内存并且可以和图计算处理进行并行处理

基于统一编址的方法

CPU 和 GPU 都可以通过一致的内存映像观察单个地址空间。这允许 GPU 程序访问 CPU 内存中的数据，而无需显式内存复制,并且按需进行内存迁移。

采用cudaMallocManaged函数实现，触发缺页异常并且进行调页；并且采用cudaMemAdvise和cudaMemPrefetchAsync进行优化。