1. 前言

  • BFS是大多数图算法最基本的算法， 例如，该遍历模式可用于进行最短路径计算、模式匹配、邻域枚举和中心性计算，都是基于BFS的，BFS自然就产生了很多变体，区别变体的重要方面就是算法的并行度和源数量：

    • 源数量自然就分为单源和多源
    • 并行度一般分为单线程、多线程和分布式
    • 许多流行的系统(etc.Spark)都注重于分布式，而忽略了单机性能优化

  • 但是图的分布式计算是非常困难的，受限于成本很高的通信，这也取决于图的复杂度，但是我们认为（分布式）必要性不高，在现实中大多数的图（数据量）大小都能放得下在企业级服务器中，所以本文只考虑单机模式，但是多线程也会考虑。

  • 单源BFS适用性很高，但是优化空间很低

  • 多源BFS优化空间高，它同时从多个源点开始遍历，并且线程之间还进行数据共享，很适合解决APSP（全最短路径）问题。对于这个问题，单源BFS需要对每个顶点进行一次BFS，而多源BFS则在可能的情况下进行并发批量BFS【small-world network ？】

  • 目前多源BFS的瓶颈在其对大图的分析能力比较有限

    • 基于GPU的iBFS算法在内存上比其他算法少了一个数量级【。。。？】
    • 基于CPU的MS-BFS是顺序执行的，要想使用所有内核，就需要给每个内核分配一个bfs的实例，且源点要非常大量的情况下才能更快的分析，且由于BFS实例是单独的，所以需要更大量的内存

  • 本文提出两种算法就是为modern massively-parallel multi-socket machines【what？】而打造的优化算法—— SMS-PBFS &MS-PBFS

    • SMS-PBFS是并行单源BFS
    • MS-PBFS是并行多源BFS
    • 这两种算法都是基于顺序的MS-BFS引入的方法，通过可拓展并行化，使得效率极大提升，特别是处理有限源的情况下，同时显著降低了内存需求

  • 本算法可以在不做修改的情况下，适用于顺序BFS

  • 本文主要贡献如下：

    • 我们提出了MS-PBFS算法，这是一种多核NUMA感知的多源BFS，即使在有限数量的源上也能确保全机使用。我们还介绍了SMS-PBFS，一种基于MS-PBFS的支持多核NUMA的单源BFS，其性能优于现有的单源BFS算法。【NUMA？？】

    • 我们引入了一种新的顶点标记方案，它缓存友好且避免倾斜。

    • 我们提出了一个并行的低开销Work-Stealing调度方案，该方案在BFS工作负载中保持NUMA局部性。
      ps:Work-Stealing算法的理念在于让空闲的线程从忙碌的线程的双端队列中偷取任务
      后两个贡献同样可以作用于现有的BFS算法和其他图算法

2. 背景（其他算法并行、单、多源的情况的分析）

  • 本节基于无向无权图，且符合small-world network模型，也就是说是个强连通图，且每个顶点的邻居数符合幂律分布，现实中大多数图都是这样的

  • BFS算法就是从给定源点开始，从1-hop开始一层层地遍历，需要两个数据结构：

    • 用于记录点是否被访问过的map映射
    • 用于存当前迭代发现的新点，然后下一次迭代来读取的队列，这个队列称之为边界（frontier）
    • ps:就是acm里面常用的queue和book
  • BFS的执行（迭代）次数决定于最远的点到源点的距离，它约束与图的直径（图直径就是图中任意两点的最长的最短距离）

2.1 顺序和并行的单源BFS

  • 传统的BFS通过自上而下（top-down）的方式遍历，导致边界（queue）当中存在很多已经遍历过的点，然后又要多次check，导致效率低下，所以Beamer（算法提出者）建议采用自底向上（bottom-up）的方法来遍历，未遍历的点，然后尝试找到其邻居里面已经遍历的点，即使BFS结果未改变，此方法也显著减少了必须check的邻居数量，从而提升性能。

  • 这个方法导致传统BFS的数据结构不能使用，传统BFS数据结构通常使用dense biteset或sparse vector，然而自底向上的遍历需要高效地使用queue查找，而不能高效地利用稀疏变量查找

    biteset：

