摘要

图形算法越来越多地用于利用大型数据库的应用程序中。但是，常规的处理器体系结构不足以处理图形计算的吞吐量和内存需求。林肯实验室的图形处理器体系结构代表了对图形问题的并行体系结构的重新思考。我们的处理器利用了创新技术，包括基于稀疏矩阵的图形指令集，无缓存存储系统，基于加速器的体系结构，收缩分类器，高带宽多维环形通信网络和随机通信。已经开发了新图形处理器的现场可编程门阵列（FPGA）原型，在图形计算吞吐量方面，其性能大大超过了常规处理器。

介绍

计算和数据分析中的许多问题都可以用图形表示，并可以使用传统的图形分析技术进行分析。如图1左侧所示，图形定义为一组由边连接的顶点，非常适合呈现数据和关系。通常，图也可以表示为稀疏矩阵，如图1 [1，2]所示，其中从顶点i到顶点j的边表示为第i行和第j列中的矩阵元素。

对于图形数据库应用程序，常规处理器与非图形应用程序相比性能较差，因为常规处理器体系结构通常无法很好地与图形计算流程匹配。例如，大多数现代处理器利用基于缓存的内存，以便利用高度本地化的内存访问模式。但是，与图处理相关的内存访问模式通常通常是随机的，并且可能导致高速缓存未命中率高。此外，图形算法会为图形遍历查询所需的索引操作任务带来可观的计算开销。

通过基于稀疏矩阵的图形表示，标准的线性代数矩阵运算可用于实现大多数图形算法。此外，对于基准图计算，稀疏矩阵运算可用于估计图算法性能。图2显示了稠密矩阵处理和稀疏矩阵图处理[9，10]之间的致密矩阵处理之间的单核计算吞吐量差异的示例。蓝色显示为在单核PowerPC和Intel Xeon处理器上运行的密集矩阵矩阵乘法内核。相反，红色显示的是在相同处理器上运行的稀疏矩阵-矩阵乘法内核。如图所示，稀疏矩阵吞吐量大约降低了1000倍，这与图形分析应用程序看到的典型性能是一致的。

并行处理器经常被用来加速大型常规计算任务。并行处理器通常由通过通信网络连接的多核处理器组成，因此可以在不同的处理器上完成计算的不同部分。对于许多科学计算应用程序，这些处理器比单个处理器可提供显着的加速。但是，大型图形处理任务通常无法在常规并行处理器上高效运行。在仅使用少量处理器之后，加速通常趋于平稳，因为图形算法的计算模式与常规的高度本地化处理所需的相比，在处理器节点之间需要更多的通信。传统并行处理器的有限通信带宽通常无法跟上图形算法的需求。过去，已经进行了许多尝试，以通过优化处理器体系结构来加速图形计算。诸如Cray XMT和Thinking Machine的Connection Machine之类的并行处理器就是使用专门的并行体系结构来加速大型图形处理的示例尝试。但是，与图处理相关的固有困难（包括分布式内存访问，与索引相关的计算和处理器间通信）限制了性能提升。林肯实验室一直在开发一种有前途的新处理器架构，该架构将提供更高数量级的计算吞吐量和功能大图问题的最佳商业替代方案的效率。据测量，我们的处理器的FPGA版本在100瓦特规模上比传统计算机快10倍，并且在1兆瓦特规模上预计要快100倍以上。此外，我们处理器的专用集成电路（ASIC）版本预计在100瓦特规模下将快100倍以上，在1兆瓦特规模下将快1000倍以上。

图处理器

新的图形处理器体系结构代表了对用于优化图形处理的计算机体系结构的重新思考[9、10、13]。该指令集基于新兴的GraphBLAS标准[11，12]，该标准为图形分析提供了通用的稀疏矩阵接口。单个处理器节点（与传统的von Neumann架构大相径庭的架构）具有本地无缓存内存。所有数据计算，与索引相关的计算和内存操作均由专门的加速器模块而不是*处理器（CPU）处理。处理器节点利用经过统计优化的新型高效消息路由算法，用于传送非常小的数据包，例如稀疏矩阵元素或部分乘积。处理器硬件设计也针对高带宽六维（6D）环形通信网络进行了优化。详细的分析和仿真以及一个小型原型已经证明，在大型分布式数据库上运行复杂的图形算法时，计算吞吐量和能效提高了几个数量级。

