第6章   图计算

6.5 图计算硬件加速技术

加速器因具备丰富的带宽资源、超高的并行能力及极低的数据传输延迟等技术优势，是实现高效图计算的重要技术手段之一。按照加速器物理器件性质来看，现有的面向图计算的硬件加速方案大致可分为基于GPU的图计算加速器、基于MIC的图计算加速器、基于FPGA的图计算加速器、以及基于ASIC（Application Specific Integrated Circuit）的图计算加速器等。

6.5.1 基于GPU的图计算加速技术

与CPU相比，GPU因集成众多计算单元，可提供更强的并行计算能力，以更高效地支撑大规模图顶点遍历与更新。图 6-5-1描述了NVIDIA Tesla P100[21]的结构图。每个GPU内部包含多个流处理器（Streaming Multiprocessor），流处理器共享全局存储单元，同时每个流处理器都有各自的私有缓存。流处理器内部含有多个线程单元，连续固定长度（一般为32）线程为一个调度基本单位，通常称为一个线程warp，warp内部线程执行SIMD（Single Instruction Multiple Data）计算模型。每个流处理器上可以同时执行多个线程warp，连续一定数量warp称为一个CTA（Compute Thread Array）,GPU对流处理器进行任务分发的基本粒度为CTA，同一个CTA内部可以通过共享存储器进行通信。一方面，通过多级粒度的任务并发，GPU可以实现超高的计算并行度，同时具备不同粒度的任务调度。另一方面，GPU内部有多个内存控制器，通过并发线程可以满足高带宽的要求。例如Tesla P100具有3584个处理单元，其内部带宽可以高达732GB/s。

图6.36

图 6-5-1  NVIDIA Tesla P100结构图

图计算具有高并发的特点，无论是vertex-centric或者edge-centric编程模型都隐藏着大量数据并行语义，可以使用GPU进行并行加速，且图计算是一种数据密集型应用，GPU高达上百GB/s的带宽相对于CPU也具有明显的优势，因此单位时间内可传输的数据更多，并充分利用GPU单指令多数据（Single Instruction Multiple Data，SIMD）并行优势进行加速，例如，可对大量的边数据同时进行更新，但基于GPU的图计算加速技术也存在着明显的挑战，主要包括以下几点：

1、 SIMD计算模型中同一个线程warp共享同一指令流，未分到任务的线程会空转等待，为了保证计算资源的充分利用，每个线程的任务应尽量均衡，而图数据往往具备一定的倾斜（power-law）特性，即少部分点拥有绝大部分边，如何划分计算任务保证负载均衡，是基于GPU图计算急需解决的首要问题。

2、 GPU内部带宽通常高达上百GB/s，这主要得益于GPU的超高位宽（例如，Tesla P100的带宽可以达到732GB/s，位宽也可达到4096 bit）。为了充分利用带宽资源，需尽可能提高每次取出数据的利用率。由于图结构的稀疏特性，每个点的邻居节点具有分布较为随机，进而导致取出数据的带宽利用率效果不佳。如何有效提高GPU的带宽利用率是基于GPU的图计算加速需要考虑的重要问题。

3、 GPU全局内存器容量可达几GB到十几GB，而工业数据集往往具备上百GB甚至更大规模，为了处理大规模图数据，常用策略是将图数据划分为子图，然后选择性地对子图进行调度处理。这种场景需要尽可能地减少数据的移动开销并且重叠计算和通信，从而达到较好的性能。

为了应对基于GPU图计算负载不均衡的问题，Back40Computing[22]（以下简称B40C）实现了基于GPU的高性能遍历算法。如图 6-5-2所示，B40C采用了scan+warp+CTA的任务划分策略，较好地解决了vertex-centric编程模型下GPU图处理的负载均衡问题。具体来说，根据度数规模，将图顶点划分为三类，对于高度数顶点和中度数顶点，分别采用CTA协作和warp协作的方式调度多个线程进行处理。对于小度数顶点，首先采用前缀和计算每个线程需要计算的任务区间，再进行任务的调度。这种混合调度策略能解决同一个warp中不同线程以及同一个CTA中不同warp的负载不均问题。此外，为了进一步减少全局访存，B40C实现了基于位掩码（bitmask）的状态记录，首先对缓存状态结构进行监测，仅在不满足条件时才进行全局结构查找，这种策略可明显减少图计算过程中的全局访存量，从而提高系统性能。

