9.3.1有向图和顶点 在每个超步S中,图中的所有顶点都会并行执行相同的用户自定义函数 每个顶点可以接收前一个超步S-1)中发送给它的消息,修改其自身及其 出射边的状态,并发送消息给其他顶点,甚至是修改整个图的拓扑结构 在这种计算模式中,“边”并不是核心对象,在边上面不会运行相应的 计算,只有顶点才会执行用户自定义函数进行相应计算 用户定义函数 F(vertex) ○表示顶点 表示发送消息 超级步(S1) 超级步S超级步(S+1) 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn
《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3.1有向图和顶点 •在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数 •每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其 出射边的状态，并发送消息给其他顶点，甚至是修改整个图的拓扑结构 •在这种计算模式中，“边”并不是核心对象，在边上面不会运行相应的 计算，只有顶点才会执行用户自定义函数进行相应计算 表示顶点 表示发送消息
932顶点之间的消息传递 消息 Compute( Compute 采用消息传递模型主要基于以 下两个原因: (1)消息传递具有足够的表达 能力,没有必要使用远程读取 或共享内存的方式 (2)有助于提升系统整体性能 Compute Computed 图9-2纯消息传递模型图 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn
《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3.2顶点之间的消息传递 Compute() 值 Compute() 值 Compute() 值 Compute() 值 消息 图9-2 纯消息传递模型图 采用消息传递模型主要基于以 下两个原因： （1）消息传递具有足够的表达 能力，没有必要使用远程读取 或共享内存的方式 （2）有助于提升系统整体性能
9.3.3 Pregel的计算过程 pregel的计算过程是由一系列被称为“超步” 用户定义函数 的迭代组成的 F(vertex) 在每个超步中,每个顶点上面都会并行执行 用户自定义的函数,该函数描述了一个顶点v① 在一个超步S中需要执行的操作 该函数可以读取前一个超步(S1)中其他顶点 发送给顶点V的消息,执行相应计算后,修改 顶点V及其出射边的状态,然后沿着顶点V的 4 ③④⑤ 出射边发送消息给其他顶点,而且,一个消 ②3④5⑥ 息可能经过多条边的传递后被发送到任意已 6 知|D的目标顶点上去 ·这些消息将会在下一个超步(S+1)中被目标顶超级51)超步3题 点接收,然后象上述过程一样开始下一个超 步(S+1)的迭代过程 ○表示顶点 表示发送消息 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn
《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3.3Pregel的计算过程 •Pregel的计算过程是由一系列被称为“超步” 的迭代组成的 •在每个超步中，每个顶点上面都会并行执行 用户自定义的函数，该函数描述了一个顶点V 在一个超步S中需要执行的操作 •该函数可以读取前一个超步(S-1)中其他顶点 发送给顶点V的消息，执行相应计算后，修改 顶点V及其出射边的状态，然后沿着顶点V的 出射边发送消息给其他顶点，而且，一个消 息可能经过多条边的传递后被发送到任意已 知ID的目标顶点上去 •这些消息将会在下一个超步(S+1)中被目标顶 点接收，然后象上述过程一样开始下一个超 步(S+1)的迭代过程 表示顶点 表示发送消息 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
9.3.3 Pregel的计算过程 在 Pregel计算过程中,一个算法什么时候可以结束,是由所有顶点 的状态决定的 在第0个超步,所有顶点处于活跃状态 当一个顶点不需要继续执行进一步的计算时,就会把自己的状态设 置为“停机”,进入非活跃状态 当一个处于非活跃状态的顶点收到来自其他顶点的消息时, Pregel 计算框架必须根据条件判断来决定是否将其显式唤醒进入活跃状态 ·当图中所有的顶点都已经标识其自身达到“非活跃( inactive)” 状态,并且没有消息在传送的时候,算法就可以停止运行 不需要执行进一步 计算就设置为停机 活跃 非活跃 收到消息后被唤醒 图9-3一个简单的状态机图 大数据技术原理与应用》 厦门大学计算机科学系 林子雨 lin@xmu.edu.cn
《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3.3Pregel的计算过程 活跃 非活跃 不需要执行进一步 计算就设置为停机 收到消息后被唤醒 图9-3 一个简单的状态机图 •在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点 的状态决定的 •在第0个超步，所有顶点处于活跃状态 •当一个顶点不需要继续执行进一步的计算时，就会把自己的状态设 置为“停机”，进入非活跃状态 •当一个处于非活跃状态的顶点收到来自其他顶点的消息时，Pregel 计算框架必须根据条件判断来决定是否将其显式唤醒进入活跃状态 •当图中所有的顶点都已经标识其自身达到“非活跃（inactive）” 状态，并且没有消息在传送的时候，算法就可以停止运行
9.34实例 a B 活跃 2+1 超步0 非活跃 -366-221 6 超步 A B C D 6 6 6 b 超步2 a B 6+1(6 6 超步3 B D 图9-4一个求最大值的 Pregel计算过程图 大数据技术原理与应用》 厦门大学计算机科学系 lin@xmu.edu.cn
《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@xmu.edu.cn 9.3.4实例 图9-4 一个求最大值的Pregel计算过程图 3 6 2 1 超步0 6 6 2 6 超步1 6 6 6 6 超步2 6 6 6 6 超步3 A B C D 活跃 非活跃 A B C D A B C D A B C D 3 6 6 2 2 1 6 6 6 6