《数据密集型计算和模型》第五章的有关内容。主要有BSP模型简介、BSP模型的发展状况、基于BSP模型的编程架构等。

英国著名计算机科学家 Leslie G. Valiant 提出了BSP模型。

一、BSP模型简介

1. BSP模型概念

【BSP模型可以定义为一下三个属性的结合】：

• 具有执行计算或存储功能的组件
• 提供组件之间点对点消息传递的选路器
• 用于在每个时间间隔L对所有或部分组件实现同步功能的设施，其中L为周期参数。

2. BSP模型原理（*）

• 在BSP模型中，计算由一系列**超步组成，在每一超步中，每个组件执行局部计算**，传递和接收消息。
• 每一周期时间间隔L作一个全局检查，以确定该超步中是否所有组件已经完成任务，如果完成则进入下一个超步；否则，下一个时间周期分配给未完成的超步。

3. BSP模型的优缺点

（1）优点

1. 不易死锁
2. 易于编程
3. 性能可预测
4. BSP模型与具体的硬件结构无关

（2）缺点

• BSP模型把所有的处理器以及处理器之间的通信同等看待，没有区分计算节点之间的能力差异以及通信距离的远近，导致在每一次超步都需要等待最慢的那个节点。

二、BSP模型发展概况

1. BSP模型初级阶段

1. DBSP模型
2. NBSP模型
3. 进程迁移BSP模型
4. 异构环境的BSP模型
5. 共享内存的BSP模型

2. 多核BSP

（1）BSP模型在云平台上的应用

【OSL】

• OSL是一个用c++语言在MPI通信库基础上编写的BSP算法框架库，包括数据并行框架和通信框架。

【BSPCloud】

• BSPCloud是一套云环境下BSP编程工具软件，目的是为开发人员提供一套BSP编程函数库，可用于云平台上I/O密集型应用。

（2）BSP模型在大数据时代的应用（*）

【Pregel】

• 为了解决大规模图算法问题，Grzegorz Malewicz等人基于BSP模型实现了一个大规模图形处理框架Pregel。
• Pregel具有高效、可扩展、容错、容易编程等特点，可部署在上千台计算节点的集群上。

【HAMA】

• HAMA是基于BSP模型的通用并行计算框架。
• 用于大规模的科学计算。

【GPS图像处理系统】

• GPS是一个完全开源的高可扩展性、高容错性和易于编程的大规模图处理系统。
• GPS的特征：
  • 可扩展的API使全局通信更易于表达和高效
  • 可以基于消息模式在计算过程中重新划分顶点到不同的工作节点
  • 在所有计算节点上划分相邻高度数节点列表以减少通信开销。

【Giraph】

• Giraph是一个迭代的图形处理系统
• 在Pregel的基础上增加了主节点计算、共享聚合、面向边的输入、核外计算等特征。
• Giraph可用于图数据处理和分析

三、基于BSP模型的编程框架

1. Prege

（1）概述

• Pregel计算由一系列的迭代组成，每一次的迭代称为一个**“超步”**。
• 在每一次超步中，Pregel都会调用每个顶点上用户自定义函数，在概念上这个过程是并行的。

（2）计算模型

• Pregel计算的输入是一个有向图
• 一个典型的Pregel计算过程包括**读取输入数据、初始化图、运行一系列被全局路障隔离的超步**直到整个计算结束、输出结果。
• 算法是否结束取决于是否所有的顶点都已经到达“Halt”状态。
• Pregel程序的输出是所有顶点输出的集合。

（3）Pregel的API（基类）

编写一个Pregel程序应该包含Pregel中已预先定义的一个子类-------Vertex类。

该类模板参数中定义了与顶点、边、消息相关的三种类型。

【通过模板如何进行解读】：

• 用户需要重写Vertex类的虚函数Compute（），在每个超步中，每个活跃的顶点将会执行Compute（）函数。
• 预定义的Vertex方法允许Compute()函数查询当前顶点和其边的信息，并发送到其他的顶点。
• Compute()函数可以通过GetValue()函数来检查与其顶点相关的值，或者通过调用MutableValue()函数来修改当前顶点的值，它还可以通过出边迭代器提供的方法来检查和修改出边的值。

【消息传递机制】

• 顶点之间的通信是通过消息传递的方式，每个消息都包含一个消息值和目的顶点的名称。
• （这里有一个算法）

【Combiners】

【聚合器】

【拓扑结构变化】

• 在同一个超步中，多个顶点发出的请求可能发生冲突
• Pregel中采用两种机制来决定如何选择：局部有序和Handlers

【输入输出】

（4）Pregel的具体实现

【基本体系结构】

Pregel将一张图分解成许多子图，每一个子图包含一系列顶点和所有这些顶点的出边。

将一个顶点分配到某个子图上仅仅取决于该顶点的ID

【容错】

• Pregel的容错是通过检查点来实现的。
• Pregel还支持密闭恢复策略

【工作节点的实现】

• 一个工作节点负责维护分配给他的内存中的部分图的状态

【主节点的实现】

• 主节点主要负责协调工作节点的活动
• 主节点同时还维护计算机进展和图的状态的统计信息

2. HAMA

HAMA是一个建立在hadoop平台上的分布式框架，主要用于大规模矩阵计算和图计算。

（1）组成

• 提供许多原语的HAMA Core
• 一个交互式用户控制台 HAMA Shell
• HAMA API

（2）优点

1. 兼容性好
2. 可扩展性
3. 灵活性
4. 适用性

（3）应用案例：线性代数

1. 用HBase表示矩阵
2. 矩阵乘法

3. GPS

GPS（图形处理系统）是一个可扩展、具有容错功能和易于执行大规模图算法的完全开源系统。

特点：

• GPS提供的API进行了扩展，可以有效地实现包含一个或多个顶点为中心的计算和全局计算结合的算法。
• GPS在计算过程中可以通过在工作节点之间对图进行重新划分，来减少通信（通信优化）
• GPS具有一个LALP的优化机制，该机制可以在工作节点上对度数高的顶点的邻接表进行划分，这将进一步减少通信量。

4. Giraph

是一个迭代的图处理系统。

• Giraph的工作节点使用Zookeeper选择一个主节点来协调计算
• 一个Giraph计算的输入是一个由顶点和有向边组成的图。

Giraph的计算方法：

1. 接收在上一个超步中发送给该顶点的消息
2. 使用接收到的消息，顶点和出边的值进行计算，这可能导致该顶点值的修改
3. 发送消息到别的顶点。

（算法）