基于拓扑重构的分布式图计算关键技术研究

发布时间：2021-06-29 14:26

　　随着信息技术的飞速发展,网页检索、社交网络、生物信息科学等领域所涉及的图论知识和算法得到了广泛应用和发展。自然生成的图数据规模呈现了爆炸式的增长,让分布式图计算这一领域成为了学术界和工业界的热门研究方向。而对于大规模图数据进行合理的划分与存储,能够减少机器节点间的通信量,是提升分布式图计算性能的研究热点之一。此外,分布式图计算系统在实现分布式计算模型时的实现方式,往往会存在着冗余计算或冗余通信的问题。因此,分布式计算模型的优化及实现,也是分布式图计算系统性能优化的关键性问题。本文深入研究了分布式图数据划分和分布式图计算模型,探讨了分布式图计算系统性能优化技术,重点围绕基于拓扑重构的分布式图分割算法和基于增量变化的GAS分布式计算模型展开了深入研究。本文的主要研究工作包括:一、深入研究并分析了分布式图计算已有的图数据划分算法,在分析其研究成果的优势时,也揭示了其各自的局限性;深入分析了现有的分布式图计算模型及其在实际分布式图计算系统的实现,发现其存在的优点和需要改进的方向。二、针对大规模图计算的低效分区问题,提出了基于拓扑重构的分布式图分割算法。通过对自然生成的图数据进行分析发现,自然图... 

【文章来源】：国防科技大学湖南省 211工程院校 985工程院校

【文章页数】：64 页

【学位级别】：硕士

【部分图文】：

云计算体系结构图

图 2.1 BSP 模型处理过程图 BSP 作业由 N 个顺序执行的超步（superstep）组成，来对应于行任务按照超步组织，在超步 Si内，各任务异步接受来自 Si-1的算并发送消息给下一个超步 Si+1。每次迭代处理的超步包含上图本地计算、全局通信、栅栏同步。地计算阶段：每个处理器进行独立的计算，处理器计算都利用理器间没有任何联系，不进行通信，独自完成相应的计算。局通信阶段：当所有的处理器完成局部计算之后，所有的信息块进行传输，该阶段没有任何计算操作。栏同步阶段：由于处理器性能差异或每个处理器需要处理数据部计算出现完成时间不一致，有的处理器可能很早就完成计算慢的节点，在通过全局通信阶段之后，数据到达栅栏同步阶段将所有的等待进行同步，可以避免因异步计算导致的死锁问题成标识该次超步结束，可以进行下次超步。步之间，通过显式地同步控制，确保所有任务均已完成超步 Si

国防科学技术大学研究生院硕士学位论文（例如边<D，B>）成为超点 A'的邻边（<D，A'>）。在图 3.2(b)中描绘了最终的拓扑结构，其中超点 A'由 A 和它的 1 跳/2 跳低度邻点组成。超点仍然被认为是低度的，并且它们的边被分配到目的点。例如，<D，A'>和<A'，E>分别与 A'和 E 一起分配。


本文编号：3256606