用二进制位来存储十进制数字，比如arr=[3,5,6,9]四个数字要占4*4字节也就是128位，换成bitset存储变成：

(0,0,0,1,0,1,1,0,0,1)2，也就是biteset[arr[i]]=1，其余为0，这样一个int从4字节变成1位

可以发现，biteset长度取决于最大数，可能会很稀疏，所以dense bitset就是紧密bitset，相当于稀疏向量转换为密集向量（不做解释）

sparse vector：稀疏向量


于是原作者在从自顶向下切换到自底向上时将数据结构从biteset转换到稀疏变量以解决此问题。

  • 并行化则是将那些BFS算法中的伸缩队列和现有工作结合起来在可伸缩的NUMA多套接字架构当中，Yasui提出的算法就是结合了这些技术，是最快的并行单源BFS

2.2 顺序多源BFS

  • MS-BFS算法是多源BFS，它进一步减少了所有源点的邻居查找总数。它基于两个有关BFS的重大发现：

    • 第一：不管数据结构如何，当图足够大时，去检查一个点是否是已经遍历过的时候代价是非常昂贵的，这会使CPU的命中率下降，如果这样平凡的操作，即使是数组这样访问时间复杂度为O(1)的数据结构，都会受制于内存延迟。在当前服务器非均匀内存访问（non-uniform memory access(NUMA) ）的架构上这个问题会进一步恶化。

    • 第二：在同一连通分量运行多个BFS时，将会在每个BFS中访问该分量的每一个点，这将导致大量的计算冗余，因为在同一分量下，两个或多个BFS在访问相同深度d的同一点v时，拓展的路径（点&边）会有大量重合。（例如，BFS1 v1—>d-hop1—>v,BFS2 v2->d-hop2—>v;则d-hop1和d-hop2重合度会很高）

      连通分量：connected component

同一连通分量内的任意两点都是可达的

补充：弱连通分量，任意两点至少有有一个可达另一个

  1.         强连通分量，任意两点必须互相可达

  • MS-BFS通过优化缓解了上述两个问题，它通过三个k宽度的bitesets来表示k个独立运行且不同源点的BFS

    • biteset-seen：seen[v]，第i位表示在BFSi当中是否已经看到了v；

    • biteset-queue：frontier[v]，确定在当前的迭代中BFS是否必须访问v；

    • bitset-next：next[v] ，集合的每一位表示下一个迭代中，每个BFSs需要访问v。

    • 每一跳的迭代，都是通过seen和frontier计算出next然后将next赋值给frontier即开始了下一跳的迭代

      现在有四个并行BFSs，所以k=4;seen[v]=(1,0,0,1)表明当前这个点v已经被BFS0&BFS3访问了；

通过这个信息，BFS的一个步骤就可以通过位运算（and ( & ), or ( | ), and negation (∼):）来确定v的所有邻居n的seen和next；

  1. for n in neighbors[v]:
  2.     next[n] = next[n] | (frontier[v] & ∼seen[n])
  3.     seen[n] = seen[n] | frontier[v]
  • MS-BFS根据bitset的宽度大小来决定任意数量的并发BFS，并且，当CPU的位数等于bitset宽度时，效率达到极致，如今的机器支持32位、64位，并且当今服务器上可以使用SSE和AVX-2来扩展到128位和256位。

ps:详细的MS-BFS看另一篇笔记。【上面的frontier=visit；next=visitNext】

2.3算法局限

  • 多核CPU利用率受限于BFS数量，说白了就是如果BFS数量（源点数量）少于CPU核心数，那么CPU利用率就不能达到100%
  • 内存占用极高，随着BFS数量变多，MS-BFS算法的数据结构所需内存急剧增加。

3. 并行单源/多源BFS

3.1MS-PBFS

自顶向下的MS-BFS

  1. 1 for each v ∈ V 
  2. 2     if frontier[v] = ∅, skip
  3. 3     for each n ∈ neighborsv 
  4. 4         next[n] ← next[n] | frontier[v] 
  5. 5
  6. 6     for each v ∈ V 
  7. 7         if next[v] = ∅, skip
  8. 8         next[v] ← next[v] & ∼seen[v] 
  9. 9         seen[v] ← seen[v] | next[v]
  10. 10         if next[v] = B∅
  11. 11             v is found by BFSs in next[v]