论文部分内容阅读
现如今图计算应用的领域非常广泛，如社交网络、物联网和神经网络等，常见的图计算系统分为单机图计算系统和分布式图计算系统。分布式图计算系统有负载不均衡、昂贵的通信开销以及弱健壮性等缺点，同时在大规模图的处理问题上，最近的研究结果表明单机图计算系统和分布式图计算系统具有同样高的竞争力。因此，单机图计算系统正成为图计算研究领域的重点。 GraphDse是一个基于外存的单机图计算系统，GraphDse图处理过程分为两个阶段：预处理阶段和更新阶段。在预处理阶段，GraphDse提出了基于目的顶点均匀分割的结构（Destination-Average Shard，DAS）和基于源顶点均匀分割的结构（Source-Average Shard，SAS）来存储图数据，保证了图数据的局部性和提高了CPU的运行效率。在更新阶段，GraphDse提出了双滑动边（Double Sliding Edges，DSE）的计算模型，避免了同步锁或者原子操作带来的系统开销，实现了很高的并行度。在迭代过程中将顶点存储在内存中，减少了在外存上对图顶点的读写操作，减少了大量的I/O数量。针对不同类的图应用提出了灵活的选择调度策略，可以跳过一条边的计算甚至一个分片的加载和计算，减少了I/O数量和提高了图算法收敛速度。 在真实世界的自然图数据和合成的图数据上运行图应用（PageRank、BFS和WCC）来进行大量的实验。和目前主流的图计算系统GridGraph相比，实验证明GraphDse可以显著地提高性能。在预处理阶段，GraphDse性能最高提升了60.1%。在更新阶段，对于PageRank应用，GraphDse系统性能最高提升了83.0%；对于BFS应用，GraphDse系统性能最高提升了44.4%；对于WCC应用，GraphDse系统性能最高提升了86.6%。