面向图计算的加速器的核心问题探讨

图计算的兴起及飞速发展很大程度上得益于图结构灵活的表达能力及其广阔的应用前景。随着图数据规模的持续性爆炸式增长，如何高效地处理大规模图数据成为大数据处理领域亟待解决的研究重点之一，这无疑对计算机体系结构的处理能力提出了更高的要求。这种要求不仅仅体现在计算性能上（如国际上每秒可遍历边数的专用排名Graph500），同时也体现在性能功耗比上（如国际上每瓦特可遍历边数的专用排名Green Graph500）。

以CPU为代表，遵循统一化设计理念、广泛通用于各类计算领域的传统处理架构在新的需求面前逐渐陷入困境。存在着并行效率低、访存随机性强、数据冲突频度高以及计算传输比低等突出问题为此，学术界和工业界涌现出了大量面向图计算的行编程范式、算法模型和处理框架等方面的研究这些系统软件层面的进展固然对解决上述通用处理架构中存在的问题起到了很好的缓解作用，但是图计算的性能仍普遍受制于底层处理架构。研究表明，即使综合运用目前先进的图计算优化技术并将贡献发挥到极致，图计算仍存在至少35%的性能损耗，这一损耗在处理稀疏型幂律图时尤为明显；更重要的是。由于图数据的频繁移动，功耗方面的表现更为糟糕。因此，开展处理架构创新驱动的“面向图计算的领域专用加速器研究”对提升图计算的处理能力有着颇为重要的现实意义。

真实世界的图数据大多数满足“小世界”和“幂律分布”的特点。前者的主要特征是任意两个顶点之间只需要通过少数的中介节点就能互相访问，从而使得图划分变得异常困难。后者的主要特征是拥有较高度数的顶点通常占比极少，绝大多数边主要集中在少数高度数顶点上，从而使得负载均衡对图计算而言显得尤为重要。

另一方面，图数据的处理算法多种多样，有以遍历为主的宽度优先搜索（Breadth First Search，BFS）算法，有以随机游走为主的网页排名（PageRank，PR）算法，也有以聚合操作为主的最小生成树（Minimum Spanning Tree， MST）算法。普遍来说，这些图算法均存在以下显著特征：计算访存比低，运行过程中伴随大量的随机访问行为，有较强的数据依赖等。

图数据结构和图算法在图计算过程中的深度交织，对主流的通用处理架构提出了严峻的挑战，具体有如下两个方面的问题。

1. 计算核心低效

以控制流为主的通用处理架构占据着传统体系结构的主流市场，其采用多核架构及多线程技术实现并行处理。以Intel x86处理架构为例，通用处理核心在图计算过程中通常表现出较低的IPC（Instruction per Cycle，每个时钟周期执行的指令数），一般在1.0以下，特别是对于访存密集型图算法，IPC其至会低于0.5。导致低效的IPC的主要因素有：

指令并行度低下：由于图较强的数据依赖和通用处理架构中指令流顺序回退（retire）串行语义的限制，导致指令并行度并不理想。首先，由于图数据依赖的存在，下一条指令的执行往往需要等待上一条指令的结果。导致指令执行过程中存在较多的等待延迟。其次，高并发图计算通常会存在多个线程对同一数据进行大量更新，为保证更新的正确性，通用架构引入了原子性保护，但牺牲了一定程度的性能。最后，图计算访存局部性差的特点使得数据缺失率较高，乱序（Out of Order，OOO）缓冲区则会迅速被指令流填满，使得后续指令产生停顿。

分支预测机制低效：传统处理架构通常采取指令预测的方式加速程序性能，预测失败时指令会被刷新，过多的失败预测会显著降低流水效率。图计算任务中存在大量的分支操作，考虑到访存的随机性和数据依赖的复杂性，很难正确预测分支条件。比如，点状态在每轮选代都会受到邻居的影响面可能不同，因此在判定点访问状态时，在大多数情况下分支预测机制会失败。

多核扩展性不强：大多数现实图通常呈现幂律分布，顶点的度数分布不均匀，在多核处理器架构中，负载不均衡通常会带来不可忽视的开销，与此同时，数据依赖也会进一步增加同步开销。因此，简单地通过增加处理核心数量的方法，很难有效地提升图计算性能，使得利用多核/多线程扩展技术提升图计算性能的效果并不理想。

2. 存储效率受限

除了计算核心的低效，图计算任务在传统通用处理架构上的访存效率也常常受限，具体表现为以下几个方面。

访存井行度低：访存并行度主要反映在对带宽的实际利用上。对图计算这类访存密集型应用，提升带宽的有效利用率能显著提升其性能。然而，受到现有存储架构下有限指令窗口大小的影响，图计算的访存并行度通常会受到限制。OOO核心中有限的MSHR（Miss Status Holding Register）数量也进一步限制了访存并行度的提升。此外，传统存储设备可提供的带宽通常也有限，例如单通道DDR4内存仅提供20GB/s的带宽，而图计算的带宽需求通常高达500GBs，这在很大程度上也限制了访存并行度的提升。

访存粒度固定：传统存储架构下，数据大多以固定粒度（例如，64字节单位）进行存储和访问，这带来了两方面的潜在问题。一方面，由于图数据的非结构化特点和随机访存特性，每次读取的数据量中通常会有较多的无效值，从而导致带宽的浪费。另一方面，为了掩盖访问延迟以充分利用带宽，需要大量的乱序访存请求，这往往远超出图计算的实际访存并行度。例如，对于延迟为90ns，带宽为64GB/s的DRAM，若访存粒度为64字节，则至少需要同时存在90个访存请求去充分利用所提供的内存带宽，远远超出图计算的实际访存并行度。

缓存机制低效：图计算访存局部性差的特点使得现有的层次化存储架构的访存效率低下。较高的缓存缺失率会增加访存延迟，同时增加对带宽的压力，计算资源在这种情况下也难以得到充分利用。针对图计算应用，采用传统技术手段提升缓存效率已然陷入困境。

通过对通用架构中计算核心和存储结构固有问题的分析，结合图计算的内在特征，可以看到传统体系结构的通用化统一设计已不再满足多样化大图数据处理的高效性诉求。为弥合现代体系结构通用性和图计算灵活定制需求之间的鸿沟，研制面向图计算的领域专用加速器（简称“图加速器”）为解决上述矛盾提供了方向。