面向自旋存内计算架构的图算法优化设计

王雪岩 陈序航 贾小涛 杨建磊 屈 钢 赵巍胜*

①(北京航空航天大学集成电路科学与工程学院 北京 100191)

②(北京航空航天大学计算机学院 北京 100191)

③(马里兰大学帕克分校电子与计算机工程系 马里兰州 20742)

1 引言

万物皆关联，用于表达和处理关联关系的图和图计算广泛应用于网络安全、社交媒体、推荐系统等关键领域，成为学术界和产业界的关注重点与研究热点。随着大数据产业的深入发展，图数据规模正在爆炸式增长，图计算系统性能面临前所未有的挑战。传统的图计算系统基于冯诺依曼架构，该架构下数据存储与计算分离，数据需要在内存与中央处理器(CPU)之间通过数据总线进行传输。进入后摩尔时代，内存访问和 CPU 计算的速度不匹配严重制约了计算效率，更为严重的是，大规模图计算问题具有高访存/计算比、访存局部性差、非结构化等特点，导致冯诺依曼瓶颈在大规模图计算系统中更为凸显[1,2]。据统计，图计算过程中存储系统消耗能量占系统整体的 90% 以上[3]，访存带宽问题成为大规模图计算系统高效计算的关键瓶颈。当前已有多种图计算的软件框架来提高分布式计算系统与单节点计算系统[4]中图算法大规模处理的效率，以及定制图加速器[5]、近存图处理方案[6]也被提出，然而这些基于冯诺依曼计算架构或近存的框架难以从根本上解决图计算的访存瓶颈[7,8]。

存内计算技术为解决这一问题提供了可能，通过将数据存储单元和计算单元融合为一体，可大幅减少甚至消除数据搬运。然而，传统易失性的内存技术面临功耗大、设计成本高等问题，近年来，新型非易失性存储器，尤其是自旋磁存储器(Magnetoresistive Random Access Memory, MRAM)的快速发展，为存内计算的高效实施带来了曙光[9]。基于自旋存内计算架构的大规模图计算技术有望解决当前大规模图计算系统面临的冯诺依曼瓶颈，大幅提高大规模图计算效率[9–11]。

在自旋存内计算架构下，存算一体阵列中的存储单元块同时是存内处理核，只需与CPU之间传输少量的控制指令或地址信息。然而，相比于传统冯诺依曼计算架构下中央处理器具备非常强大的复杂计算能力和控制能力，自旋存内计算架构中相对分散的存内处理核更适合处理计算类型相对单一、控制逻辑相对简单的任务[12]。由于存内计算架构的上述数据传输模式和计算特点，传统图算法往往不能很好地直接应用于存内计算。此外，图算法种类很多，不同的图算法的计算类型差别比较大。因此，如何匹配图计算和存内计算架构的特点，实现图在存内计算架构下的高效存储和计算，是大规模图计算存内加速的关键挑战。本文针对该问题开展了深入研究，首先以多种图算法为实例进行优化设计，进一步探索面向自旋存内计算架构的图算法的优化设计方法学，提出图算法面向存内计算架构的优化模型。

2 相关背景

2.1 图与图计算

图(Graph)是计算机领域用于表示对象之间关联关系的一种数据结构，包含顶点(Vertex)和边(Edge)，顶点和边分别表示对象以及对象之间的关系，对现实世界有着强大的表征能力。图计算便是以图作为数据模型来表达问题并予以解决的这一过程，通过对大型图数据的迭代处理，获得图数据中隐藏的重要信息。图计算已被广泛应用于医疗、教育、军事、金融等多个领域，成为全球科技竞争新的战略制高点。

