【博士论文】高性能并发图计算优化技术研究

图能够方便地表达事物之间的关联关系，因而广泛应用于现实生活中的诸多应 用场景，例如社交网络图、电路图和电商交易图，为图计算赋能数据挖掘和分析提 供基础。由于图计算的重要性和普遍性，同一图计算平台上通常并行运行着大量图 算法（以下简称并发图计算任务），为不同的应用或者用户提供高性能的图计算能力 支撑。除了与传统图计算任务相同的计算特征外，并发图计算任务还存在着严重的 资源竞争、数据竞争等新型挑战，任务并发度和总体性能较低。为此，如何设计面 向并发图计算任务的高性能执行环境，快速挖掘出海量图数据中潜在的各种商业或 科学价值，已成为目前亟需解决的问题。为了高效支持图计算任务的执行，目前国内外学者已经从面向图计算的体系结 构和系统软件等方面开展了广泛的研究。然而，现有图计算硬件加速器和软件系统 无法充分感知不同图计算任务之间的运行时特征，例如潜在的数据局部性和通信行 为相似性等。现有方案在支持并发图计算任务时面临着数据访问行为不规则、冗余 访存开销大以及通信效率低等问题，导致严重的数据访问瓶颈和底层硬件资源的低 效利用。为了解决并发图计算任务面临的挑战，分别从体系结构层面和系统软件层 面开展研究来实现高性能并发图计算技术，有效支持并发图计算任务的执行。针对并发图计算任务数据访问行为不规则问题，提出了以数据局部性为中心的 并发图计算硬件加速技术，以提高并发图计算任务的访存效率。分析发现，由于不 同图计算任务往往沿着同一图拓扑来遍历相同图数据，这些任务之间存在极强的数 据局部性。基于此发现，该硬件加速技术首先动态探索并发图计算任务活跃图顶点 之间的依赖关系，使并发图计算任务沿着图拓扑遍历和处理相同图数据，以此来规 则化并发图计算任务的图遍历行为。其次，该硬件加速技术对并发图计算任务的图 顶点访问进行高效合并，从而提高顶点访问的局部性。实验结果表明，与现有图计 算硬件加速技术 HATS、Minnow 和 PHI 相比，本设计能够获得最高 11.3 倍的加速比。针对并发图计算任务冗余访存开销大问题，提出基于细粒度同步的核外并发图 计算技术。该技术首先提出了一种面向并发图计算任务的细粒度同步执行机制，使得只需在缓存和内存中加载和存储相同图结构数据的一个副本就能服务多个并发图 计算任务，从而降低图数据的冗余访存成本，提高底层硬件资源的利用率。其次， 提出了图结构感知的数据重划分和缓存机制，通过自适应地加载并发图计算任务所 需的图数据，并将频繁使用的图数据缓存在主存中，提高加载图数据利用率和最小 化 I/O 开销。实验结果表明，所提出的核外并发图计算技术，能够将现有图计算系统 GridGraph、GraphChi 和 X-Stream 的并发图计算任务吞吐率最高提升 13 倍。针对并发图计算任务在分布式环境下扩展性差的问题，提出了相似性感知的分 布式并发图计算技术。分析发现，并发图计算任务之间的通信行为存在极强的相似 性。基于此发现，首先提出了相似性感知的分布式并发图计算执行机制，其沿着图 划分块之间的拓扑关系来加载图数据，并以此高效驱动分布式平台中每个计算节点 上的任务执行，从而使得加载的图数据能够被更多任务共享；通过高效的通信机制 来使得不同任务的通信行为以规则的方式批量进行，从而降低并发图计算任务的通 信成本，提高通信效率。其次，提出了面向并发图计算任务的增量负载均衡机制和 面向动态图处理的数据存储优化机制，以此来提高分布式计算资源利用率和保证在 支持动态图处理时的执行效率。实验结果表明，与分布式图计算系统 Gemini 和 Seraph 相比，本设计在支持并发图计算任务时能够获得最高 6 倍的加速比。总的来说，本文分别研究了并发图计算任务不规则访存行为与底层体系结构不 匹配问题、并发图计算任务之间冗余数据访存开销高问题以及分布式并发图计算扩 展性差问题，围绕体系结构、单机和分布式系统软件层面实现高性能并发图计算技 术，显著提升并发图计算任务的执行性能。