论文部分内容阅读
图结构具有很强的表达能力,现实世界中诸多实体以及实体之间的联系可以抽象成图中的顶点和边,通过分析图数据来挖掘有价值的信息,具有重要的现实意义。近几年来,图数据迅速增长,网页搜索、社交网络、生物信息等领域图建模早已达十亿甚至千亿规模。并且,图本身呈现的幂律分布和随机访问等特性,使得在图数据处理过程中很难利用时间和空间局部性。以上问题为设计高效的图计算框架带来了严峻挑战。单机图计算框架以其能够充分利用计算和存储资源、线程间通信更加高效以及编程简洁易懂等优势,逐渐成为研究热点。本文围绕图计算面临的诸多难题,针对单机上高效图计算框架的设计与实现开展了深入研究,主要工作和创新点如下:1.基于闪存的冗余阵列构建方法。闪存相对磁盘具有高带宽、低延迟、随机读写性能好等优势,为了进一步缩短与内存之间的性能差距,为图计算提供高速外部存储,我们探究了高速闪存阵列的构建方法。我们分别选用SATA和PCIe两种接口的固态盘,组成了RAIS0,5和6三种模式下的闪存阵列。然后,分析了队列深度和请求粒度对单块固态盘和闪存阵列性能发挥的影响,测试了挂载四种主流文件系统XFS、EXT4、F2FS和Btr FS后单盘和闪存阵列的性能表现差异。最后,总结了如何针对上层应用IO特性来构建高速闪存阵列以及优化IO的方法。2.基于NUMA架构的外存图计算框架HPGraph。目前服务器一般拥有多个处理器并以NUMA架构互联,处理器访问本地内存的性能要远远高于远端内存。因此,我们设计实现了一种适配NUMA架构的外存图计算框架HPGraph:针对NUMA特性的数据划分和访问模式能够尽量减少远端内存的访问;细粒度的edge＿block过滤策略,可以有效减少外存IO访问量;并且,使用work-stolen机制保证线程间负载均衡以充分利用处理器的计算资源。除此之外,我们构建了高速闪存阵列作为HPGraph的外部存储,进一步缩短图数据处理时间。大量实验表明,HPGraph相比于同类图计算框架GridGraph最高可获得约130%性能提升。3.基于众核处理器的内存图计算框架Ants。相对于多核处理器,众核处理器拥有更多的计算核心,能够提供更强的并行计算能力。同时,众核处理器上计算核心之间的网络互联更加复杂。在KNL服务器上,我们设计实现了基于众核处理器的内存图计算框架Ants,主要针对异构内存和cache-false sharing问题进行了一系列优化工作。实验表明,我们设计的数据划分机制能够很好的发挥异构内存各自的优势,任务调度策略有效降低了cache-false sharing问题导致的网络通信和内存访问开销。相比于同类计算框架Ligra,Ants取得了最高约9倍加速效果。更进一步,我们在多核服务器上验证了所提出的任务调度策略的适用性和有效性。4.基于内存的快速Truss分解算法pTD。Truss分解在图挖掘领域扮演着重要角色,通过对Truss分解步骤的深入分析,我们发现算法初始化阶段和分解阶段的三角形查找过程极为相似,基于此,提出了一种基于内存的快速Truss分解算法pTD。pTD将分解阶段的三角形查找上移来对图中每条边的support值进行初始化,同时保存查找结果供分解阶段使用,以此达到减少计算量、缩短处理时间的目的。由于中间结果数据规模较大,我们构建了高速闪存阵列作为外部存储,并使用计算IO重叠机制进一步降低外存IO开销。通过真实数据集上的测试,pTD相对于经典Truss分解算法最高能够取得约5倍的加速效果。