图计算具有高访存计算比和不规则访存的特点，冯诺依曼架构下的访存开销是大规模图计算的关键瓶颈。传统优化方法通过用对暂存器内存优化和流水线的顺序访问减少内存访问延迟等策略只能从一定程度上缓解，难以从根本上解决访存瓶颈问题。2016年，通用的存内计算架构Pinatubo被提出[13]，在存储阵列中实现 AND/OR/XOR/INV 等布尔逻辑，并基于该架构进行图计算加速的评估。此后的一系列研究工作在存算一体阵列中实现了更多的逻辑计算功能，如ADD等，并利用这些逻辑功能实现了更多的图算法类型，对图计算存内处理的可行性也进行了分析和验证[11,14]。前期工作也针对特定图算法，如三角形计数算法等进行了优化设计，以更好地在存内计算架构中执行[12]。然而，面向存内计算架构的更广泛的图算法优化模型有待进一步深入研究。

2.2 自旋存内计算模型

自旋磁存储器利用电子的自旋属性实现数据存储，具有非易失、耐擦写、高速度和低功耗等优点，被认为是下一代最具潜力的非易失性工作内存技术之一[8]。更为关键的是，MRAM 使用器件的电阻信息存储数据，通过电流的累加可以自然地实现逻辑运算，尤其是在耐擦写方面具有很大优势，已被证明是最适合的存算介质之一[9,10]。一个典型的自旋转移矩磁存储器(Spin-Transfer Torque MRAM,STT-MRAM) 单元由1个接入晶体管和1个磁性隧道结(Magnetic Tunnel Junction, MTJ)组成，MTJ由固定磁取向的固定层和可切换磁取向的自由层组成。磁性层被一种隧道氧化物隔开。自由层与固定层的相对磁性取向决定了MTJ所提供的电阻。平行阻态RP对应了低阻态，而反平行阻态RAP对应了高阻态。读操作是通过启用字线并在位线与源线之间施加一个偏置电压，比较通过MTJ时的总电流与提供的参考阈值来读出存储在MTJ中的数据。写操作是通过启用字线并在位线与源线上施加适当的电压，使得流经MTJ的电流大于MTJ临界开关电流来完成。写入的逻辑值取决于写入电流的方向。利用STT-MRAM实现存内计算是在一个STT-MRAM的阵列中同时启用多个字线(WLi和WLj)，并且在字线上施加一个偏置电压Vread，流过源线的总电流(ISL)是流过每个比特单元的电流的总和。通过设置不同的参考阈值可以实现相应不同的逻辑功能。

2.3 自旋存内图加速架构

自旋存内计算芯片电路模块主要包括存储阵列、行列译码器、读写电路、输入输出 (I/O) 模块、控制器等，其中存储阵列、输入输出模块与常规自旋磁存储器芯片类似。通过对行列译码器和读写电路做修改可支持图计算涉及的逻辑运算功能。图计算存内加速架构主要由4个部分组成：控制器、数据缓冲器、MRAM存算单元、特殊功能单元(Special Function Unit, SFU)(见图1(a))[12,15]。首先将图数据存储在存算一体阵列，通过控制器控制在存算一体阵列中执行相对应的逻辑操作，若图算法需要比较、乘法等复杂的运算操作，则将需要进行运算的数据转到SFU中进行特殊运算。计算阵列的内部结构如图1(b)所示，每个芯片由若干Bank组成，每个Bank由若干子阵列构成，它们连接到全局行解码器和全局数据寄存器上。子阵列由多个Mat构成，每个Mat中由行驱动和列驱动对阵列的计算形式进行控制。

图1 基于MRAM的图计算存内加速架构

3 面向存内计算架构的图算法优化

利用图和矩阵在数学上的等价关系，图算法通常可以通过矩阵运算在存内计算架构中实现。然而，一些复杂的矩阵运算(例如矩阵乘法)普遍存在于图算法的矩阵实现中，且在存算一体阵列中实现这些复杂运算面临很大的开销。通过分析矩阵运算对应图计算的物理意义，可以避免矩阵乘法等复杂的运算，仅利用“与”逻辑运算等简单位运算即可完成特定图算法，从而能够高效地在自旋存内处理核中实现[15]。本部分进一步探索了单源最短路径、K-core、链路预测等图算法的优化实现，并以此提出基于位运算等简单运算的图算法优化设计模型。

