跳转至

图知识库

知识框架

图的存储

CSR和PWA

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

CSR和PWA存储结构

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函数实现,触发缺页异常并且进行调页;并且采用cudaMemAdvisecudaMemPrefetchAsync进行优化。