毕 业 设 计（论文） 外 文 文 献 翻 译
文献、资料中文题目：Bigdata的一种新的计算模型 文献、资料英文题目： 文献、资料来源：
文献、资料发表（出版）日期： 院 （部）： 专 业： 班 级： 姓 名： 学 号： 指导教师：
翻译日期： 2017.02.14
英文文献译文
第12章
Bigdata的一种新的计算模型
摘要：自从几年前BigData一直是一个热门词汇。但是，什么是完全对应的（理论值）的计算机模型？可以做些什么并且不能以这样的模式来完成？这些都要求答案的问题。最近，一个模型提出通过模拟受限制，以解决这个问题版本PRAM模型。在本文中，我们提出了所谓的理论模型主/从多处理器（MSM简称），这是非常类似于一个实际使用MapReduce的但有额外的限制有关BigData系统处理。此模型捕获一些最重要的属性的实用的粗粒度多处理器（CGM）模型（而不是PRAM）。该在这样的主/从模式最重要的思想是：（1）即使主只能在任何给定访问所有的数据的一小部分在其从属处理器时间，（2）大量的从节点之间的数据传输的被认为是不可能或成本过高，和（3）一个额外的从属处理器，与数据一起它 携带，可以很容易地集成到系统支持的可扩展性。在这样的一个模型捕获实际的MapReduce的最重要的特征系统，一些标准问题，如排序，成为难以解决的问题。然后，我们提出了一种自适应MSM模型，其中主节点仍具有有限的工作内存，但大中专storage.We演示如何这两款车型的MSM可以用来解决一些基本问题，当数据量是巨大的。
12.1简介
自从几年前BigData一直是一个热门词汇。几乎在每一个行业，我们听说有人在谈论BigData，一个突出的例子就是庞大的数据allWalmart交易量，或搜索查询谷歌已经处理，或视频监控系统监控所有的道路交叉口在纽约市，所有只是在一个单一的一天。在不同的国家资助机构设立研究项目针对不同地区处理BigData。总之，BigData在那里并且将改变我们lives.We需要正确地处理它们，如果没有，它们将变得我们的负担。 尽管如此，似乎不存在一个普遍接受的模型BigData计算。由于并行一定程度必须被用来处理BigData，让我们先简要回顾一下已知的并行计算模型（[2]）。 最流行的并行模型是PRAM（PRAM模型）这是提出了20世纪70年代，但不幸的是一个通用的实用PRAM从未建，虽然最近有一些努力做到这一点[17]。另一方面，出现了大量的基于PRAM算法的研究，见[11，13]。但在PRAM算法理论和实践工作的系统之间的差距仍然巨大。见此差距，在20世纪90年代初，的LogP [3]和BSP（散装同步并行）模型[16]提出，在本质上有一个分布式的内存，整体异步并行机。在90年代初期，粗粒度多处理器（CGM），它可以被看作是和的LogP BSP的受限版本，提出了建议。总之，CGM是一组处理器中，每个有足够的本地存储器和足够的计算能力，并且该同步是通过点对点通信。事实上，两个实际系统，PVM-平行的虚拟机，和MPI消息传递接口，被实现并通过在并行计算的专业人员广泛使用。事实上，CGM算法两个特殊的问题已发表在科学期刊[5,6]。然而，CGM需要实时应用的高通信带宽和系统连接，因此，是不是太昂贵，或者不
是真正的实际应用的许多商业应用中，尤其是当数据量是巨大的，当一个全连接网络不能保证。
出人意料的是，主/从模式，calledMapReduce，于1990年底通过由谷歌，成为大规模网页搜索，几乎普遍[4]。的MapReduce的思想如下。 （1）主节点的地图和把一个任务分解成几个部分，并将它们分配给它的从属节点（图进程），以及（2）从节点完成子任务和主节点为结合返回结果进一步计算（缩小的过程）。注意，此过程可在多轮来完成，并可以递归进行，即，从节点可以进一步划分任务到一组子从节点。在这种模式下，通信只是一个主节点和它的奴隶之间，奴隶不能直接彼此通信。在图12.1，P1是从主节点节点P2; P3和P4;递归P4是P5和P6主节点。
一MapReduce的系统的最显著特性，从应用的角度来看，是可扩展性。即，当一个有一个额外的从属节点可用的（有一些相关的数据一起），很容易将其添加在现有下主，而不改变系统的总体拓扑结构。在图12.1，当节点P7加入作为下P4从属节点，所有其他节点，除了P4，不受影响。对于CGM，一会到新的节点之间加入了一个沟通渠道到所有的现有节点，这是更为昂贵实现。
它仍然告诉能做什么和不能使用的MapReduce高效地完成系统。 MapReduce的实际成功主要是搜索和查询侧（见[10]一个最近的调查）。有了这个动力，在2010年，卡洛夫，苏芮，并提出Vassilvitskii MapReduce的一个模型，它是基于模拟PRAM[12]的受限版本。在这种模式下，许多图问题可以有效地解决了[14]。然而，由于这种模式继承了一些PRAM的弊端，我们认为它可能是太强大（或实际成本太高），与任何现有的实际MapReduce的系统相比。
图12.1实际的MapReduce系统
图12.2主/从多处理器模式