Parallel Graph BFS

Scalable Graph Exploration on Multicore Processors （SC2010(高性能网络、存储和分析）， IBM TJ Watson）

  • 通过并行/并发设计能够极大地提升traverse的性能
  • 本文设计了graph上的多核并行算法
  • 算法一通过直接的锁机制实现并发，行8和行10-12分别需要原子操作的原则来防止冲突
  • 算法二有两个优化，第一个是bitmap控制节点visited，第二个是减少并发控制的原子操作（行13-18）
Algorithm 1
Algorithm 2
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。