英文文献译文.docx

《英文文献译文.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、英文文献译文第12章Bigdata的一种新的计算模型摘要：自从几年前BigData一直是一个热门词汇。但是，什么是完全对应的（理论值）的计算机模型？可以做些什么并且不能以这样的模式来完成？这些都要求答案的问题。最近，一个模型提出通过模拟受限制，以解决这个问题版本PRAM模型。在本文中，我们提出了所谓的理论模型主/从多处理器（MSM简称），这是非常类似于一个实际使用MapReduce的但有额外的限制有关BigData系统处理。此模型捕获一些最重要的属性的实用的粗粒度多处理器（CGM）模型（而不是PRAM）。该在这样的主/从模式最重要的思想是：（1）即使主只能在任何给定

2、访问所有的数据的一小部分在其从属处理器时间，（2）大量的从节点之间的数据传输的被认为是不可能或成本过高，和（3）一个额外的从属处理器，与数据一起它携带，可以很容易地集成到系统支持的可扩展性。在这样的一个模型捕获实际的MapReduce的最重要的特征系统，一些标准问题，如排序，成为难以解决的问题。然后，我们提出了一种自适应MSM模型，其中主节点仍具有有限的工作内存，但大中专storage.We演示如何这两款车型的MSM可以用来解决一些基本问题，当数据量是巨大的。12.1简介 自从几年前BigData一直是一个热门词汇。几乎在每一个行业，我们听说有人在谈论BigData

3、，一个突出的例子就是庞大的数据allWalmart交易量，或搜索查询谷歌已经处理，或视频监控系统监控所有的道路交叉口在纽约市，所有只是在一个单一的一天。在不同的国家资助机构设立研究项目针对不同地区处理BigData。总之，BigData在那里并且将改变我们lives.We需要正确地处理它们，如果没有，它们将变得我们的负担。尽管如此，似乎不存在一个普遍接受的模型BigData计算。由于并行一定程度必须被用来处理BigData，让我们先简要回顾一下已知的并行计算模型（[2]）。最流行的并行模型是PRAM（PRAM模型）这是提出了20世纪70年代，但不幸的是一个通用的实用

4、PRAM从未建，虽然最近有一些努力做到这一点[17]。另一方面，出现了大量的基于PRAM算法的研究，见[11，13]。但在PRAM算法理论和实践工作的系统之间的差距仍然巨大。见此差距，在20世纪90年代初，的LogP[3]和BSP（散装同步并行）模型[16]提出，在本质上有一个分布式的内存，整体异步并行机。在90年代初期，粗粒度多处理器（CGM），它可以被看作是和的LogPBSP的受限版本，提出了建议。总之，CGM是一组处理器中，每个有足够的本地存储器和足够的计算能力，并且该同步是通过点对点通信。事实上，两个实际系统，PVM-平行的虚拟机，和MPI消息传递接口，被实

5、现并通过在并行计算的专业人员广泛使用。事实上，CGM算法两个特殊的问题已发表在科学期刊[5,6]。然而，CGM需要实时应用的高通信带宽和系统连接，因此，是不是太昂贵，或者不是真正的实际应用的许多商业应用中，尤其是当数据量是巨大的，当一个全连接网络不能保证。出人意料的是，主/从模式，calledMapReduce，于1990年底通过由谷歌，成为大规模网页搜索，几乎普遍[4]。的MapReduce的思想如下。（1）主节点的地图和把一个任务分解成几个部分，并将它们分配给它的从属节点（图进程），以及（2）从节点完成子任务和主节点为结合返回结果进一步计算（缩小的过程）。注意，

6、此过程可在多轮来完成，并可以递归进行，即，从节点可以进一步划分任务到一组子从节点。在这种模式下，通信只是一个主节点和它的奴隶之间，奴隶不能直接彼此通信。在图12.1，P1是从主节点节点P2;P3和P4;递归P4是P5和P6主节点。一MapReduce的系统的最显著特性，从应用的角度来看，是可扩展性。即，当一个有一个额外的从属节点可用的（有一些相关的数据一起），很容易将其添加在现有下主，而不改变系统的总体拓扑结构。在图12.1，当节点P7加入作为下P4从属节点，所有其他节点，除了P4，不受影响。对于CGM，一会到新的节点之间加入了一个沟通渠道到所有的现有节点，这是更为

7、昂贵实现。它仍然告诉能做什么和不能使用的MapReduce高效地完成系统。MapReduce的实际成功主要是搜索和查询侧（见[10]一个最近的调查）。有了这个动力，在2010年，卡洛夫，苏芮，并提出VassilvitskiiMapReduce的一个模型，它是基于模拟PRAM[12]的受限版本。在这种模式下，许多图问题可以有效地解决了[14]。然而，由于这种模式继承了一些PRAM的弊端，我们认为它可能是太强大（或实际成本太高），与任何现有的实际MapReduce的系统相比。图12.1实际的MapReduce系统图12.2主/从多处理器模式打算，而不是PRAM以获得