超图作为图的一般推广，能够准确地表达数据之间普遍存在的高阶关联性。在超图中，每条超边能够同时连接任意数量的顶点，从而打破了传统图只能抽象成对交互的局限性，为抽象复杂问题中的多元交互关系提供了新的方法。目前，超图已广泛应用于超大规模集成电路设计、3D对象识别和图像检索等领域。然而，现有超图计算系统普遍采用以任务为中心的执行模型，使得众多公共顶点（或超边）在不同的时间被不同的处理单元重复地访问，导致了片上缓存命中率低下。为了从根本上解决这一问题，我们提出了以数据为中心的超图执行模型，即根据已加载到片上缓存中的数据反向触发相关任务参与计算。在此种执行模型下，每轮迭代中的超图数据只需被加载到片上一次，就可以被其相关计算任务充分重用，从而极大地改善了超图计算的时间和空间局部性。为了最大限度地释放该执行模型的性能潜力，我们进一步设计了以数据为中心的超图计算加速器XuLin，其配备了自适应数据加载机制，以消除无效数据的冗余加载。此外，XuLin还配备了优先级感知的差分数据合并机制，以缓解访存冲突造成的性能损失。实验结果表明，与基于CPU的超图计算系统Hygra和基于ASIC的超图处理引擎ChGraph相比，XuLin在性能上平均提升了20.47倍和8.77倍，在片外访存数量上平均减少了9.76倍和2.81倍。

该成果“A Data-Centric Accelerator for High-Performance Hypergraph Processing”发表于会议IEEE/ACM International Symposium on Microarchitecture (MICRO) 2022上，MICRO是计算机体系结构领域的顶级国际会议，也是中国计算机学会（CCF）推荐的A类会议。

• 论文链接：https://ieeexplore.ieee.org/document/9923798

传统图结构只能抽象实体之间的成对关系，无法灵活地刻画诸多现实应用中复杂的高阶关系。然而，高阶复杂关联是物理世界的客观存在。因此，作为简单图拓扑结构泛化表示的超图受到了广泛关注。与传统图结构相比，超图包含一组顶点（如图1（a）中的v₀）和超边（如图1（a）中的h₀），其中每个超边允许连接任意数量的顶点，从而克服了传统图结构难以抽象多元交互关系的局限性。图 1（b）描述了图1（a）中超图的二部图表示，其中实心圆表示顶点v，空心圆表示超边h，彩色实线表示二部边。如果两条超边h_i和h_j共享了至少一个顶点，则称h_i和h_j重叠。例如，图1（a）中的超边h₀和h₂包含公共顶点v₀和v₄则超边h₀和h₂重叠。顶点重叠也有类似的定义。

超图计算依赖于一个迭代处理过程，每轮迭代依次执行超边计算和顶点计算两个阶段。超边计算阶段以特定的顺序（例如按顶点索引的顺序）遍历当前所有的活跃顶点，根据用户定义的超边更新函数，依次更新每个活跃顶点的相邻超边。在超边计算完成后，启动顶点计算。该阶段根据用户定义的顶点更新函数，使用新激活的超边的属性值来更新其相邻顶点的属性值，并生成下一轮的活跃顶点集。重复上述过程，直至没有活跃的超边和顶点或达到最大迭代次数。

在早期的研究中，以Hygra为代表的超图计算系统，普遍遵循索引从小到大的顺序来依次处理顶点和超边，使得访存局部性较差和片上高速缓存未命中率较高，从而导致性能受限。以图1（a）中的超图为例，处理超边h₀和h₂都需要访问顶点v₀和v₄。假设片上缓存只能容纳4个顶点，当处理h₀时，顶点v₀、v₄和v₆被加载到片上缓存。接下来处理h₁时，顶点v₁、v₂、v₃和v₅被加载到片上缓存，同时顶点v₀、v₄和v₆被替换出缓存。这使后续h₂的处理面临缓存未命中的情况，刚刚被替换出片上缓存的顶点v₀和v₄，又被重复加载进缓存，造成了冗余的片外存储器访问。整个过程总共发生了12次缓存未命中。

为了提高缓存命中率，我们之前发表在HPCA’22上的工作ChGraph，提出了链驱动的超图处理方法，即优先安排与当前处理的超边存在重叠关系的超边作为后继待更新的超边，使得这两个超边的共享顶点被加载到片上高速缓存后可以被及时地重用。图1（c）所示的超边链代表了新的执行序列h₀、h₂、h₁、h₃。首先，超边h₀的内部顶点v₀、v₄和v₆被加载到片上缓存中。接下来处理超边h₂，顶点v₀和v₄被及时地重用，发生缓存命中。当处理超边h₁时，顶点v₂还驻留在缓存中，因此被重用。但是，顶点v₀、v₄和v₆被v₁、v₃和v₅替换出片上缓存。当处理超边h₃时，顶点v₁和v₃会被重用。上述过程发生了8次缓存未命中，相比于原来的12次，降低了三分之一。

虽然ChGraph通过调整任务的执行顺序可以改善超图计算的时间局部性，从而降低缓存未命中，但是其片外访存时间仍然占总执行时间的49.65%。究其原因是链与链之间数据重用的机遇被忽视。以图2中的超图为例，其两条超边链Chain#1（h₁、h₄、h₀、h₅）和Chain#2（h₃、h₆、h₂、h₇）被两个计算单元并行处理。Chain#1中的h₁在开始时访问顶点v₁和v₈，而Chain#2中的h₇在结束时需要访问顶点v₁和v₈。但两者间隔时间较长，顶点v₁和v₈可能被其他数据替换出缓存，造成了缓存未命中。其次，虽然ChGraph改善了时间局部性，但是空间局部性仍然很差，甚至因为任务执行顺序的调整，使得空间局部性变得更差。上述两个问题导致的冗余片外访问量占总访问量的63.78%，成为了制约超图计算性能的主因。