图 6-5-2  B40C scan+warp+CTA负载均衡策略

Gunrock[23]进一步设计了基于GPU的图计算通用加速库，如图 6-5-3所示，评测结果显示，相较于基于CPU的经典图处理框架，Gunrock在性能上可高出至少一个数量级。Gunrock提出基于活跃数据集合的编程抽象，框架维护一个活跃节点集合，每轮迭代过程中，根据活跃节点以与图拓扑结果，通过Advance（类似于Expand）操作，然后经过Filter操作（去除重复节点）可以得到下一个活跃节点集合。通过Gunrock设计的通用API，开发人员可以基于GPU实现更加复杂的图算法。

图 6-5-3  Gunrock data-centric编程模型

除此之外，Gunrock设计并封装了基于GPU的常用图优化技术。例如，针对负载均衡问题，采用了类似于B40C的线程细粒度调度和基于warp/CTA的混合调度策略，以实现不同粒度间的计算任务负载均衡。针对访存带宽问题，采用了CSR和Edge list的混合数据结构提高聚合访存的效率，对点操作采用CSR结构，对边操作采用Edge list访问，最大程度上减少了乱序访存带来的额外开销。针对不同的图应用特征，Gunrock还提供了一些特定的优化接口，如SSSP的优先调度、 BFS的Push/Pull切换调度等。

为了进一步提升GPU带宽利用率，Graphie[24]针对大规模图数据的处理调度进行了优化。为了充分提高GPU的聚合访存性能，Graphie采用了分类边表（sorted edge list）的方式进行数据存储，但现有的edge list仍然存在聚合访存效率不高的问题，这主要是因为原始图数据集中部分节点未含有出边，从而导致边表结构存在空缺项。如图6.39所示，顶点3和顶点4无出边，其边表对应的结构则无顶点3和顶点4，使得GPU在访问顶点相应点数据时，顶点数据不连续所导致的带宽资源浪费。为此，Graphie提出了一种重编码图结构，将无出度的顶点编号放置编号集的尾部，这样可保证所有源点集合访问的连续性，从而提高图计算的聚合访存效率。Graphie支持GPU的大图处理，将边表分为固定大小的数据块，将活跃点数据块传输到GPU进行处理，为方便记录每个数据块中是否存在活跃节点，如图 6-5-4所示，通过插入虚拟顶点，Graphie保证每个数据块起点的连续性且范围长度相同。

图 6-5-4  Graphie重命名算法规则

6.5.2 基于MIC的图计算加速技术

Intel Xen Phi[25]（简称MIC众核处理器）的结构如图 6-5-5所示，与GPU结构类似，MIC构架是一种支持一致性内存访问的对称多处理器结构。MIC的多个处理核之间通过环形双向总线进行核间通信。每个处理核配置相应容量的一级缓存和二级缓存，同时每个处理核拥有一个标量处理单元和一个向量处理单元，向量处理单元拥有长度为512位的SIMD处理能力。MIC构架的优势在于,能提供与GPU类似的SIMD性能加速能力的同时，仍可较好地支持OpenMP、MPI、Intel TBB、Cilk等多核处理器的编程环境，具备很好的代码可移植性。

图 6-5-5  Intel Xen Phi结构图

由于MIC构架与GPU构架同是基于SIMD技术进行加速，且均具有很高的带宽，因此其面临的问题与GPU类似。与GPU不同的是，MIC所采用的是X86指令集，这意味着能够运行在Intel CPU平台的代码也能运行在MIC平台上，具有天然的异构计算优势。

