PDF《第9章 图计算》

《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.

edu.cn 2013年9月修订版 厦门大学计算机科学系 2013年新版 林子雨 厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn 主页:http://www.cs.xmu.edu.cn/linziyu 第9章 图计算 (2013年新版) 厦门大学计算机科学系研究生课程 《大数据技术基础》 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 课程提要 ? 图计算简介 ? Google Pregel图计算模型 ? Pregel的C++ API ? Pregel模型的基本体系结构 ? Pregel模型的应用实例 ? 改进的图计算模型 ? 参考资料 本讲义PPT存在配套教材,由林子雨通过大量 阅读、收集、整理各种资料后编写而成 下载配套教材请访问《大数据技术基础》2013 班级网站:http://dblab.xmu.edu.cn/node/423 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 图计算中的问题 ? 大型图(像社交网络和网络图等)常常作为现在系统计算需要的一 部分.现在存在许多图计算问题像最短路径、集群、网页排名、最小 切割、连通分支等等,但还没有一个可扩展的通用系统来解决这些问 题. ?解决这些问题的算法的特点:它们常常表现为比较差的内存访问局 部性、针对单个顶点的处理工作过少、以及计算过程中伴随着的并行 度的改变等问题. ?可能的解决方法: ?为特定的图应用定制相应的分布式实现 ?基于现有的分布式计算平台 ?使用单机的图算法库 ――如BGL,LEAD,NetworkX,JDSL,Standford ,GraphBase,FGL等 ?使用已有的并行图计算系统 ――如Parallel BGL,CGMgraph等 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 图计算的两种软件 目前通用的图处理软件主要包括两种.一种主要基于遍历算法、实时 的图数据库,如Neo4j , OrientDB , DEX , 和InfiniteGraph .另一种则是以图 顶点为中心的消息传递批处理的并行引擎,如Hama , Golden Orb , Giraph , 和Pregel .第一种基本都基于tinkerpop的图基础框架,tinkerpop项目关 系如图1所示: 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 BSP模型 以图顶点为中心的消息传递批处理的并行引擎主要是基于 BSP(Bulk Synchronous Parallel)模型所实现的并行图处理包.BSP是 由哈佛大学Viliant和牛津大学Bill McColl提出的并行计算模型.一个BSP模型由大量相互关联的处理器(processor)所组成,它们之间 形成了一个通信网络.每个处理器都有快速的本地内存和不同的 计算线程.一次BSP计算过程由一系列全局超步组成,超步就是计 算中一次迭代.每个超步主要包括三个组件: ?并发计算(Concurrent computation):每个参与的处理器都有 自身的计算任务,它们只读取存储在本地内存的值.这些计 算都是异步并且独立的. ?通讯(Communication): 处理器群相互交换数据,交换的形式 :由一方发起推送(put)和获取(get)操作. ?栅栏同步(Barrier synchronisation): 当一个处理器遇到路障, 会等到其他所有处理器完成它们的计算步骤.每一次同步也 是一个超步的完成和下一个超步的开始. 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 Superstep 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 Pregel是由Google开发的一个用于分布式图计算的计算框架,主要用于图遍 历(BFS)、最短路径(SSSP)、PageRank计算等等.共享内存的运行库有很多, 但是对于Google来说,一台机器早已经放不下需要计算的数据了,所以需要分 布式的这样一个计算环境.没有Pregel之前,可以选择用MapReduce来做,但是 效率很低.下面简单介绍一下PageRank算法在Pregel和MapReduce中的实现. PageRank算法作为Google的网页链接排名算法,具体公式如下: 对任意一个链接,其PR值为链入到该链接的源链接的PR值对该链接的贡献 和(分母Ni为第i个源链接的链出度). Pregel的计算模型主要来源于BSP并行计算模型的启发.要用Pregel计算模型 实现PageRank算法,也就是将网页排名算法映射到图计算中,这其实是很自然 的,网络链接是一个连通图. Pregel图计算框架 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 上图就是四个网页(A,B,C,D)互相链入链出组成的联通图.根据Pregel的计算模 型,将计算定义到顶点(vertex)即A,B,C,D上来,对应一个对象,即一个计算单元. 每一个计算单元包含三个成员变量: ? Vertex value:顶点对应的PR值?Out edge:只需要表示一条边,可以不取值 ? Message:传递的消息,因为需要将本vertex对其它vertex的PR贡献传递给目标 vertex 每一个计算单元包含一个成员函数: ? Compute:该函数定义了vertex上的运算,包括该vertex的PR值计算,以及从该 vertex发送消息到其链出vertex PageRank在Pregel中的实现 《大数据技术基础》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 2013年9月修订版 PageRank在Pregel中的实现 class PageRankVertex : public Vertex { public: virtual void Compute(MessageIterator* msgs) { if (superstep() >