基于bsp的大规模图处理系统中通信和缓存技术研究

《基于bsp的大规模图处理系统中通信和缓存技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文基于BSP的大规模图处理系统中通信和缓存技术研究作者姓名：白秋石指导教师：于戈教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机软件与理论论文提交日期：学位授予日期：评阅人：2012年6月鲍玉斌王溪波论文答辩日期：答辩委员会主席：东北大学2012年6月朱靖波万方数据AThesisinComputerSoftwareandTheoryResearchontheCommunicationandCacheTechniquesinBSP--BasedLargeScaleGraphPr

2、ocessingSystemsbyBaiQiushiSupervisor：ProfessorYuGeNortheasternUniversityJune2012㈣唱㈣盯㈣琢㈣删万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚的谢意。学位论文作者签名：伽髟BEt期：3D1)、6．D-学位论文版权使用授权书本学位论文作者和

3、指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：毛捅签字日期：如f2、6、纠两年∥导师签名：于弋签字日期：上3fZ．6·乞f万方数据东北大学硕士学位论文摘要基于BSP的大规模图处理系统中通信和缓存技术研究摘要随着计算机以及网络技术的发展，在计算机集群中采用并行的分布式计算方式提高计算处理能力已经

4、成为发展趋势。云计算(CloudComputing)的一个最主要的优势就是它的强大的并行计算处理能力，而这种能力是建立在一个简便高效的并行编程模型的基础上的。其中，最有代表性的就是Google提出的MapReduce分布式并行编程模型。然而，随着近年来互联网应用的迅猛发展，Web网络、社交网络等大规模网络图数据的分析处理成为了研究热点，例如社交网络中的最短路径、网页搜索的PageRank等。这些图处理问题通常需要多次迭代，而MapReduce适合于通用的大数据集计算问题，在处理具有多次迭代性质的图挖掘问题时会导致次优的性能。因而这些图算法

5、往往更适合于采用基于消息传递的并行模型来处理。BSP(BulkSynchronousParallel)整体同步并行模型就是一种支持消息传递的块内异步并行，块问显式同步的并行计算模型。随着Google基于BSP模型实现的大规模图处理系统Pregel的提出，在云环境中采用BSP模型实现大规模图处理系统成为了主要的解决途径。本文旨在以BSP模型为核，tl,，研究基于BSP模型的大规模图处理系统中的消息通信原理和磁盘缓存技术的设计方案及其实现等问题。提出了一种基于队列的消息组织方式和通信方案，并在此基础上提出了基于消息打包、多发送者线程池以及支持

6、消息合并的优化通信方案。针对基于BSP的大图处理系统可能存在的内存不足以存放计算中所有的图和消息数据的问题，本文建立了数据的内存管理模型，并基于内存优先(MemoryFirst)的思想，分别提出了图数据和消息数据的磁盘缓存策略及相应的算法：MF．GHIC算法、MLF图数据遍历算法和基于消息队列优先级的消息数据磁盘缓存算法等。将本文提出的通信和缓存技术应用于NEU．BSP系统中，我们通过实验，首先分析了通信方案中各类参数的较优值及其相互的制约关系；其次证明了在磁盘缓存率低于30％时，系统的时间性能下降并不显著；最后，我们以PageRank和

7、单源最短路径为例，通过与Hadoop系统的对比实验，证明了在数据完全驻留内存时，NEU．BSP系统比Hadoop系统快1．2到18倍，在数据超过30％以上缓存到磁盘时，NEU—BSP系统仍然能保持与Hadoop系统基本持平的时间性能。关键词：BSP；图处理；消息通信；磁盘缓存；云计算万方数据东北大学硕士学位论文AbstractResearchontheCommunicationandCacheTechniquesinBSP—BasedLargeScaleGraphProcessingSystemsAbstractWiththedevelo

8、pmentofcomputerandnetworktechnology,paralleldistributedcomputinginclustershasbecomethetrend．Them