MOSAIC[26]是基于CPU+MIC异构平台实现的核外图处理框架，其采用的设计思路是将图数据切分成固定大小（称为tile）,然后每个tile内部的数据在MIC协处理器端进行局部加速归约，对归约得到的结果在CPU端进行全局归约，同时协处理器的计算任务和主机端任务能较好的流水化，充分利用二者的计算能力。由于tile本身是一种边表结构，因此可以较好地利用带宽资源。有趣的是，如图 6-5-6，MOSAIC采用了一种希尔伯特顺序化对原始图数据进行预处理，这种特定的顺序化能够较好地提高数据的局部性与复用率，这对充分消化MIC的计算能力和减少I/O传输量都能起到明显的作用，实验表明，最高可以减少68%数据传输量。此外，MOSAIC修改了文件系统，并采用NVMe驱动，因此可以支持MIC和NVMe之间直接的数据拷贝，避免了通过CPU的中转开销。

图 6-5-6  MOSAIC基于希尔伯特曲线的数据划分策略

6.5.3 基于FPGA的图计算加速技术

现有研究表明，内存访问延迟过高、并行度不足等问题导致传统CPU架构在处理图应用时往往面临着严重的性能与能源损耗[27][28]。FPGA作为一种介于通用芯片（如CPU，GPU）与定制化芯片（ASIC）之间的计算平台，一方面，提供了大量的计算资源以保证较高的并行度，另一方面，提供了较好的可重构性以保证较低的能源损耗。因此，大量研究人员与机构开始尝试使用FPGA解决传统架构中存在的问题。

由于图应用的数据局部性差和访存随机性大的特点，因而其访存延迟通常明显大于传统应用。针对图计算访存延迟高的问题，现有基于FPGA的图计算工作在执行模型和数据划分等方面开展了大量工作。

在执行模型方面，现有的FPGA工作多数基于Edge-centric模型[6]以提升边数据访问的局部性[2][29][30]。如图 6-5-7（b）所示，传统的Vertex-centric模型[2]遵循着“源点—源点出边—目标点”的访问模式。由于在图计算中源点编号的非连续性，因此，源点出边与目标点的访问通常亦非连续，从而导致了较差的局部性。如图 6-5-7（c）所示，相比于Vertex-centric模型，Edge-centric模型遵循着“边—边的源点—边的目标点”的访问模型。通过流式（streaming）处理边的方式保证了边数据访问的局部性，从而降低边数据的访问延迟。

图 6-5-7  Vertex-Centric模型与Edge-Centric模型

在数据划分方面，传统的划分方法以等分方式所有边数据以同等计算量为尺度进行划分。这种方法可以一定程度上保证较好的负载均衡，却加剧了各划分内点数据访问的随机性。因此现有工作通常采用网格划分（grid-partition）的方式提升点数据访问的局部性[29]。如图 6-5-8所示，该方法以等分的方式将所有点数据划分为N个区间（I1，I2，…，IN），然后将所有边数据划分为N*N个网格（G1,1，G1,2，…，GN,N）。其中网格，即Gi,j中包含所有源点在Ii和目标点在Ij的边。网格划分方式的优势在于，当流式处理每一个网格内的边数据时，由于源点和目标点的编号范围确定，点数据访问的随机性可以得到有效地降低。此外，可以采用预取的方式将这些点数据缓存在片上内存（on-chip memory）内，进一步降低点数据访问的延迟。

图 6-5-8  网格划分

通过在执行模型与数据划分等方面的优化技术，现有的FPGA工作有效缓解了图计算在传统架构下访存延迟过高的问题。而针对并行度不足的问题，现有工作通常通过在片上提供大量的处理单元的方式以利用图计算中潜在的并行性[29][30]。如图 6-5-9（a）所示的FPGA工作为网格划分中的每一个网格均分配了一个独立的处理单元为了避免图 6-5-9（b）所示的由数据竞争造成的计算资源的浪费，现有工作在任务分配时加入了洗牌（shuffling）机制[29]。如图 6-5-9（c）所示，该机制在分配任务时会优先分配分属不同网格的边数据，避免计算资源的空闲，从而降低总体的计算时间。

图 6-5-9 洗牌机制

6.5.4 基于ASIC的图计算加速技术

