Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

问题

  • 且cpu部分的存储貌似只是内存,没有考虑外存那些
  • 在UVM settings下讨论(CUDA支持)

本文作为对比对象的:

大图放多GPU或GPU和CPU

GPU BFS

external BFS:已计划

一些定义

UVM

CSR和BFS

分析

factors that impact performance(DATA ACCESS PATTERN):

  • Dependence on the Source Node
  • Dependence on Graph Ordering
  • Dependence on Directedness

问题形式化(貌似没有用)

理想的order:

1 HARMONIC LOCALITY ORDERING

希望的

从随机的顶点出发BFS,所以希望

这个在无向图中可以

计算

算法

“精确”

代替上面的c(x)

计算中心性

给order

不是严格按照中心性降序作为order的原因以及设计:

近似

把上式展开,相同d的项放在一起,得到的和式,第一项对应和x距离为1的所有点,第二项对应和x距离为2的所有点…

评论