0.Abstract
图是许多实际计算应用程序的关键数据结构之一，图分析的重要性日益增长。虽然现有的软件图处理框架提高了图分析的可编程性，但底层通用处理器仍然限制了图分析的性能和能效。我们构建了一个特定于领域的加速器 Graphicionado，用于图分析工作负载的高性能、节能处理。为了高效的图分析处理，Graphicionado不仅利用了以数据结构为中心的数据路径专门化，还利用了内存子系统专门化，同时充分利用了该领域固有的并行性。Graphicionado增强了顶点编程范式，允许将不同的图分析应用程序映射到同一加速器框架，同时通过一组小的可重构块保持灵活性。本文详细描述了 Graphicionado流水线设计的选择，并深入探讨了 Graphicionado如何解决通用CPU上应用程序执行效率低下的问题。我们的研究结果表明，与在16核 Haswell Xeon 处理器上执行32个线程的最先进的软件图形分析处理框架相比，Graphicionado 获得了1.76 -6.54倍的加速比，同时少消耗了50-100倍的能量。
1.介绍
18世纪早期，图论和拓扑学作为一种娱乐数学谜题被称为“ K onigsberg 桥问题”，后来发展成为众所周知的多对多关系的表示，解决了网络通信、社会资讯、自然语言处理、系统生物学和网络安全等领域的研究问题。在生产和消费“大数据”的时代，人们对开发图分析应用程序以获得新的解决方案和见解的兴趣重新高涨; 例如，谷歌的PageRank [30] ，Facebook 的语义搜索引擎，图搜索[44] ，Ayasdi的拓扑数据分析引擎，该引擎帮助科学家进行更有效的乳腺癌治疗[15] ，以及 MITRE 的网络战分析管理软件CyGraph [48] ，该软件将入侵警报与已知的漏洞路径相关联。这种新的兴趣促使软件社区开发更有效的图分析处理框架[4,5,23,25,33,35,46]以及硬件社区，以创建能够以比现成的通用处理器和系统更高的效率执行图分析应用程序的硬件[11]。为此，我们的研究重点是利用图分析应用程序表现出的结构化数据移动和计算模式来提高效率，并缓解此类应用程序在传统CPU上执行时面临的挑战。
在考虑图领域加速器时，必须考虑某些关键特性。首先，图分析应用程序通常受到内存延迟或带宽限制。例如，相对于少量计算，图遍历通常需要许多内存访问。不幸的是，当前的通用处理器不是执行此类应用程序的理想平台。它们的低效性包括1）由于低效的内存访问粒度而浪费了片外内存带宽—在只操作一部分数据(例如4字节)的情况下加载和存储64字节的缓存数据;2）低效的片内内存使用率—硬件缓存不受图特定数据类型的影响，并且不能有效地在片上保留高局部性数据，3）执行粒度上的不匹配ーー使用 x86指令计算和通信数据，而不是利用特定领域的数据类型进行图分析，例如边和顶点。为了克服这些限制，除了利用图工作负载的固有并行性来缓解这些性能瓶颈外，我们还提出了一组数据类型和内存子系统专门化。
我们构建、设计和评估用于处理图分析工作负载的特定于领域的加速器。Graphicionado的灵感来自于顶点编程范型和一些可重新配置的块，这种特殊而灵活的pipeline意味着图分析应用程序（作为顶点程序编写）将在Graphiciando上运行良好。
本文做出了以下贡献：
- 一个专门的图分析处理硬件管道，它采用数据类型和内存子系统的特殊化，同时提供称为Graphiciando的特定于工作负载的可重构块。
- 深入了解各种微体系结构优化，以提供性能和能效，提取更多并行性的技术，以及支持使用切片和分区的大规模真实图形的策略。
2.背景动机
2.1 软件图处理框架
软件图处理框架通常旨在为用户提供三个方面：易于编程、提高性能和有效的可扩展性，从而允许工作负载扩展。为了提高图算法的可编程性，人们提出了不同的编程模型。例如，顶点编程[4、33、35、46]、稀疏矩阵运算[8]、图域特定语言[18]和基于任务的模型[23]。此外，软件框架在性能和可扩展性方面也存在很大差异，尤其是与本地应用程序相比[43]。
在图框架的各种编程接口中，最流行的是顶点编程。在该模型中，整个算法可以表示为对单个顶点及其边的操作。这种编程模型通常被认为易于使用且没有过度限制，但在实践中实现性能可能会有很大差异。GraphMat[46]已被证明在单个节点上的许多不同软件图形框架中具有最佳性能。虽然每个基于顶点编程的图框架的确切编程API略有不同，但它们都具有相似的结构。
图1显示了使用三个基本算子的顶点编程示例：Process_Edge、Reduce和Apply。在顶点程序中，每个顶点都有一个迭代更新的特定于应用程序的顶点属性。在每次迭代中，检查每个顶点，以检查是否有来自活跃顶点（即在上次迭代中状态更新的顶点）的传入边。然后，对于来自活跃顶点的所有传入边，相应的顶点使用Process_edge分别处理每条边，并使用Reduce执行reduction，以形成单个值。最后，使用reduce之后的值、其顶点属性和常数顶点属性来使用Apply更新顶点的当前状态**。**属性已更改的顶点在下一次迭代中处于活跃状态，迭代将继续，直到没有更多活跃顶点或指定了最大迭代次数。一些可选参数是用户可以控制的，例如，是否所有顶点在所有迭代中都被视为活跃的，以及收敛阈值是什么。该模型有助于指定各种有用的图算法[43]。2.2 算法
在本文中，我们讨论了四种不同的基本图算法，它们在机器学习、图遍历和图统计等应用中具有代表性。这些是核心内核和构建块，占据了许多应用程序中大部分的图处理运行时间。本节简要介绍了这些算法，并展示了每个算法如何映射到编程模型。
PageRank（PR）PageRank算法根据某些指标（例如流行度）计算图中顶点的分数。网页表示为顶点，超链接表示为边。下面的等式显示了如何计算每个顶点的PageRank分数。α是一个常数，Udeg是顶点U的出度和常数属性。在PageRank中，所有顶点在所有迭代中都被视为活跃的。
广度优先搜索(BFS) BFS 是 Graph500基准中一个广泛使用的图形搜索算法，在一个未加权的图形上进行操作[1]。该算法从一个给定的初始顶点开始，迭代地搜索相邻的顶点，并为每个连接到迭代的活动顶点的顶点分配距离。下面的公式显示了在迭代 t 时，与活动顶点相邻的每个顶点的距离是如何确定的。
单源最短路径（SSSP）这是一种图遍历算法，计算加权图中单个源与所有其他顶点之间的距离。与BFS类似，该算法迭代探索起始顶点的相邻顶点，并将距离分配给连接到迭代活动顶点的每个顶点。BFS和SSSP之间的主要区别在于，SSSP利用边权重来确定距离，而BFS没有。下面的等式显示了如何为与活动顶点相邻的每个顶点确定距离。
协同过滤(CF) CF 是推荐系统中一种流行的机器学习算法。它根据一组不完整的(用户，项目)评分来评估给定项目的用户评分。该算法的假设是通过用户与项目之间的潜在特征匹配来确定一个(用户，项目)的等级，算法的目标是计算每个顶点(即用户和项目)的潜在特征。为了达到这个目的，执行了基于梯度下降的矩阵分解。下面的公式显示了如何计算每个顶点的特征。Vf 是一个长度为 K 的特征向量(注意，本文使用了 K = 32) ，λ 和 γ 是常数。协同过滤运行在一个无向二部图上(也就是说，一个图的顶点可以分成两个不相交的集合—在 CF 中，用户集和项目集是两个不相交的集合) ，并且所有的顶点在所有的迭代中都被认为是活跃的。
将算法映射到编程模型 可以有多种方法将算法映射到此处指定的顶点编程模型。上述算法的映射示例如表一所示。请注意，Process_Edge的Vprop参数是一个可选参数。事实上，许多图算法要么不需要这个参数，要么可以在没有这个参数的情况下表示。然而，GraphMat支持Vprop，因为它提高了某些算法（如协同过滤）的可编程性。2.3 软件框架的低效性
之前在[43]中已经表明，大多数平台优化的本机图算法都是内存带宽有限的。为了确定片外内存带宽使用的低效性，我们测量了使用 Intel VTune 放大器的 Intel Xeon 服务器上的 GraphMat [46]带宽消耗[21]。结果如图2所示。
在这里，片外通信的效率被定义为将片外存储器流量归一化为最优通信情况的比率—在一个虚拟设备中的片外存储器访问量，该设备具有足够的片上存储器，可以在每次迭代中重用所有数据，但不能跨越迭代。GraphMat 比 BFS 和 SSSP 的最佳情况执行更多的芯片外存储器访问，因为 GraphMat 执行缓存粒度的芯片外随机访问，并且这些算法使用许多非本地4或8字节访问。这些算法的带宽受到限制，因为取出了整个cacheline，但只使用了一小部分，导致带宽浪费。PageRank 的芯片外内存使用更接近最佳状态，因为它执行更少的随机内存访问。然而，在这种情况下，内存延迟或计算吞吐量往往成为性能瓶颈。在像Flickr这样的小输入图上，GraphMat可以执行的片外访问少于最优访问，因为整个图小到足以容纳40MB LLC，并且与最优通信情况不同，数据在迭代过程中保持在片上。
软件图形处理框架通常还有另一个低效之处，它们必须执行许多指令才能移动数据，并为定义目标算法的自定义计算提供数据。如图3所示，对于四种算法中的三种，执行的指令中不到6%用于自定义计算（即，Process_Edge、Reduce、Apply）。换句话说，超过94%的执行指令负责遍历图（即，查找顶点的相关边等）并加载所需参数（例如，顶点属性、边权重）以进行自定义计算。这些指令开销通常会导致低能效。2.4 克服低效性
为了克服软件框架的低效性，我们采用了两类解决方案。首先，我们应用了内存子系统的专门化，并构建了一个作为加速器一部分的片上存储器。片上存储将频繁而低效的片外随机数据通信转换为片上、高效、细粒度的暂存式记忆体访问，从而大大减少了通信延迟和带宽。其次，我们应用数据结构特定的专门化或数据类型专门化，并围绕处理图形分析原语、顶点和边形成数据路径。这进一步减少了外围指令的开销，以便为计算准备操作数。在这项工作中，我们将证明数据类型专门化与可编程和高性能顶点程序范式相结合，使得 Graphicionado 流水线不仅平衡特定性和灵活性，而且提供卓越的能效。3. GRAPHICIONADO OVERVIEW
Graphicionado 是一个专门处理图分析算法的硬件加速器。为了更好的可编程性和灵活性，Graphicionado 继承了软件图处理框架 GraphMat 的优点。与软件图形处理框架一样，Graphicionado 允许用户通过定义三个计算(Process_ Edge、 Reduce 和 Apply)来表达特定的图形算法。此外，它透明地处理所有必要的数据移动和片内外通信，以支持这些操作。Graphicionado 通过对计算流水线和内存子系统应用专门化，克服了软件图处理框架的局限性。3.1 图处理模型
图4显示 Graphicionado 使用伪代码的工作流程。Graphicionado 采用坐标格式的输入图。在这种格式中，图表示为一个顶点列表，其中每个顶点 v 与一个顶点属性 VProperty 相关联，每个边 e 与一个由边id eid 索引的3元组(srcid，dstid，weight)相关联。先根据 srcid 再根据 dstid 对这个边列表进行排序。在将输入图输入到 Graphicionado 处理流水线之前，需要对输入图进行一些预处理: 构造一个 EdgeIDTable 并将其存储在内存中。这个数组存储每个顶点的第一个边的 eid，以允许从特定顶点开始的边的流式访问。Graphicionado 还使用内存来存储与所有顶点关联的顶点属性数组 VProperty、临时顶点属性数组 VTempProperty 和常量顶点属性数组 VConst。
Processing Phase 在这个阶段，检查每个活跃顶点的所有传出边，并计算必要的用户定义计算，Process_Edge 和 Reduce，以及相关顶点属性的更新，并将其存储到临时顶点属性数组 VTempProperty 中。只有当处理完所有活跃顶点时，此阶段才会终止。对于一些图分析工作负载，比如协同过滤，不仅需要读取和操作与源顶点相关的属性，还需要读取和操作与目标顶点相关的属性，如伪代码(第6行)所示。
Apply Phase 在这个阶段中，与所有顶点关联的属性使用用户定义的 Apply 函数进行更新。Apply 使用来自顶点属性数组 VProperty 的输入值、存储在内存中的常量顶点属性数组 VConst 以及从处理阶段计算出的临时顶点属性数组 VTempProperty，对顶点属性数组进行必要的更新。ActiveVertex 数组跟踪哪些活跃顶点在此阶段更改了其属性值。其实就是在processing阶段从某一个活跃顶点开始处理其连着的所有边，将目的顶点要更新的值放在临时数组中，直到处理完所有活跃顶点，该阶段结束。在apply阶段利用这个临时数组更新目的顶点属性值。
3.2 硬件实现
在本节中，我们将描述实现 Graphicionado 图形处理模型的硬件块的微架构。每个模块对应于图4中的一行或多行伪码，其物理特性是使用第七节所述的实现方法获得的。图5显示了一个基本的 Graphicionado 流水线，该流水线由模块和模块之间用于通信和连接的小硬件队列(4-8个入口 FIFO)构成。
Graphicionado 模块
Sequential Vertex Read 执行给定起始地址的顺序内存读操作。它缓冲一个cacheline的数据，并且每次将一个顶点属性传递给输出队列，以供下一个流水阶段使用。该模块用于processing阶段的 P1阶段，以及apply阶段的 A1和 A2阶段来读取 VProperty 和 VTempProperty。
Sequential Vertex Write 执行给定起始地址的顺序内存写操作。它从输入队列获取要存储的数据，并将其写入其内部缓冲区。当它的内部缓冲区有一个缓冲区值的数据时，它执行对内存的写请求。此模块用于在apply阶段的A4中存储更新后的 VProperty，将在A5中存储 ActiveVertex。
Random Vertex Read/Write 执行给定顶点 ID 的随机读和写。它用于在阶段 P4中读取目标 VProperty，在阶段 P7和 P9中读写 VTempProperty。
EdgeID Read 执行从预构造的 EdgeIDTable 中读取给定的顶点 id，并输出与输入顶点 id 关联的第一条边的 eid。该模块的实现对于基础流水线和优化的 Graphicionado 流水线是不同的。第4.1节提出了一个优化的实现。
Edge Read 执行给定 eid 的边数据的随机和顺序读取。初始访问是随机的，但后续访问是连续的。检查所有流入的边数据的 srcid。只要所获取的边的 srcid 与正在处理的边的 srcid 匹配，模块就会继续从内存中获取边数据。
Atomic Update 通过三个步骤执行目标 VProperty 的更新。首先，模块在阶段 P7中读取 VProperty，然后在阶段 P8中执行 Reduce 计算，最后将修改后的 VProperty 写回阶段 P9中的内存。由于这是一个读-修改-写的更新，因此对于同一个顶点，进程需要是原子的(即同一个顶点不能同时出现在多个流水阶段中)。该硬件模块通过暂停流水线并且当检测到违反条件时阻塞正在处理的顶点 id 的事务来强制 P6阶段的原子性。我们使用一个小的4路关联 CAM-like 结构来实现这种原子性(16个4字节条目)。
Custom Modules 如前所述，Graphicionado 使用三个用户定义的自定义计算—— Process_Edge、 Reduce 和 Apply ——它们表示目标图算法。实现这些自定义计算有几种选择: 1)完全可重构的结构(例如，FPGA 片上/片上封装[26]) ，2)可编程的 ALU，或者3)一组算法的片上完全自定义实现。用户可以根据自己的需要在这些选项中进行选择。本文使用第三种方法对其进行评估，我们使用单精度浮点加法器、乘法器和比较器构造自定义函数。
4. GRAPHICIONADO OPTIMIZATIONS
第三节介绍了 Graphicionado 流水线的基础实现。然而，为了使这个流水线有效地工作，匹配每个流水阶段的吞吐量以实现最大效率是非常重要的。本节探索基础实现的潜在瓶颈，并提供优化和扩展以减轻这些缺点。
A. 利用片上暂存器存储器（SPM）
改进目标顶点更新
Graphicionado 管道中最重要的瓶颈之一是目标顶点更新（图 5 阶段 P6-P9）。它的性能很差，因为随机顶点读取和写入内存的速度很慢。此外，顶点属性需要更新，许多图形算法小于8字节，执行缓存线粒度内存读取和写入最终会浪费片外内存带宽。更进一步，目标顶点更新必须是原子的。如果要更新的下一个目标与当前正在更新的目标相同，则对内存的长延迟随机访问可能会使流水线长时间停止。Graphicionado通过利用专门的大型片上嵌入式DRAM（eDRAM）暂存器来优化这些随机顶点读取和写入（图6级P6-P9）。这种片上存储容纳了 VTempProperty 阵列，可显著提高随机顶点读取和写入的吞吐量，通过在片上读取和写入来消除cacheline粒度片外存储器访问的带宽浪费，并通过最大限度地减少 VTempProperty 访问的延迟来降低流水线停顿时间。
改进边 ID 访问
管道中的另一个潜在性能瓶颈是读取 EdgeIDTable（图 5 阶段 P2）。在此阶段中，从内存中读取给定源顶点的第一个传出边的eid。这是另一种随机内存访问，它使流水线停止以进行长延迟访问，并浪费片外内存带宽，因为eid只有4个字节。与读取目标顶点属性的情况一样，Graphicionado也将此EdgeIDTable数据放在片上暂存器存储器中。
在片上存储 VTempProperty 和 EdgeIDTable 可消除流水线中几乎所有的随机内存访问。在片上暂存器存储器大小不够大的情况下，将采用有效的分区方案并在第VI节中进行描述。分区方案仅允许将部分此类数据存储在片上，同时将性能影响降至最低。
B. 边访问模式优化
虽然一些图形算法（例如BFS和SSSP）与活动顶点的边界一起运行，但有许多算法只是将所有顶点视为活跃顶点，例如PageRank和CF。我们将这些算法称为完整的边访问算法。对于完整的边访问算法，图 6 中的阶段 P3 从边列表的开头执行顺序读取。这种优化以及利用片上暂存器存储器可消除任何随机的片外存储器访问，因为所有顶点都被视为活跃状态，并且不使用阶段P4中的可选目标顶点属性。在apply阶段也进行了类似的优化，其中删除了图 5 中的阶段 A5，并如图 6 所示为生成的优化流水线。
C. 预取
通过上述优化，Graphicionado中的大多数片外存储器访问现在都是顺序访问。由于这些片外存储器访问的地址不依赖于流水线的任何其他部分，因此我们可以轻松执行下一行预取，并在需要之前将数据导入加速器。我们将顺序顶点读取和边读取模块（图 6 中的阶段 P1 和 P3）扩展到预取和缓冲到cacheline直至N个 （N=4用于我们的评估），并将它们配置为只要缓冲区未满，就继续从内存中获取下一个cacheline。通过这种优化，几乎所有的顺序内存访问延迟都可以隐藏，Graphicionado可以以高吞吐量运行。
D. 对称图的优化
大多数图形处理框架（包括GraphMat）自然地与有向图一起工作。在这样的框架中，无向输入图被有效地视为对称图。也就是说，对于每个边（srcid，dstid，weight），都存在一个对称边（dstid，srcid，weight）。虽然此方法有效，但它会为完整的边访问算法（如协同过滤）带来不必要的内存访问。例如，为了处理边（u，v，weight），在处理阶段结束时读取源顶点属性VProperty [u]，目标顶点属性VProperty[v]和边数据e = （u，v，weight）并更新VProperty [v]。稍后在处理对称边缘（v，u，weight）时，将再次读取完全相同的数据集，并且这次更新了VProperty [u]。为了减少带宽消耗，Graphicionado 扩展了其流水线，以便在从对称图处理边时可以更新源顶点属性和目标顶点属性，而无需读取相同的数据两次。这反映在图 6 阶段 P5-P9 所示的优化管道中，其中这部分流水线被复制。
E. 大顶点属性支持
当前的 Graphicionado 流水线旨在支持每个周期处理多达 32 个字节的顶点属性数据。当需要较大的顶点属性时，例如，Collaborative Filtering 实现每个 128 字节的顶点属性，则将大顶点属性简单地视为涉及多个 flit 的数据包，其中每个 flit 包含 32 个字节。对于Graphicionado中的大多数流水线阶段，每个flit都是在不等待整个数据包到达的情况下处理的（以类似于虫洞交换的方式）。对于自定义计算阶段，我们等待整个数据包数据使用简单的缓冲方案到达，然后再执行计算（如在存储和转发交换中）以保持功能。通过适当的缓冲（CF 情况下为 4 flit），管道的吞吐量不会受到显著影响。
5. Graphicionado Parallelization
通过第 IV 节中描述的优化，Graphicionado 能够以合理的效率处理图形分析工作负载。但是，到目前为止，它是一条流水线，理论上的最大吞吐量限制为processing阶段的每个周期一个边，apply阶段的每个周期一个顶点。本节讨论通过利用图工作负载中固有的并行性来进一步提高 Graphicionado 流水线吞吐量。
A. 扩展到多个流
在 Graphicionado 管道中提供并行性的一种朴素方法是复制整个管道，并让每个复制的管道或管道流来处理一部分活动顶点。事实上，这是软件图形处理框架中增加并行度时最常见的方法。不幸的是，这种方法在硬件管道中引入了一些重大缺点。当多个复制的流尝试读取和写入相同的片上暂存器位置时，这些操作将被序列化，性能会降低。为了避免这些访问冲突，Graphicionado将处理阶段分为两部分，面向源的部分和面向目的地的部分，对应于图5中的阶段P1-P3和阶段P4-P9。然后分别复制这两个部分，并使用如图7所示的横杆开关连接。管道面向源部分中的每个并行流负责执行源顶点的子集，管道面向目标部分中的每个并行流负责执行目标顶点的子集。横杆开关通过匹配边缘的目标顶点 ID 来路由边缘数据。为了最大限度地提高交换机的吞吐量，实施了虚拟输出队列 [47] 等标准技术。
管道的面向源部分从内存中读取预先分区的源 VProperty 和关联的边缘;分区是使用源顶点 ID 的最后一个完成的日志2(n)位n流。类似地，管道中面向目标的部分从内存中读取预先分区的目标 VProperty，并从片上暂存器读取和写入预先分区的目标 VTempProperty，如图 8 所示。分区是使用目标顶点 ID 的最后一个完成的日志2(m)位m流。
源流和目标流的这种并行化消除了内存访问冲突，因为每个流都严格限制为仅访问以独占方式分配的内存和暂存器内存区域。这种并行化技术的另一个优点是简化了片上暂存器存储器设计。我们实施m用于 Graphicionado 的双端口 eDRAM 实例，而不是使用单个大型 eDRAM2米港口。
B. 边访问并行化
对于这种并行化的Graphicionado管道，Read Edges（阶段P3）可能是性能瓶颈之一，因为它需要偶尔执行随机片外存储器访问。即使对于不需要随机片外存储器访问的完整边缘访问算法，此阶段仍然可能是性能瓶颈，因为它每个周期只能处理一个边，而先前阶段读取源属性和读取 EdgeIDTable 每个周期可以处理一个顶点。现实世界的输入图往往在顶点数和边数之间有很大的差异，边数比顶点数大一个数量级或几个数量级。这使得每个周期获取多个边沿对于保持高吞吐量和平衡管道设计是必要的。Graphicionado 复制读取边缘单元并并行化边缘访问。
我们在图 9 中展示了基于主动顶点的算法和完整边缘访问算法的并行化边缘访问的不同实现。在基于活动顶点的算法实现中，活动顶点 ID 根据输入队列占用率（最低占用率优先）分配给边缘访问的读边单元之一。然后，从存储器加载的边沿被仲裁并传递到横杆开关上。在完整的边缘访问算法实现中，每个源顶点 ID 都广播到所有读取边缘单元，并且这些单元仅访问具有指定目标顶点 ID 的边，如第 V-A 节所述。每个读取边的输出直接连接到横杆交换机的虚拟输出队列。
C. 目标顶点访问并行化
虽然使用可选的目标顶点属性数组并不常见（图 5 中的阶段 P4），但它在存在时会成为性能瓶颈，因为它涉及随机顶点读取。为了缓解这种性能下降，我们实现了类似于上述并行边缘读取器（图9a）的并行化方案。将复制读取 DST 属性模块，并将每个目标顶点 ID 分配给占用最低的模块，以提取目标 VProperty。然后对从内存加载的顶点属性进行仲裁，以在每个周期生成单个输出。
6.可扩展的片上存储器使用率
如第 IV-A 节所述，Graphicionado 将片上存储器用于两个目的：执行临时目标属性更新 （P7-P9） 和读取边缘 ID 表 （P3）。通过将这些数据存储在片上暂存器中，Graphicionado提高了流水线级的吞吐量（P3，P7和P9），避免片外内存带宽浪费，并通过最大限度地减少临时目标顶点属性更新的延迟来降低流水线停顿时间。但是，在许多情况下，暂存器内存大小不够大，无法容纳所有必需的数据。本节探讨有效利用有限的片上暂存器存储器的策略。
A. 图切片
存储临时目标顶点属性需要Number of Vertices× S我ze of 一个 Vertex Property片上暂存器存储器的字节数。假设具有 4 字节顶点属性大小和 32MB 片上暂存器内存大小，则可以支持具有多达 800 万个顶点的图形。为了在不失去片上存储器使用优势的情况下处理较大的图形，Graphicionado 将图形切片为多个切片，并一次处理一个切片。
切片技术的工作原理如下。首先，将输入图中的顶点分为N基于其顶点 ID 的分区。图 10 中的示例图形有六个顶点，它们被划分为两个分区：P1 包含顶点 （1、2、3） 和P2包含顶点 （4， 5， 6）。然后根据边缘的目标顶点落在哪个分区来构造两个切片，如图10右侧所示。对输入图进行切片后，Graphicionado 会为每个子迭代处理图形的一个切片，即对切片 1 执行处理阶段，对切片 1 执行应用阶段，对切片 2 执行处理阶段，对切片 2 执行应用阶段，并对所有迭代重复。由于切片是使用目标顶点 ID 进行分区的，因此可以避免写写冲突，并且不需要对边进行两次处理。切片确实会产生一些开销，因为可以多次读取相同的源顶点属性，因此与不切片相比，总读取带宽使用量略有增加。
B. 对称图的扩展图切片
虽然图形切片与大多数 Graphicionado 优化是正交的，但当与对称图优化一起使用时，它需要额外的管道扩展（第 IV-D 节）。通过对称图优化，暂存器内存需要容纳源和目标顶点的顶点属性数组。在这种情况下，图10中的切片无效，因为它的片上存储要求没有降低。我们采用扩展切片方案，如图 11 所示。
给定一个对称图，如图11所示，Graphicionado预处理该图并生成一个有向图，该有向图仅保留从较大的顶点ID到较小的顶点ID的有向边。
使用生成的有向图，构造三个切片：Slice1={（u， v）|u∈P1，v∈P1}，Slice2={（u， v）|u∈P2，v∈P1}和Slice3={（u，v）|u∈P2，v∈P2}.与原始的图切片方案不同，原始的图切片方案仅侧重于基于 dstid 的图切片，此扩展方案同时考虑 srcid 和 dstid 进行切片。跟N分区，此扩展切片方案生成N(N+1）/2片。
为了使Graphicionado使用这种扩展切片方案进行操作，还必须对控件进行扩展。首先，在执行“应用”阶段之前，应注意确保与要更新的顶点关联的所有边都经过了处理阶段。使用扩展切片方案时，与基本情况不同，“应用”不会对每个子迭代都发生。相反，对于最后一次处理顶点分区的子迭代，它会有选择地发生。此外，由于每个子迭代不会完全处理与顶点分区关联的所有边，因此暂存器内存上的临时顶点属性数据应存储到内存中，并在每个处理阶段之间加载回暂存器内存。
表 12 显示了一个四分区案例的示例控件。请注意，暂存器内存数据的这种必要回写不是动态决定的。相反，它们是由顶点分区的数量先验确定的。因此，在运行时，Graphicionado只需要遵循预先确定的控制流。
C. 粗化边缘 ID 表
片上暂存器的另一个用途是存储EdgeIDTable，它保持顶点与其相应的起始边缘ID之间的映射，如图13-（a）所示。当 EdgeIDTable 的大小太大而无法拟合时，将存储一个粗略的 EdgeIDTable，如图 13-（b） 所示。粗化 EdgeIDTable 为每个对象存储一个 EIDN顶点 （N=2这里）而不是存储每个顶点的EID。要查找与给定顶点 ID 对应的边，读取边单元从索引开始你好：/N在粗化 EdgeIDTable 中，其中 vid 是顶点 ID 和N是粗化因子。
使用粗化的 EdgeIDTable 时，将产生额外的边缘访问，在权衡片上存储大小和额外的边缘访问时需要小心。请注意，切片技术实际上降低了每个顶点的平均度数，从而减少了粗化 EdgeIDTable 的开销。
若有收获，就点个赞吧
0 人点赞