A 基于稀疏矩阵代数指令集的并行图处理器架构
将图算法实现为稀疏矩阵运算有很多优点。一个优点是，与使用常规指令集直接实现图形算法的传统软件所需的代码量相比，代码行数大大减少。但是，虽然这种优势可以提高软件开发效率，但不一定会导致常规处理器的计算吞吐量更高。

也许在稀疏矩阵运算中实现图形算法的一个更重要的优势是设计并行处理器来进行计算要容易得多。稀疏矩阵运算，而不是一般的图形算法。指令集可以大大简化，因为实现基于稀疏矩阵的图形算法需要很少的基本指令。稀疏矩阵运算有助于处理器体系结构设计的另一个原因是，它更容易可视化并行处理器上运行的稀疏矩阵运算的并行计算和数据移动。这一优势使开发人员可以轻而易举地想到高效的体系结构和硬件设计。

图形处理器是高度专业的并行处理器，针对分布式稀疏矩阵运算进行了优化。该处理器的目标是实现用于分析大型数据库的图形算法（转换为稀疏矩阵格式）。由于大型矩阵无法容纳在单个处理器的内存中，并且需要比单个处理器提供的吞吐量更多的吞吐量，因此该方法是将大型矩阵分布在许多处理器节点上。图4显示了并行处理器的高级体系结构。它由一组称为节点处理器的专用稀疏矩阵处理器组成。节点处理器连接到全局通信网络，它们也通过全局控制总线连接到全局控制处理器。

尽管图3中的通用高级体系结构看起来与传统的多处理器系统非常相似，与传统的并行体系结构实现方式明显不同。主要区别之一是处理器的指令集基于稀疏矩阵代数运算[2]，而不是基于常规指令集。重要的指令内核包括表1中所示的稀疏矩阵-矩阵乘法，加法，减法和除法运算。通常需要替换这些矩阵运算中的各个元素级运算符，例如矩阵乘法运算中的乘法和累加运算符。与其他算术或逻辑运算符（例如最大值，最小值，AND，OR，XOR等）配合使用，以实现通用图形算法。许多图形算法已经被转换为稀疏矩阵运算[2，4，5]。


新体系结构的另一个主要区别特征是高带宽，低功耗的通信网络，该网络专门用于传递小消息。典型的消息包含一个矩阵元素或一个部分乘积，它由数据值，行索引和列索引组成。相反，常规的通信网络试图最大化消息大小，以便最小化与移动数据相关的开销。新开发的具有小消息大小的统计路由算法大大提高了图形处理的通信吞吐量。此外，与传统并行处理器的带宽相比，网络硬件本身的带宽要大得多。需要大带宽来处理图形处理需求。

B 基于加速器的节点处理器架构
实验室的单个节点处理器的体系结构与传统的基于缓存的冯·诺依曼机器（在计算机中执行所有计算）也有很大的不同。这种新架构由许多专用模块组成，包括矩阵读取器，矩阵写入器，分类器，算术逻辑单元（ALU）和通信模块，如图4所示[9、10、13]。 CPU主要用于为稀疏矩阵指令提供控制和时序。大多数计算，通信和内存操作由专门设计为最佳执行给定任务的专用模块执行。没有缓存，因为高缓存未命中率会降低图形处理速度。通常，在执行稀疏矩阵计算时会同时使用多个模块。基于专用加速器模块的体系结构通过实现高度并行的流水线计算，提供了比常规冯·诺依曼处理器体系结构更高的计算吞吐量。在常规处理器中，微处理器用于计算所有处理任务，例如内存访问，与通信有关的处理，算术和逻辑运算以及控制。这些处理任务通常是串行完成的，并且需要很多时钟周期才能执行，从而降低了总体计算吞吐量。在新架构中，这些任务由单独的专用加速器模块并行执行。这些加速器模块设计为使用高度定制的体系结构来实现快速吞吐量。理想情况下，将它们设计为跟上可能的最快数据速率，即在单个时钟周期内以有效吞吐量处理一个矩阵元素或一个部分乘积。通过使这些模块具有多个并行版本来处理每个时钟周期的多个矩阵元素或部分乘积，可以进一步提高速度。矩阵读取器和写入器模块设计为可从内存有效读取和写入矩阵数据。示例格式包括压缩稀疏行（CSR），压缩稀疏列（CSC）和坐标（也称为元组）格式（图5）。在坐标格式中，数据，行索引和列索引存储为三对。为了节省存储空间并提高查找性能，在CSR格式中，元素数据和列索引以数组格式成对存储。一个附加的数组存储每列的行起始地址，以便可以使用这些指针查找存储行的内存位置。 CSC格式类似，除了列是压缩而不是行是压缩的。

