每周学点大数据 | No.47 BSP 模型下的单源最短路径

No.47期

BSP 模型下的单源最短路径

我们先来举个例子吧。单源最短路径也是一种很典型的图论问题,前面我们提到过,就是求解从一个源点到各个节点的最短距离,有时带上求解最短路径。我们来看看如何“把自己想象成一个节点”。以下面这个图为例。

在这个图中,我们选取的源点是0 号节点。图中有一些有向边,每条有向边都有一个权值。

我们要求解的就是源点0 抵达其他4 个节点的最短距离。

在第一轮迭代中,每一个其他节点都向外发送自己的权值,节点的权值表示当前状态下源点0 到它的最短距离。此时其他节点到源点0 的最短距离都是∞。而源点向外发送其出度边的值,就像这样:

经过了第一轮迭代,图中的权值会变成这样:

源点0 右侧的两个节点的权值进行了更新,它们拥有当前状态下到源点的最短距离10 和5。

从第二轮开始,每一个节点向外发送的权值都略有变化,每一个节点向它每一个出度顶点,这条出度边的权值与其当前到源点的最短距离,也就是其顶点的权值。结果就是这样:

小可:哦,我懂了,接下来要比较每一个节点收到的值是不是比当前的最短距离要小,如果是,就要替换当前的节点权值。

Mr. 王:没错,经过这一轮替换,结果就是这样:

这样每一轮节点都继续执行如同第二步的工作,有些节点在某轮中既不发出消息,也不接收消息,这样这些节点就停摆了。一旦在某轮中所有的节点都停摆了,整个算法就结束了。每一个节点上的权值就是源点0 到该节点的最短距离。

Mr. 王:现在我们要想一想,这样做和MapReduce 的区别。在Pregel 平台上程序设计的最大特点就是从图中每一个节点出发,在执行计算的机器上保持顶点和边,用网状结构传输信息。

也就是说,每一个节点,或者说保存着这些节点的每一台机器不需要知道整个图的结构,只需要执行自己本轮应该执行的操作就可以了。这样做可以说是一种“真正的”分布式思想。

而MapReduce 则不然,虽然在解决图问题时我们可以设计一轮轮MapReduce 去进行图算法中的迭代,但是每一阶段都要利用整个图的全部状态,需要整合MapReduce 链。这意味着MapReduce 只是借助了分布式计算平台,让多台机器投入到图算法的求解中来,却不能在出现多轮迭代的图计算中实现“真正的”分布式。

小可兴奋地说:我很想尝试用Pregel 去写一个图算法,在实际使用中应用Pregel 是怎么做的呢?

Mr. 王打开电脑中的一段代码,说:这就是Pregel 的C++ API。其实Trinity 平台的API 和Pregel 的都是比较类似的,可以触类旁通。

在实际使用的过程中,需要定义的就是节点这个类。我们要重载节点的几个函数,也就是前面提到的执行操作(Compute 函数,其中的msgs 就是收到的来自其他节点的信息)、发送信息(SendMessageTo 函数),当然还有一个重要的VoteToHalt,这个函数用来确定整个系统是不是停摆,比如本轮中某节点没有动作,它就投票停机,如果所有的节点都投票停机了,那么就说明整个系统已经不再变化了。对于每一个节点来说,其各项值和送出信息的数据类型都是不同的,在实际的设计过程和使用过程中,可以借助模板类来确定。

小可好奇地说:我还想看看最短路径这个程序具体是怎么写的。

Mr. 王:我这里刚好有一份最短路径的代码。

我们一起来剖析一下这段代码。和前面的框架是相符的,继承了顶点类,派生出最短路径节点类,在派生类中重载了Compute 函数,程序在执行过程中我们要做的就是遵循前面提到的思想,接收所有节点向我发送的消息,然后判断这些消息中包含的路径权值是不是比我小,如果小就更新我的节点。同时我也要向其他节点发送包含我最短路径和出度边长之和的消息。最后,如果本轮没有任何动作和改变,我要执行投票停机这个操作。

小可:如果我想部署一个Pregel 平台,需要怎么做呢?

