1.介绍

这里就省略了，SMS-PBFS已经讲过了。

2.背景

2.1图

和SMS-PBFS一样是small-world networks的无权无向图，符合六度分隔理论

2.2 BFS介绍

BFS algorithm

  1. 1 Input: G, s
  2. 2 seen ← {s} 
  3. 3 visit ← {s} 
  4. 4 visitNext ← ∅ 
  5. 5
  6. 6 while visit = ∅ 
  7. 7     for each v ∈ visit
  8. 8         for each n ∈ neighbors of v
  9. 9             if n !∈ seen
  10. 10                 seen ← seen ∪ {n}
  11. 11                 visitNext ← visitNext ∪ {n}
  12. 12                 do BFS computation on n
  13. 13     visit ← visitNext
  14. 14     visitNext ← ∅

  • 解释

    • BFS从源点开始，各个顶点都会有两种状态：discovered和undiscovered
    • discovered代表访问了这个点，同时还意味着explored它的邻居
    • BFS从将源点s添加到seen开始，还会添加一组将要访问的点visit。
    • 迭代访问v in visit（7）
    • 探索新的点n，这些点是v的邻居（8）
    • 如果n是undiscovered，则将n添加到seen和visitNext中（9~11）
    • 可以进行一些其他算法的操作（例如最短路径算法可以在此时存储s和n的距离）（12）
    • 剩下的不解释了太简单

  • 优化BFS：

    • 在small-world networks图中，连通分量很少甚至为1，所以图很大的时候，BFS随机访问边和点就会很多，导致CPU命中率下降，从代码8、9行可见，遍历seen和邻接表时，会有大量随机访问（这就是命中率降低）。
    • 在2、3跳以后，会有大量的点被找到（六度分隔），导致你遍历邻接表时，未被发现的点远少于已发现的点，那么（代码第9行）会导致许多无用的查找（这就是计算冗余），visit里面大量无用数据也会占用内存。

  • 优化措施：

    • 针对机器结构、存储结构等优化数据结构，对硬件系统的优化
    • Beamer的自下而上MS-BFS，他尽量去避免遍历visit，而是通过迭代undiscovered点，根据其边去找到discovered点，也就是visist内的点。

3.MS-BFS

  • 目标

    • 避免CPU命中率降低
    • 避免资源耗费
    • 避免过高同步成本

  • 方案

    • 利用small-world networks特性共享计算
    • 在单核CPU中并发数百个BFS
    • 既不用锁，也不用原子操作

3.1MS-BFS algorithm

如果直接跑多个BFS（不做其他操作）就会发现，在单连通分量图中，每个点都会被重复访问多次（次数=BFS数量）。small-world networks的特性让多个BFS当中，在第三度或第四度的时候已经将绝大部分的点都访问完了。

伪代码

  • 首先，程序输入图G，BFSs B，还有所有所有BFSs的源点si的集合S（下面的ω代表BFSs数量）[Line1]

  • seen不再是已发现的点集而是每个点都有个自己的集合，表示自己是否被某个BFSs看见

  • visit和visitNext包含多个元组 (v’, B’ ),而B’包含于B，表示这些BFSs下一跳必须探索点v’

  • 默认将所有源点对应的BFSs标记上，赋值给seeni，代表已经访问[Line2]

  • 将所有源点和它对应的BFS组成元组，赋值给visit，代表初始状态需要探索的点[Line3]

  • 接下来开始迭代：[Line6]

    • 遍历visit的点v（即元组(s,b)的 s）[Line7]

      • 令B’v为空，然后将visit中所有当前点v的元组(当前点v，正在探索v的BFSs)并到B’v当中[Line7~10]
        此时，B’v当中包含所有当前跳正在探索v的BFSs，所以同一时刻v只会被遍历一次

      • 在11-16行表现出了BFSs共享计算探索的过程

      • 对于每个v的邻居n，算法先找到下一跳需要去探索n的BFSs，存到set D当中[Line 12]
        这些BFSs bi须符合这些条件：首先是bi正在探索v（即bi∈B’v），且此bi还没探索过n（即bi!∈seen(n))

      • 如果D不为空[Line 13]，代表至少有一个BFS需要在下一跳探索n，因此我们将元组(n,D)赋值给visiNext[Line 14]，因为下一跳一定会探索n，所以提前将BFSs D并到seen(n)当中[Line 15]

      • 此时可以做一些基于BFS的其他算法的操作[Line 16]
        注意：D当中的BFSs bi∈D仅对邻居遍历一次，并且在下一跳中，这些BFSs 只会对每个n探索一次。所以运行大量BFS时，就大量减少了内存访问次数

    • 将visist更新为visitNext的值[Line 17]

    • visitNext置空[Line 18]

