问题
code
related work
CPU-多BFS实例
- MSBFS VLDB[26] Manuel Then, Moritz Kaufmann, Fernando Chirigati,
Tuan-Anh Hoang-Vu, Kien Pham, Alfons Kemper,
Thomas Neumann, and Huy T Vo. The more the
merrier: Efficient multi-source graph traversal.
Proceedings of the VLDB Endowment, 8(4), 2014.- CCF-B [27] Ahmet Erdem Sarıyuce, Erik Saule, Kamer Kaya, and ¨
Umit V ¸Cataly ¨ urek. Regularizing graph centrality ¨
computations. Journal of Parallel and Distributed
Computing, 2014.- CCF-B IPDPS [28] Ahmet Erdem Sariyuce, Erik Saule, Kamer Kaya, and
Umit V Catalyurek. Hardware/software vectorization
for closeness centrality on multi-/many-core
architectures. In International Parallel & Distributed
Processing Symposium Workshops (IPDPSW), pages
1386–1395. IEEE, 2014.
GPU-多BFS实例
- 见上面[27]
- SC [35]Adam McLaughlin and David A Bader. Scalable and
high performance betweenness centrality on the gpu.
In International Conference for High Performance
Computing, Networking, Storage and Analysis (SC),
pages 572–583. IEEE, 2014
一些字母含义和取值
idea
example中状态数组SA的图示说明
典型的BFS
observation on shared frontiers
1 JOINT TRAVERSAL 和MSBFS类似+GPU设计
data structure
generate JFQ
implementation of JFQ
example
2 GROUPBY 这个好（将BFS分组以最大化组内BFS的frontiers share）
原理
结论
结论的详细得出过程
speedup指相对于串行、分离地执行这个group中的BFS而言的加速比（串行时间/此方案时间）
idea
规则
对于两个BFS实例而言
q的选择：
规则应用方法
N be default = 128
效果：
规则的直观解释：
3 GPU-BASED BITWISE OPERATIONS 和MSBFS类似+GPU设计
idea
数据结构
实现：
expansion
inspection
Early Termination：This newly freed-up thread will then be scheduled to work on other frontiers.
frontier generation
