跳转至

Parallel BFS

常规广度优先搜索的局限性

简单bfs是每次从队列中取出当前的访问节点后，之后就将它的邻接节点加入到队列中，这样明显不利于并行化。

实现一： 两队列

使用了两个队列，第一个队列存当前同一层的节点，第二个队列用来存储当前层节点的所有邻接节点(下一层节点)，等到当前层的节点全部访问完毕后，再将第一个队列与第二个队列进行交换，即可。

这样做的优势在于便于以后的并行化。同一层的节点可以一起运行，不会受到下一层节点的干扰。

但是写有问题，并行计算要储存下一层节点时，push操作不是原子的，需要加锁。 

q1.push(1);
   distance[1]=0;
   while(!q1.empty()){
      clear(q2);
      for(int i=0;i<q1.size();i++){
         int node=q1.front();
         q1.pop();
         cout<<node<<"->";
         int start_edge=g.outgoing_starts[node];
         int end_edge=(node==g.num_nodes-1)?g.num_edges:g.outgoing_starts[node+1];
         for(int j=start_edge;j<end_edge;j++){
               int outgoing=g.outgoing_edges[j];
               if(distance[outgoing]==-1){
                  distance[outgoing]=1;
                  q2.push(outgoing);
               }
         }
      }
      swap(q1, q2);
   }

实现二：PBFS

思想和实现一一样，但是对并行时竞争情况有处理。

思想：都是将并行处理的一层节点bag的相邻节点存到下一次处理的bag中。

竞争：

  1. 第 18 行的 v.dist 更新为 d+1。
  2. 幸运的是，由于都是设置为同一个值，该竞争不影响结果。
  3. 第19行，可能同时将同一个节点加入out-bag,导致额外的工作
  4. 但是这个bag数据结构是具有元素各异的性质，正好解决这个问题。
  5. 根本没有元素各异好吧。
  6. 第19行，可能同时将同一个节点加入out-bag,不会写同一个地方吗？insert

最后还是要加锁，屮。

辅助数据结构 - pennant

辅助数据结构，称为 "pennant"， 是一个\(2^k\)个节点的特殊树。根只有个left子节点，该子节点有个完整是二叉树。

通过这个辅助数据结构，可以实现动态无序集的 bag 数据结构

注意，普通的k层完全二叉树，有\(\(1+2+4+2^{k-1}=2^k-1\)\)个节点。 

PENNANT-UNION(x,y)
   1 y. right = x. left
   2 x. left = y
   3 return x

PENNANT-SPLIT(x)
   1 y = x. left
   2 x. left = y. right
   3 y. right = NULL
   4 return y

数据结构 - bags

bag是pennant的集合，其中没有相同大小的pennant。PBFS采用固定大小的数组S[0...r]称作 backbone 骨干。 数组中的第k元素S[k]为空或者保存着指向大小为\(2k\)的pennant。可知，整个数组S[0...r]最多保存\(2\)元素。 所以BAG-CREATE分配了保存空指针固定大小的数组backbone,会花费Θ(r)时间。

This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.

BAG-Insert类似二进制计数器递增的过程 

BAG-INSERT(S,x)
   1 k = 0
   2 while S[k] != NULL
      3 x = PENNANT-UNION(S[k],x)
      4 S[k++] = NULL
   5 S[k] = x                 #不执行循环 S[0] = x,不是在图7这种插入。

BAG-UNION(S1,S2)     
   1 y = NULL // The “carry” bit.
   2 for k = 0 to r
   3 (S1[k],y) = FA(S1[k],S2[k],y)
BAG-UNION(S1,S2)因为每一个PENNANT-UNION都需要固定的时间，计算FA（x，y，z）的值也需要恒定的时间。计算结果包主干中的所有条目需要Θ（r）时间。该算法可以改进为Θ（lgn），其中n是两个包中较小的包中的元素数，方法是保持每个包主干的最大非空索引，并将索引较小的包合并为索引较大的包

其中FA(x,y,z)相当于三个数的加法，c是进位，s是余位。

函数解释

函数时间开销

BAG-CREATE O(1) BAG-INSERT(n) O(1)-O(lgn) BAG-UNION(n) ~O(lgn)

函数时间开销

需要进一步的研究学习

暂无

遇到的问题

PBFS: 1. 11行为什么是lg呢，全部遍历不好吗？ 1. 因为存的是\(2^r\)的元素

This bound can be improved to O(1) by keeping track of the largest nonempty index in the backbone.

开题缘由、总结、反思、吐槽~~

flood fill的需要

参考文献

https://www.cnblogs.com/JsonZhangAA/p/9016896.html

https://zhuanlan.zhihu.com/p/134637247

A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) from ACM SPAA 2010