小结：

  • 算法就是在每一跳的时候，将所有BFSs的状态统一到一个set（visit(v)）里面，还有对全局所有点对应BFS的遍历状态(seen)
  • 通过上述集合，可以得到当前所有BFSs的遍历状态，就可以以O(n)的时间分析出每个下一跳应该遍历的点n应该被哪些BFSs探索
  • 而visitNext其实就是个临时变量（相当于tmp），每次迭代都会置空，用于存放下一跳遍历的策略
  • 这样，在传统BFS当中，每一跳每个BFS都要遍历一次neighbor和next就变成了每一跳所有BFSs只遍历一次neighbor和next，当BFSs变多时，差距就拉开了
  • 这个算法并不是并行处理一个BFS，而是多个BFSs并行同时执行，并且BFSs信息（状态）共享

例：

  1. 算法输入图G、BFSs B、源点 S

  2. 初始化：seen1={b1},seen2={b2},visit={(1,{b1}) , (2,{b2})}【空集:seen3={},seen4={},seen5={},seen6={}】

  3. 第一跳：遍历visist中的点（1、2）；B’1={b1},B’2{b2}；遍历邻居n(3,4)；
    D={b1}:v=1,n=3,4 ∪ visitNext【D是正在遍历1且没遍历过3,4的BFS，并到visitNext】；B’3={b1,b2};
    D={b2}:v=2,n=3,4 ∪ visitNext【D是正在遍历2且没遍历过3,4的BFS，并到visitNext】；B’4={b1,b2}；
    visitNext={(3,{b1}) , (3,{b2}) , (4,{b1}) , (4,{b1})}赋值给visit；
    seen3={b1,b2},seen4={b1,b2}；

  4. 第二跳：遍历visit中的点（3、4）；B’3={b1,b2}，B’4={b1,b2}；遍历邻居n(1,2,5,6)；
    D={b1}:v=3,n=2,5,6 ∪ visitNext【D是正在遍历3且没遍历过2,5,6的BFS，并到visitNext】；
    D={b2}:v=4,n=1,5,6 ∪ visitNext【D是正在遍历4且没遍历过1,5,6的BFS，并到visitNext】；
    visitNext={(1,{b2}) , (2,{b1}) , (5,{b1,b2}) , (5,{b1,b2})}赋值给visit；
    seen1={b1,b2},seen2={b1,b2},seen3={b1,b2},seen4={b1,b2},seen5={b1,b2},seen6={b1,b2}；

  5. 第三跳（结束）：遍历visist中的点（1、2、5、6）；B’1={b2},B’2{b1},B’5={b1,b2},B’6{b1,b2}；遍历邻居n(3,4)；
    D={}:v=1、2、5、6，n=3、4；【D是正在遍历1or2or5or6且没遍历过3or4的BFS,是空集】；
    ∵D=∅；visit<—visitNext=∅
    结束迭代。

3.2位运算优化

上述算法用集合求并集一类的操作很慢，还要去遍历seen来查看点有没有被看过，效率低下，我们换种数据结构来优化算法

  • 数组seen[i]表示某个点被哪些BFS发现，操作中1<<bi就是将第i号BFS（假设我们就这么编号）访问，这样二进制数第i位是1，假设第j位是0代表第j个BFS没有发现点i；
  • visit同样
  • 开始迭代[Line 7]
  • 遍历点1~N
  • 如果点i正被探索：

  • 遍历i的邻居n

    • visit[vi]&~seen[n]代表没发现n的线程（seen取反）且（&）正在访问vi的BFS bi
    • 如果确实存在bi（D!=∅）
    • visitNext[n]|D 代表（注意：第一次循环visitNext是置空（全0）的）将所有可以遍历邻居的BFS bi并到visitNext中【因为是遍历多个邻居，所以visitNext充当个缓存器（buff）】
    • 做些其他算法操作
  • 然后visit更新，即代表下一跳所有线程各自该访问哪一个点
  • 置空visitNext（置为全0）

所以，用位运算效率就取决于CPU位数的限制，这一点详细介绍看SMS-PBFS。

例：

和上面例子一样的，更简单就不解释了

4.算法调优

4.1 Memory Access Tuning

在上述算法中，还是存在随机访问过大，在Line11、13、14处会有大量随机访问，且同样存在同一个neighbor n被多次访问，因为一个n可能在同一个深度有多条入边，所以在Line8和10中，很可能存在点v1,v2都有同一个邻居n，例子中就是这种情况。

所以在此引入ANP策略即聚合邻居策略（Aggregated Neighbor Processing）

ANP：

  • 简而言之，就是在BFS之前先将下一跳所有要遍历（i.e.包括所有v的所有邻居在内）先更新到visitNext当中，再进行BFS。

  • 测试：

    测试数据和上面的例子完全一致

BFS策略

尽管MS-BFS已经极大地减少了数组（位集）的遍历次数，但是在最后一跳或几跳的时候，还是会有扫描很多遍历过的无效点（虽然只遍历一次，但是还是浪费很多资源）

Beamer将MS-BFS分成了两种策略：自上而下和自下而上，自上而下就是传统的MS-BFS，而自下而上则相反，通过遍历seen来找到当前未被BFS发现的点，然后从这些点开始反向遍历找到已发现的点，通常情况下，自上而下通常是第一跳或前几跳的BFS采用的策略，自下而上则是最后一跳或几跳采用的策略，两策略在BFS中是可以互相转换的。