3.1 单源最短路径算法优化设计

单源最短路径算法广泛应用于路线图、超大规模集成电路设计等领域。单源最短路径算法计算一个初始顶点到其他顶点的最短距离。传统的计算单源最短路径的算法涉及大量的循环递归操作，难以在存内计算架构高效实现。因此，亟需对单源最短路径算法进行优化设计。

本文提出基于原位计算的单源最短路径计算方法。如图2所示，首先，设置一个序列标记未被处理的顶点(Tag序列)，除源顶点V0外均初始化为1，将源顶点V0对应位置设置为0；一个序列标明源顶点与各目标顶点的初始连接关系(Connected序列)，即为图的邻接矩阵中源顶点对应行；一个结果序列用于存储源顶点到图中其他所有顶点的最短路径(Distance序列)，初始化为图的邻接矩阵中源顶点对应行，元素0表示当前源顶点不可到达该目标顶点。然后，将Tag序列与Connected序列进行AND逻辑操作，找到未被处理且存在路径从V0可达的顶点Vi(AND运算为“1”)。最后，在邻接矩阵中定位第i行，定位该行中第1个不为0的顶点Vj，将源顶点到顶点Vi的路径长度S(V0,Vi)与顶点Vi到顶点Vj路径长度S(Vi,Vj)相加，并将其与目前源顶点到顶点Vj的路径长度S(V0,Vj)进行比较，较小的即为当前源顶点到顶点Vj的最短路径。注意需区分当前源顶点与目标顶点的路径状态是否为不可达的状态，如果连接序列相应值为0表示不可达，此时应输出较大值作为当前路径长度，图2中使用比较单元(CoMPare unit, CMP)和多路选择器实现该逻辑。之后，重复上述操作，不断更新源顶点到各目标顶点更短的路径距离，直到得到源顶点到所有顶点的最短路径。

图2 基于位逻辑运算优化实现单源最短路径

3.2 K-core算法优化设计

K-core算法在图中找出符合指定核心度的紧密关联的子图结构，其中每个顶点至少具有K的度数，且所有顶点都至少与该子图中的K个其他顶点相连。K-core算法在金融风控、社交网路和生物信息等领域广泛应用。本文首先计算图中每一个顶点的度数，即计算图的邻接矩阵中每一行非0元素的个数，这一过程可以用比特计数器完成。将比特计数器返回的结果发送到比较器，与预定的K值进行比较，如果计算后的结果大于K值，则不做处理，否则将该顶点在矩阵中所在的行与列做清零处理，相当于在图中删除了该顶点。重复上述过程直到没有新的顶点被删除，返回当前K-core子图。

3.3 链路预测算法优化设计

链路预测是图计算中的一个经典问题，即通过已知的网络节点以及网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性。例如，集成数据库系统(DataBase systems and Logic Programming, DBLP)网站集成了计算机科学领域的综合研究论文列表。 可以从 DBLP 中的论文构建共同作者关系图，其中作者是节点，如果作者共同撰写了至少1篇 DBLP 中记录的论文，则可以认为他们是有联系的，预测以前从未合作过的作者之间的新合作是一个有趣的链路预测问题。局部重叠度量是非常有效的链路预测的启发式方法，即基于邻域重叠度来处理关系预测任务，邻域重叠度定义为两个顶点共同邻居节点和总邻居节点数量的比值，然后设置一个阈值来确定何时预测边的存在。该方法适用于资源受限的边缘侧计算场景，且即使与更先进复杂的深度学习方法相比，也常常能获得有竞争力的性能[16]。

