图结构感知的图处理优化机制研究

发布时间：2021-06-15 11:05

　　随着大数据时代的来临,越来越多大数据应用需要以图的形式描述数据,进而通过迭代方式对其加以处理。如何高效利用图结构特性加速图处理,降低大规模图计算系统开销,成为图计算领域亟待解决的问题。然而,现有图处理系统对顶点活跃程度差异缺乏考虑,将活跃顶点（即热顶点）和非热顶点（即冷顶点）混合划分在同一分区,导致加载包含热顶点的分区时,增加不必要的冷顶点加载开销,延长图处理时间,降低图处理系统性能。针对上述缺陷,提出了图结构感知的图处理算法,并基于目前最先进的图处理系统Gemini实现了该算法（新系统为GGraph）。提出了图结构感知的图划分算法,该算法考虑了图结构的幂律特性,使用具有低开销的逻辑重划分方案,根据迭代过程中顶点间数据依赖的变化自适应划分冷/热图划分片（即含有大量热顶点的分区）,使得热顶点能够得到优先处理,同时降低冷顶点的计算频次,减少不必要的数据访问开销。为进一步提高收敛速度,还提出了基于热图划分片的调度算法,将热图划分片赋予更高的处理优先级,使得热顶点能够优先计算,并且得到足够的迭代处理次数,既减少了顶点收敛所需的更新轮次,又降低了每轮迭代所需的计算时间,加速图算法的收敛。实验结果... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：58 页

【学位级别】：硕士

【部分图文】：

点划分示意图

数顶点连接大部分边，点划，更新这些顶点时会产生跨部分的邻接顶点，对于这些低系统性能。图，该划分方式平均分配各个降低边跨越计算节点的数量结构和顶点间的依赖关系。中，边跨越多个分区。如图2， 5和 6被划分在分区 3，在低度数顶点较多的图中，消息的传播，降低跨节点通信

华 中 科 技 大 学 硕 士 学 位 论 文下，热顶点较多的计算节点需要更多时间遍历所有边，产生“木桶效的收敛时间。点边混合划分方式werLyra[11]提出了一种混合图划分方法 Hybrid-Cut，即对度数高的顶，对度数低的顶点采用边划分方式。如图 1.3 所示，Hybrid-Cut 图度数的不同选取差异化的处理策略，将度数较低的顶点（如 2， 3，放置在一起，以保证数据局部性，同时将度数较高的顶点（如 1），以充分利用图计算框架并行计算的能力。通过按顶点度数对顶点，Hybrid-Cut 算法在局部性和算法并行性上达到了较好的均衡。

【参考文献】：
期刊论文
[1]内存计算技术研究综述[J]. 罗乐,刘轶,钱德沛.  软件学报. 2016(08)
[2]从系统角度审视大图计算[J]. 吴城文,张广艳,郑纬民.  大数据. 2015(03)
[3]医疗健康大数据:应用实例与系统分析[J]. 董诚,林立,金海,廖小飞.  大数据. 2015(02)



本文编号：3230940