Mr. 王:一般来说,一个Pregel 平台都需要运行master 和worker 两种进程。其中master主要完成维护worker、恢复worker 产生的错误、提供一个以网页形式表现的用户界面来控制和监督worker 进程的执行情况;而worker 是工作的主要承担者,它负责在每一轮迭代中处理自己的任务并且与其他worker 进行消息传递。至于数据的存储,一般会选用GFS 和BigTable这样的分布式文件系统,一些临时产生的、内存存不下的大量中间结果,会相应地被存储在磁

盘中。

在实际的运行过程中,往往是多个程序的副本在服务器集群中执行,然后由master 进程分配划分内容作为每一个worker 的输入。每一个worker 会存储和执行多个图中的顶点并标记它们。

在master 的命令调度下,每一个worker 执行自己的Superstep。每一个worker 循环通过已标记的顶点计算每个顶点。整个网络中没有统一的时钟来标注什么时间去进行信息传递,而是采取信息异步传输,有需要的时候自行传递即可,但所有的信息传递都要在Superstep 结束前传送完毕。系统会不断地重复以上步骤,直到没有已标记顶点或信息传输,此时我们想要的结果就已经求解出来了。在程序运行停止后,master 会命令每一个worker 保存图的部分信息。

下期精彩预告:

经过学习,我们讨论了一种很典型的图论问题——单源最短路径。在下一期中,我们将学习计算子图同构问题。更多精彩内容,敬请关注灯塔大数据,每周五不见不散呦!

内容来源:灯塔大数据 文章编辑:柯一

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Dubbo入门学习--负载均衡策略(4)

Dubbo入门学习--负载均衡策略 负载均衡 ? Random LoadBalance 随机,按权重设置随机概率。 在一个截面上碰撞的概率高,但调用量越大分布越...

35840
来自专栏Gaussic

OpenBr快速入门 原

这篇教程旨在使用一些有趣的例子让你熟悉OpenBR背后的思想、对象以及动机。注意需要摄像头的支持。

22010
来自专栏QQ音乐技术团队的专栏

Android 中图片压缩分析(上)

在 Android 中进行图片压缩是非常常见的开发场景,主要的压缩方法有两种:其一是质量压缩,其二是下采样压缩。

1.4K20
来自专栏Spark学习技巧

第2篇:数据库关系建模

第二篇:数据库关系建模 前言 ER建模环节完成后,需求就被描述成了ER图。之后,便可根据这个ER图设计相应的关系表了。 但从ER图到具体关系表的建立还需要经过两...

34860
来自专栏CVer

重磅:TensorFlow实现YOLOv3(内含福利)

YOLO官网:YOLO: Real-Time Object Detection keras-yolo3:https://github.com/qqwweee/k...

13.5K200
来自专栏宏伦工作室

深度有趣 | 01-02 前言和准备工作

用 Python 做一些有意思的案例和应用,内容和领域不限,可以包括数据分析、自然语言理解、计算机视觉,等等等等

11420
来自专栏新智元

【TensorFlow1.2.0版发布】14大新功能,增加Intel MKL集成

【新智元导读】TensorFlow 今天发布最新版 1.2.0,公布了14大最新功能。新智元带来最新介绍,包括 API 的重要变化、contrib API的变化...

35290
来自专栏IT笔记

Dubbo负载均衡配置

在集群负载均衡时,Dubbo提供了多种均衡策略,缺省为random随机调用。 负载均衡扩展 (1) 扩展说明: 从多个服务提者方中选择一个进行调用。 (2) 扩...

49150
来自专栏媒矿工厂

Ittiam优化VP9,turnaround时间大幅减少

libvpx是Google开发的视频编解码器VP8和VP9的开源软件实现库。libvpx中包含了VP9视频编码算法,相比H.264/AVC,在高...

32750
来自专栏CVer

ECCV 2018 776篇论文一键下载

昨天推送了ECCV 2018 收录论文名单全公布,看到很多CVer纷纷转发至朋友圈,Amusi真的很开心!

36320

扫码关注云+社区

领取腾讯云代金券