图3展示了一个在存内优化实现图的链路预测的例子。假设要预测顶点V2与顶点V4之间是否有一条边相连，首先找到顶点V2和V4在图的邻接矩阵中所对应的行，分别为R2和R4，对R2和R4两行间进行AND逻辑运算，并用比特计数器统计非零元素的个数，即为两个顶点间共同邻居顶点的个数。之后，再对R2和R4两行之间进行OR逻辑运算，并用比特计数器统计非零元素的个数，即为两个顶点间总的顶点的个数。最后，将进行AND逻辑运算与进行OR逻辑运算后的结果发送到特殊功能单元(Special Function Unit, SFU)中进行除法运算操作，再与我们设定的预测阈值进行比较，从而确定顶点V2与顶点V4之间存在边的可能性。

图3 基于位逻辑运算优化实现链路预测算法

3.4 图优化设计模型

面向存内计算架构优化的图算法计算过程主要分为4个主要的步骤：(1)初始化；(2)目标定位：寻找顶点的邻居顶点；(3)属性汇聚：将顶点与其邻居顶点聚合；(4)计算更新：更新顶点聚合后的属性。具体而言，在初始化阶段，将给定图算法的计算参数和与数据存储在图数据缓冲区中。如表1所示，在目标定位阶段，定位满足特定条件的顶点，其中不同图算法具有不同的条件，例如连通分量计算算法和单源最短路径算法根据AND运算结果进行筛选；在属性汇聚阶段，通过逻辑运算将目标顶点的相关顶点信息汇聚，如AND/OR/Bitcount等计算；在计算更新阶段，通过位计数器或者特殊功能单元(包括加法、除法、比较操作等)来更新图的相关属性值。反复迭代该过程，直到满足算法的终止条件，得到最终的结果。本文提出的面向存内计算架构的图算法优化模型可以为其他图算法设计提供思路框架。

表1 图算法存内计算优化模型

4 实验结果

4.1 实验环境设置

为了验证本文所提方法的有效性，我们进行了自旋存内图计算系统的器件 电路 架构跨层次协同仿真。具体而言，在器件级，使用 Brinkman 模型和 Landau Lifshitz Gilbert(LLG)方程表征自旋电子器件(参数设置见表2)；在电路级，设计自旋电子器件的Verilog A模型，使用 45 nm的FreePDK库对电路进行表征，获取器件单元的读写时延和能耗；进一步地，基于Verilog设计外围控制电路等模块，实现图算法需要的基本逻辑运算类型，并使用 Synopsis Tool 进行综合后仿真，得到逻辑运算的性能参数；在架构级，基于开源的模拟器NVSim获得在自旋存算一体阵列(16 MB STT-MRAM)中进行逻辑运算的性能；最后，基于SNAP图数据集[17]进行整体性能评估。在CPU(Intel(R)Core(TM)i7-7700HQ, 2.8 GHz, 8核)计算平台上调用GraphX计算框架作为计算速度与能耗的比较基准。

表2 MTJ关键参数

4.2 性能与能耗比较

表3展示了本文所提单源最短路径算法、K-core算法和链路预测算法在图的存内加速架构上的性能与现有的CPU计算框架GraphX的实现对比。在单源最短路径算法、K-core算法、链路预测算法上，相比于CPU实现，本文所提方案均可以实现平均一个数量级以上的加速。

表3 图计算存内加速架构实现与CPU实现速度对比(s)

图4展示了在单源最短路径算法、K-core算法和链路预测算法上的能耗情况与现有的CPU上的计算框架GraphX上的比较。与现有的CPU计算框架相比，本文提出的方案在单源最短路径算法、K-core算法和链路预测算法上平均节省30倍以上的能耗。

图4 图计算存内加速架构实现与CPU实现的能耗标准化结果对比

5 结论

传统的大规模图计算系统面临冯诺依曼架构下的访存瓶颈，基于新型自旋磁存储器的存内计算架构加速大规模图计算成为研究热点。本文探索了单源最短路径、K-core、链路预测等图算法的优化实现，并以此提出了基于位运算等简单运算的图算法优化设计模型，对于突破大规模图计算所面临的冯诺依曼瓶颈具有关键意义。