微信小程序本地存储与登录页面处理实例详细讲解
666
2022-10-15
GraphMapReduce- 图计算框架
GraphMapReduce: 基于MapReduce编程模型的图计算框架
(名词约束: 顶点Vertex-图中顶点;节点Process-计算单元节点),目录说明:
代码主要包含四个文件: gmr.cpp gmr.h algorithms.h graph.h|__graph/---------#此目录包含测试用的图例数据|__include/-------#此目录包含所使用到的第三方库的头文件(目前只用到了ParMetis,去掉了GKlib)|__lib/------------#包含了使用到的第三方库|__gmr.cpp------#程序的main函数入口和迭代循环|__gmr.h---------#包含主要的计算过程函数computing()和计算结果更新函数updateGraph()|__algorithm.h—#常用图算法的MapReduce实现|__graph.h-------#定义了图数据结果和常用的集中图操作函数
一. 框架的基础
1. MPI:
结算节点之间通信通过MPI实现;
2. MapReduce编程模型
3. 图划分:
为了将整图的不同部分放到不同的计算节点进行并行计算,需要将整划分为若干子图。本框架中每个子图包含三个部分{inners, borders,neighbors},inners表示子图内与其他子图没有连接的顶点;borders表示子图内与其他子图又连接的顶点;neighbors表示子图外与本子图连接的顶点。
二、迭代计算过程
1. 数据交换:
第一步,先遍历自己计算的子图graph与其他子图的邻居情况,并收集需要向其他节点发送的字节数,并申请发送缓冲区;
第二步,通过MPI_Alltoall()与其他节点交换其他节点需要接受的字节数,每个节点收到信息后,各自计算和申请接受数据需要的空间。
第三步,再次遍历自己计算的子图graph,并将需要发往其他节点的顶点信心拷贝到发送缓存char *sb;
第四部,调用MPI_Alltoallv(),将发送缓存中的数据发往各节点.
2. 计算1th/2:map
将子图graph和接受缓冲区中的数据实例化为顶点Vertex,再调用业务逻辑函数map将Vertex生成key/value list。
3. 对生成key/value list进行排序: sort
4. 计算2th/2:reduce
将排序好的key/value list按照业务逻辑函数reduce进行规约.
5. 将reduce计算的结果更新到graph中
三. 编译和运行
1. (not mandatory)切图
切图采用了metis库,其源码和说明位于include/metis中,其编译使用可参考include/metis/README.md.已经有切好的例图,位于graph/下。
2. 编译gmr
make clean && make
3. 运行
mpirun -np graph_nparts ./gmr
四. 例子
4.1 PageRank
4.1.1. 如下包含10个顶点的简单图,划分之后包含三个子图subgraphs[3]:
4.1.2. 迭代过程
每个子图现将自己的边界顶点发送给其所连接的邻居节点,采用MPI_Alltoall()实现;在每个计算节点的内部,将每个顶点映射为若干键值对: > {key, value1},其中key in [neighbors], value1 = value / neighbors.size()void map(Vertex &v, std::list
4.2.3 PageRank终止点问题和陷阱问题
上述上网者的行为是一个马尔科夫过程的实例,要满足收敛性,需要具备一个条件: 图是强连通的,即从任意网页可以到达其他任意网页:互联网上的网页不满足强连通的特性,因为有一些网页不指向任何网页,如果按照上面的计算,上网者到达这样的网页后便走投无路、四顾茫然,导致前面累计得到的转移概率被清零,这样下去,最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉,C变成了一个终止点,得到下面这 个图:
另外一个问题就是陷阱问题,即有些网页不存在指向其他网页的链接,但存在指向自己的链接。比如下面这个图:
上网者跑到C网页后,就像跳进了陷阱,陷入了漩涡,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~