从本质上讲，先前的解决方案都遵循了以任务为中心的执行模型，即首先将二部边任务按照指定的顺序依次调度到计算单元，然后将任务所需的数据从片外存储器加载到片上高速缓存来并行处理。然而，由于顶点和超边之间存在复杂的交织关系，几乎不可能找到一个局部性最优的调度顺序。因此，我们提出一种新颖的以数据为中心的超图执行模型，其首先将数据加载到片上缓存中，然后根据已加载的数据反向触发其所有相关二部边任务参与计算。在此种执行模型下，每轮迭代所需的数据只需要加载一次，就可以被其所有的相关任务充分重用，时间和空间局部性得到了极大地改善。

基于上述见解，我们提出了以数据为中心的加载-触发-合并（Load-Trigger-Reduce，LTR）执行模型，以优化超图计算的局部性。为了方便将数据加载进片上缓存，我们借鉴现有的超图划分方法，将一个大规模的超图划分成若干个小分区。在每轮迭代中，对于一个超图分区，其顶点和超边数据首先被加载到片上缓存。然后，该分区中的二部边任务将以流的方式加载到片上缓存，并触发计算，生成中间结果。最后，对相同顶点在不同计算单元中生成的中间结果进行并行合并，生成唯一终值。

该LTR执行模型足够通用，可以在CPU、GPU等多种硬件实现。但是，由于以下原因，其性能潜力将受到限制。首先，LTR模型要求超图数据分区必须驻留在片上缓存直到所有相关任务执行完成，才能被替换出缓存。但是，在CPU架构上，缓存中的数据是由其缓存替换策略（例如，最近最少使用算法LRU）来管理，难以显示地控制。其次，分区中的顶点数据并不一定在每轮迭代中都被使用，这取决于它们相关联的超边是否被激活。因此，每轮迭代都加载整个分区会产生大量不必要的片外访存。最后，LTR模型会同时运行多个相似的任务来更新同一顶点，这虽然提高了并行性，但也导致了严重的数据冲突。

为了解决上述三个问题，以充分挖掘LTR执行模型的性能潜力，我们进一步设计了LTR驱动的超图计算加速器XuLin。如图3所示，该加速器主要由数据加载器Loader、地址翻译器Translator、任务触发器Trigger、任务处理器Processer、合并器Reducer等五个部件组成。其中数据加载器、任务触发器以及合并器分别对应LTR模型中的三个执行阶段任务。考虑到片上缓存、计算单元私有寄存器和片外存储器使用不同的地址空间，地址翻译器负责对不同地址空间上的数据地址进行转换，并记录地址映射关系。任务处理器负责对任务触发器输出的二部边任务执行具体的更新逻辑。

XuLin配备了自适应数据加载机制，以减少不必要的数据加载。具体而言，我们在数据加载器中内置了一个基于键值的划分表，该表记录了当前各分区的激活信息，以指导数据加载器跳过不存在活跃顶点或超边的分区。为了进一步减少无效数据的加载，我们将每个分区划分为细粒度的子块，并构建子块表。我们将包含活跃数据的子块动态组合成逻辑分区并加载到片上缓存参与计算。由于子块表存在一定的维护成本，我们根据激活超边的数量自适应决定是否使用子块合并的策略，以最大化数据加载的效率。

为了有效地缓解数据冲突造成的性能损失，XuLin配备了优先级感知的差分数据合并机制。如图4所示，将频繁发生访存冲突的数据（即高优先级数据）复制多份并缓存在计算单元私有寄存器PR中。每个计算单元HPU更新本地寄存器PR中的数据副本，待每个分区中的计算任务全部执行结束后，每个寄存器PR中的数据被发送给二叉合并树HDRU完成中间结果合并。对于低优先级数据，我们采用基于双调排序的归约网络，来实时完成对HPU输出的低优先级中间结果的高效合并。

为了验证以数据为中心的LTR执行模型的有效性，我们在CPU上实现了一个基于LTR的超图计算系统，称之为XuLin-C。另外，我们在FPGA和ASIC平台上分别实现了我们的硬件设计，称之为XuLin-F和XuLin。基于CPU的超图计算系统Hygra和基于ASIC的超图处理引擎ChGraph作为对比对象。实验结果如图5所示，同为基于CPU的解决方案，XuLin-C相比于Hygra实现了平均2.21倍的性能提升，充分说明了LTR执行模型的优越性。相比于Hygra和ChGraph，XuLin分别实现了平均20.47倍和8.77倍的性能提升。这一方面是得益于LTR执行模型对超图计算局部性的改善，另一方面是因为硬件加速器设计能够避免指令预取和控制等开销。

图6显示了XuLin、XuLin-C、ChGraph和Hygra的片外存储器访问量对比结果，相比于Hygra和ChGraph，XuLin分别降低了平均9.76倍和2.81倍的片外存储器访问量。虽然XuLin与XuLin-C均使用LTR执行模型，但是由于CPU架构中缓存替换策略的限制，XuLin-C无法保证每个分区内的数据在其计算过程中始终驻留在cache，因此XuLin-C的片外存储器访问量是XuLin的1.43倍。

详细内容请参见：

Qinggang Wang, Long Zheng, Ao Hu, Yu Huang, Pengcheng Yao, Chuangyi Gui, Xiaofei Liao, Hai Jin, Jingling Xue, “A Data-Centric Accelerator for High-Performance Hypergraph Processing”, In Proceedings of the 55th ACM/IEEE International Symposium on Microarchitecture (MICRO) 2022. 

https://ieeexplore.ieee.org/document/9923798