矩阵读取器和写入器模块的设计使所有开销操作（例如，对矩阵元素数据和索引进行格式化，为CSC和CSR生成用于写入的指针数组以及为读取而生成矩阵元素索引）自动执行而无需其他操作说明。这样，与稀疏矩阵读和写操作相关的复杂性被最小化，并且显着加快了存储器接口操作.

ALU模块设计为在稀疏矩阵元素或部分乘积流上运行，而不是像常规处理器体系结构中那样通过寄存器文件运行。流传输方法消除了寄存器加载操作，并增加了计算吞吐量。它通常根据索引对数据流执行指定的算术或逻辑运算。例如，仅当元素索引完全匹配时，ALU模块才可以累加连续的矩阵元素。因为这些矩阵运算仅在索引匹配时才执行计算，所以此功能对于稀疏矩阵加法和乘法运算很有用。

通信模块处理处理器节点之间的通信。它获取矩阵元素或部分乘积，并生成一条通信消息，其中包括坐标格式的矩阵元素和包含目标处理器地址的标头。标头还可以包含错误检测和纠正位以及其他相关信息，例如消息的优先级。然后，将通信消息发送到全局通信网络，然后转发到目标节点。通信模块还解码接收到的消息，执行纠错，然后以坐标格式将矩阵元素或部分乘积输出到节点中。

节点处理器的存储器可以用各种类型的存储器来实现，包括静态随机存取存储器（SRAM），动态RAM和同步DRAM。诸如闪存之类的非易失性存储器可以用于长期存储以及例如在存储需求很高的情况下。

节点控制器模块负责设置和协调稀疏矩阵操作。在进行稀疏矩阵运算之前，控制器模块使用本地控制总线将控制变量加载到加速器模块的控制寄存器和控制存储器中。控制变量包括要执行的稀疏矩阵运算的类型，矩阵存储器的存储位置，矩阵分布映射以及其他相关信息。控制器模块还执行定时和控制。节点控制器模块可以用常规的通用微处理器实现。由于该处理大部分是常规处理，因此该特定微处理器也可以具有高速缓存。节点控制器还可以执行加速器模块未很好支持的其他处理任务，例如创建标识矩阵并检查矩阵是否在所有处理器节点上都为空。控制器模块绑定到全局控制总线，该总线用于将数据和程序加载到节点或从节点加载数据，并执行全局计算过程控制。

排序器模块用于对矩阵元素索引进行排序以进行存储，以及在矩阵操作期间查找匹配的元素索引。它是图形处理中最关键的模块之一，因为超过95％的计算吞吐量可以与索引的排序相关联。稀疏矩阵和图形运算主要包括弄清楚应该对哪个元素或部分乘积进行运算。相反，执行相对较少的实际元素级操作。为了满足计算吞吐量要求，开发了收缩式k路收缩合并分类器体系结构[14]，以提供比常规合并分类器高得多的吞吐量。

例如，当k = 32时，k方式合并排序器的吞吐量是2方式合并排序器的五倍。合并分类器。在常规处理器中实现k路合并分类器的主要困难在于，在合并分类过程的每个步骤中，要花费很多时钟周期才能找出k个条目中的最小（或最大值）值。理想情况下，应在一个处理器时钟周期内计算出k的最小值，以实现最大的分拣机吞吐量。 100％有效的收缩期合并分类器[9]可以使用k个线性收缩期阵列单元达到此性能要求，并且由于它由重复的收缩期单元组成，且仅具有最近邻通信，因此特别适合FPGA和集成电路（IC）实现。