与采用FPGA平台的动机类似，传统CPU架构在处理图应用时面临着访存延迟较高与并行度较低等问题。尽管现有的图计算系统能在一定程度上缓解上述问题，其性能与性能功耗比依旧受限于顶层的硬件架构。因此，许多研究人员与机构开始尝试为图计算设计专用加速芯片（ASIC）。

通用处理器架构（CPU）在处理图应用时，往往面临着以下问题：1）低效的访存粒度浪费了大量内存带宽，例如，CPU一次访存会读取或存入一个大小为64Byte的Cacheline数据，由于图计算较差的局部性，这些数据中往往只有很小一部分是有效数据；2）低效的片上缓存架构，现有Cache架构仅仅适用于局部性较好的应用；3）低效的计算粒度，现有CPU遵循传统指令流架构，在处理图计算时往往指令效率较低；4）较低的内存级并行度，内存带宽难以得到充分的利用。为了解决上述问题，现有工作从缓存设计、流水线设计、并行架构设计等方面对图计算性能进行优化。

在缓存设计方面，普林斯顿大学提出的Graphicionado[32]从专用化的角度出发，使用了高速暂存存储器（scratchpad memory）来替代传统的Cache架构。与传统的Cache架构不同，Graphicionado使用的缓存架构与内存之间没有直接的映射关系，因而也不存在Cache命中检测、数据块实时替换等操作。Graphicionado将待处理的图按目标点排序的方式进行划分，并保证每个划分内所有的点数据均可存放于片上缓存中。当且仅当当前划分被处理完毕时，片上缓存的数据才被写回并替换为下一待处理划分。一方面，通过将点数据访问转移至片上缓存，Graphicionado显著提升了顶点数据的访存精度，有效减少了内存带宽的浪费；另一方面，通过这种静态替换的方式，Graphicionado有效缓解了数据块频繁替换问题，显著降低了访存延迟。

针对片上缓存架构，如图 6-5-10所示，比尔肯大学从细分化角度对传统Cache架构进行改进[33]。相较传统Cache架构无差别地处理所有种类的数据，往往面临数据频繁冲刷Cache导致命中率下降的问题，该架构对图应用中所有的数据进行细粒度的划分，将传统的Uniform Cache细分为多个子Cache以保存不同类型的图数据。

图 6-5-10 细分化Cache架构

在流水线设计方面，Graphicionado以GraphMat[34]的编程模型为基础，针对图计算设计了专用的流水线架构。如图 6-5-11所示，Graphicionado摒弃了传统Instruction-Set-Architecture的方式，将图计算中所有的计算操作抽象为加速器中的执行模块，整个流水线架构分为处理阶段和应用阶段。在处理阶段，流水线依次完成源点数据读取、边数据读取、目标点数据读取、边计算、原子更新等操作。Graphicionado通过将所有活跃点依次送入流水线处理阶段来完成图计算中一次迭代的所有计算。在应用阶段，流水线一次完成旧点数据读取、新点数据读取、点数据比较、更新等操作。Graphicionado在一次迭代计算完成后，通过调用应用阶段流水线以将新的点数据写回内存并生成下一轮迭代的活跃点集合通过将图计算流水化的方式。Graphicionado有效减少了传统ISA中取值与译码的开销，从而提升整体的指令效率。

图 6-5-11  Graphicionado流水架构

在并行架构设计方面，Graphicionado通过增加流水线的方式实现访存的并行化（如图 6-5-12所示）。虽然这种方式在软件架构中实现较为简单，但在实际的硬件设计中却容易带来较大的性能损失。例如，当不同流水线同时需要写或者读取同一个数据时，为了保证计算的准确性，这些操作往往需要强制串行化从而降低整体的计算性能。为此，在设计并行架构时，Graphicionado将执行阶段的流水线拆分为源点与目标点相关的模块。如图 6-5-12所示，假定流水线个数为n，则源点相关的模块中的流水线i仅处理编号中最后log2(n)位为i的源点。目标点相关模块中的流水线与之同理。通过这种任务划分机制，可避免多条流水线同时访问同一点数据的情况，从而有效地提升内存级并行度。

图 6-5-12  Graphicionado并行架构