论文部分内容阅读
图是一种很重要的非结构化数据,可以用于建模现实世界中的各种问题,被广泛应用到交通运输、金融、社交网络等重要领域。但由于图计算过程中严重的结构依赖性,导致应用执行时内存随机访问严重,内存带宽成为限制图计算系统性能的重要因素。并且不同类型图算法的内存访问特征差异明显,单一的内存图数据组织不足以应对各种图算法多样化的内存访问需求。针对上述问题,分析了常见图算法的动态运行特征和内存数据访问特点,将图算法分为遍历式和迭代式两类,研究不同运行特征下的高效的图数据组织策略。对于遍历式图算法,通过分析其运行过程,发现同一个顶点和不同邻居节点之间存在关联度的大小差异,对邻居节点的访问顺序是影响算法运行过程中缓存命中率的重要因素。基于此提出了基于关联度的图顶点重映射算法GDL-VC,并采用滑动窗口模型SW实现了内存图数据的合理布局。该布局结果能够体现出图的结构特性,使相关联的顶点ID分布呈现局部有序,减少图算法运行过程中的内存随机访问。对于迭代式图算法,通过分析其算法收敛特性,发现图结构中“超级顶点”长时间不能达到收敛状态而造成了迭代式图应用的长尾现象。针对于此,提出了基于影响力的图顶点重映射算法GDL-DR,该布局算法根据顶点的影响力(顶点度)完成图数据的布局。这样在图算法迭代后期,活跃顶点集执行状态更新时,与之相关联的邻居节点紧凑分布,可以减少内存随机访问,使顶点更快的达到收敛状态,缩短应用执行时间。测试结果表明:GDL-VC布局算法能够给遍历式图应用(连通分量、单源点最短路径)带来25.4%、27.5%的平均内存访问效率提升,部分数据集超过50%;GDL-DR布局算法能够给迭代式图应用(网页排名、标签传播)带来23.9%、17.1%的平均内存访问效率提升,最大提升百分比为42.9%。对于GraphChi测试平台,两种布局算法带来的系统加速比均达到1.5×以上,部分图数据超过2×;Cache命中率提高到90%以上。