C 6D环形通信网络和随机消息路由
新的图形处理器架构是使用高带宽光链路以6D环形配置互连的并行处理器。由于具有更高的二等分带宽，因此6D环形线圈比低维环形线圈具有更高的通信性能。通信网络被设计为一种包路由网络，经过优化可支持小到单个稀疏矩阵元素的小包大小。网络调度和协议的设计应使来自节点的连续通信数据包具有随机的目的地，以最大程度地减少网络拥塞[15]。该设计与典型的常规多处理器消息路由方案形成了鲜明的对比，后者基于更大的消息大小和全局仲裁路由，这些路由用于最小化消息路由开销。但是，基于大型消息的通信通常难以路由，并且由于所涉及的通信链路被阻塞的长时间段而可能具有较高的消息争用率。较小的消息大小以及随机的目标路由可最大程度地减少消息争用并提高总体网络通信吞吐量。图6显示了基于随机目标通信与唯一目标通信的512节点（8×8×8）3D环形网络（出于说明目的绘制为3×3×3网络）的仿真。即使两种路由方法都基于较小的消息大小，但唯一的目标路由具有的消息争用率接近于基于大消息大小的常规路由算法的争用率。在使用相同网络的仿真中，随机目的地路由实现了大约高六倍的数据速率和网络利用率。

FPGA原型开发和性能测量

林肯实验室已经使用商用FPGA板开发了图形处理器的FPGA原型，如图7所示。每个板都有一个大型FPGA和两个4 GB DDR3存储库。每块板上实现了两个图形处理器节点。小型4板机箱可实现与1D环形网络捆绑在一起的8节点图形处理器。由于商用板由于用于网络连接的通信端口数量有限而提供了有限的可扩展性，因此将来将使用可支持6D环形网络和多达100万个节点的定制FPGA板开发更大的原型。

图8显示了每秒遍历的边沿相对于具有不同数量节点的原型处理器的功耗所测得的（1、2、4和8个节点）和预计的（> 8个节点）性能。为了获得预期的性能，对体系结构进行了详细的仿真，并使用位级准确的仿真模型来仿真运行稀疏矩阵-矩阵乘法内核的多达1024个节点的处理器。对于具有8个以下节点的原型处理器，预计性能和测量性能是相同的。为了比较，还绘制了Cray XK7和XT4超级计算机系统的性能。 [16，17]与少量节点上的常规处理器相比，FPGA原型处理器的测量功率效率高一个数量级。在更高数量的节点上，由于计算吞吐量的线性加速，预计的功率效率差异会增加几个数量级。该架构具有多种功能，可实现线性加速。一种是由高带宽网络和高级随机分组路由算法支持的处理器节点之间的足够通信带宽。另一个因素是高效的负载平衡算法。为了使图形处理器高效运行，它需要在所有节点之间平衡内存使用和处理。这意味着处理器节点中存储的稀疏矩阵元素的数量，生成的部分乘积和累积的部分乘积必须与其他节点很好地平衡。

将来，通过使用ASIC代替FPGA，可以获得更高的吞吐性能和功率效率，如图8中的绿色性能线所示。ASIC可以实现更高的处理器电路密度和功率效率。通过从DDR3 SDRAM升级到DDR4 SDRAM，可以提高内存性能和电源效率。对于光通信，利用波分复用（WDM）低功率硅光学技术可以显着提高每根光纤的通信比特率并降低通信功耗[18，19]。

总结

麻省理工学院林肯实验室的图形处理器体系结构代表了对图形体系结构的根本性重新思考。它利用多种创新来克服常规体系结构的缺点，包括：基于稀疏矩阵的图指令集，基于加速器的体系结构，高性能的脉动分类器，随机通信，无高速缓存的存储系统和高带宽MIT林肯实验室已开发出基于商用FPGA技术的图形处理器原型。稀疏矩阵乘法是图形分析中最重要的内核之一，已经在8节点原型处理器上进行了演示，并且正在进行开发更大的原型系统的工作。当前的小型原型旨在证明该体系结构的可扩展性以及空前的图形算法吞吐量和功率效率。在少量节点上测得的功率效率比商用处理器高一个数量级，而在节点数量更多时，预计性能会提高几个数量级。将来，可以使用定制ASIC实现进一步优化此实现，从而进一步提高计算吞吐量和能效