3.1.4 大规模并行计算
大规模并行计算模型是对现实世界中并行计算系统框架进行数学抽象的一种方式，这些系统包括 MapReduce、Hadoop、Spark 和 Dryad 等。这个模型处理的是如下场景：由于图的规模太大，我们将图的边任意地存储在若干个机器上。每个机器存储图的部分数据，且这些机器的总空间几乎是整个图大小的线性函数。计算在同步轮次中进行。在每一轮中，每台机器本地对存储在本地的数据执行一些计算，然后与其他机器交换消息。这个过程可以被抽象为通信模型，其中每
台机器在每一轮中创建消息包，并将其加载到路由网络中。每台机器的空间大小也隐含地反映了大规模并行计算模型中的通信瓶颈。局部计算通常在线性或近线性时间内运行，在大规模并行计算算法的分析中通常被忽略，因为通信是瓶颈。大规模并行计算模型中算法设计的目标是使用尽可能少的通信轮次来尽可能准确地对数据进行分析。