顶点 ID,每个顶点都有一个可修改的用户自定义值与之关联,每条有向边都和其源顶点关联,并记录了其目标顶点 ID,边上有一个可修改的用户自定义值与之关联?在每个超步 S中,图中的所有顶点都会并行执行相同的用户自定义函数。每个顶点可以接收前一个超步(S -1) 中发送给它的消息,修改其自身及其出射边的状态,并发送消息给其他顶点,甚至是修改整个图的拓扑结构。需要指出的是,在这种计算模式中,边并不是核心对象,在边上面不会运行相应的计算,只有顶点才会执行用户自定义函数进行相应计算《大数据技术原理与应用》厦门大学计算机科学系林子雨 ziyulin@xmu. 9.3.2 顶点之间的消息传递图9? 2 纯消息传递模型图采用消息传递模型主要基于以下两个原因: (1)消息传递具有足够的表达能力,没有必要使用远程读取或共享内存的方式(2)有助于提升系统整体性能《大数据技术原理与应用》厦门大学计算机科学系林子雨 ziyulin@xmu. 9.3.3 Pregel 的计算过程图9? 3 一个简单的状态机图? Pregel 的计算过程是由一系列被称为“超步”的迭代组成的。在每个超步中,每个顶点上面都会并行执行用户自定义的函数,该函数描述了一个顶点 V在一个超步 S中需要执行的操作。该函数可以读取前一个超步(S -1) 中其他顶点发送给顶点 V 的消息,执行相应计算后,修改顶点 V及其出射边的状态,然后沿着顶点 V的出射边发送消息给其他顶点,而且,一个消息可能经过多条边的传递后被发送到任意已知 ID的目标顶点上去。这些消息将会在下一个超步(S +1) 中被目标顶点接收, 然后像上述过程一样开始下一个超步(S +1) 的迭代过程?在 Pregel 计算过程中,一个算法什么时候可以结束,是由所有顶点的状态决定的,当图中所有的顶点都已经标识其自身达到“非活跃( inactive )”状态时,算法就可以停止运行
全文预览
