一种异步高能效图计算加速器

技术领域

本发明涉及图数据处理，特别涉及一种异步高能效图计算加速器。

背景技术

随着大数据、云计算技术和互联网产业的逐渐成熟与发展，人类生活进入了数据爆炸的时代。大数据有着“4V”的特征，分别是数据体量大(Volume)、数据类型多(Variety)、增长速度快(Velocity)以及价值密度低(Value)。图作为最经典、最常用的数据结构之一，现实生活中的很多数据经常被抽象成多种多样图结构的数据。图中的顶点可以代表不同的实体，图中的边可以代表不同实体之间的关系[7]。常见的图结构类型的数据有社交关系图(social networks)、网页链接图(web graphs)、交通网络图(transport networks)、基因分析图(genome analysis graphs)等。此外，图数据规模的增长非常迅速，如在2011年，Twitter公司每天发布的推文量超过2*10⁸，而在2013年，Twitter公司每天发布的推文量则上升至5*10⁹。随着机器学习和数据挖掘应用的日益广泛，图数据的规模也变的越来越大。另一方面，由于大规模的图数据表现出极度的不规则性，导致在传统的MapReduce和Hadoop系统上进行计算的过程中产生大量的数据通信，进而造成计算效率低下的问题。如何有效的进行大规模图数据的处理与分析是目前学术界和工业界的一大研究热点，为了有效的应对上述挑战，国内外研究学者纷纷把目光投向图计算加速器的设计。为提高加速图算法的收敛效率，降低图计算的功耗和能耗，本发明设计了一种异步高能效图计算加速器，加速器采取异步计算的方式加速算法的收敛速度，同时采用定制专用加速器的手段降低系统的功耗和能耗。

发明内容

本发明目的是：提供一种异步高能效图计算加速器，提高图数据处理的计算效率，降低图计算加速器的功耗和能耗。

本发明的技术方案是：

一种异步高能效图计算加速器，包括依次连接的数据预处理模块、数据传输模块和数据处理模块，其中：

数据预处理模块，对给定的示例图G在初始化阶段被预处理，对大规模图数据进行划分，进而图G被组织成以batch_size为大小的子图数据Batch Row Vector；

数据传输模块，将子图数据Batch Row Vector通过PCIe DMA传输至板载DDR，再通过AXI DMA传输至片上加速器。

数据处理模块，为加速器片上逻辑，包括存储模块和计算模块；存储模块包括片上缓存、计算模块包括片上计算模块。

优选的，存储模块包括五个缓存区，分别是源顶点缓存区、目标顶点缓存区、源顶点状态值缓存区、目标顶点缓存区以及输出结果缓存区，这些缓存区用来存储片上需要计算的图数据以及输出结果。

优选的，所述存储模块基于行向量的表示形式对图数据进行存储，称为Batch RowVector，Batch Row Vector为2维存储结构，由4个行向量组成，第一个行向量存储子图数据中边的源顶点，第二个行向量存储子图数据中边的目标顶点；源顶点的状态值以及目标顶点状态值被存储在第三个以及第四个行向量中。

优选的，所述片上计算模块分成4个子模块，分别是StreamEdges、AsynchronousController、Reduce、Update；片上计算模块与存储模块通过AXI-Stream连接，其中：

StreamEdges负责遍历片上存储的子图数据，读取源顶点的状态值并且更新目标顶点的临时状态值；

Asynchronous Controller在计算过程中进行异步控制，负责将更新好的最新的顶点状态值传播至后续的计算过程中，在传播的过程中，控制器比较后续计算中的边的源顶点是否与当前计算的边的目标顶点一致，若一致，则进行异步更新；

Reduce负责收集同一个目标顶点上来自不同源顶点的状态值分量，对于PageRank算法来说为“+”操作，对于BFS算法来说为“min”操作；

Update执行更新函数将状态值更新至相应的顶点。

优选的，所述加速器的执行过程包括四个阶段：预处理阶段、StreamEdges阶段、Reduce阶段以及Update阶段；

在预处理阶段，加速器初始化所有顶点的distance，顶点1的distance设置为1，将其设定为根节点，dist[]保存着图数据中所有顶点的distance，每个顶点在dist[]中有对应的状态值；在每一次Batch Row Vector处理之前，host从dist[]读取顶点的状态值填充至Batch Row Vector，然后Batch Row Vector被逐个传输至FPGA的板载DDR中，板载DDR上的Batch Row Vector也将逐个传输至加速器；在StreamEdges阶段，加速器顺序的遍历Batch Row Vector中的边，根据源顶点状态值更新目标顶点状态值；Domino通过线性更新策略和二分更新策略来进行异步控制，异步控制机制将顶点的最新状态值传播至后续的计算过程中；同一个目标顶点的不同状态值分量在Reduce阶段被收集，最后Update阶段执行更新函数将计算好的状态值更新至相应的顶点，host完成batch之间的状态值传播。

优选的，所述线性更新策略对每个batch上的所有图数据进行线性查询。

优选的，所述二分更新策略采用二分查找算法进行实现。

本发明的优点是：

本发明设计了异步高能效图计算加速器，采用异步计算的方式加速了图算法的收敛速度，基于硬件平台定制加速器降低了系统的功耗和能耗。

附图说明

下面结合附图及实施例对本发明作进一步描述：

图1为本发明异步高能效图计算加速器系统架构

图2为本发明异步高能效图计算加速器执行过程示意图；

图3为本发明异步高能效图计算加速器异步更新流程图。

具体实施方式

如图1所示，本发明所揭示的异步高能效图计算加速器，主要针对大规模图数据的处理，采用硬件定制的方式提高系统的效率，降低系统的能耗，包括依次连接的数据预处理模块、数据传输模块和数据处理模块，其中：

数据预处理模块，对给定的示例图G在初始化阶段被预处理，由于硬件平台片上资源的限制，因此需要对大规模图数据进行划分，进而图G被组织成以batch_size为大小的子图数据Batch Row Vector；

数据传输模块，将子图数据Batch Row Vector通过PCIe DMA传输至板载DDR，再通过AXI DMA传输至片上加速器，对于计算结果的传输则与子图数据的传输过程相反。

数据处理模块，为加速器片上逻辑，包括存储模块和计算模块；存储模块包括片上缓存、计算模块包括片上计算模块。

具体实施时，所述存储模块包括五个缓存区，分别是源顶点缓存区、目标顶点缓存区、源顶点状态值缓存区、目标顶点缓存区以及输出结果缓存区，这些缓存区用来存储片上需要计算的图数据以及输出结果。本发明设计基于行向量的表示形式对图数据进行存储，称为Batch Row Vector，如图1所示。Batch Row Vector为2维存储结构，由4个行向量组成，第一个行向量存储子图数据中边的源顶点，第二个行向量存储子图数据中边的目标顶点；源顶点的状态值以及目标顶点状态值被存储在第三个以及第四个行向量中，这里所说的顶点状态值与具体的图算法有关，如对于PageRank算法则是顶点的Rank值，对于BFS算法来说则是顶点距离根节点的BFS深度。

所述片上计算模块分成4个子模块，分别是StreamEdges、AsynchronousController、Reduce、Update；片上计算模块与存储模块通过AXI-Stream连接，其中：

StreamEdges负责遍历片上存储的子图数据，读取源顶点的状态值并且更新目标顶点的临时状态值；

Asynchronous Controller在计算过程中进行异步控制，负责将更新好的最新的顶点状态值传播至后续的计算过程中，在传播的过程中，控制器比较后续计算中的边的源顶点是否与当前计算的边的目标顶点一致，若一致，则进行异步更新；

Reduce负责收集同一个目标顶点上来自不同源顶点的状态值分量，对于PageRank算法来说为“+”操作，对于BFS算法来说为“min”操作；

Update执行更新函数将状态值更新至相应的顶点。

如图2所示，所述加速器的执行过程包括四个阶段：预处理阶段、StreamEdges阶段、Reduce阶段以及Update阶段；在预处理阶段，加速器初始化所有顶点的distance，顶点1的distance设置为1，将其设定为根节点，dist[]保存着图数据中所有顶点的distance，每个顶点在dist[]中有对应的状态值；在每一次Batch Row Vector处理之前，host从dist[]读取顶点的状态值填充至Batch Row Vector，然后Batch Row Vector被逐个传输至FPGA的板载DDR中，板载DDR上的Batch Row Vector也将逐个传输至加速器；在StreamEdges阶段，加速器顺序的遍历Batch Row Vector中的边，根据源顶点状态值更新目标顶点状态值；Domino通过线性更新策略(naive update mechanism)和二分更新策略(bisect updatemechanism)来进行异步控制，异步控制机制将顶点的最新状态值传播至后续的计算过程中；同一个目标顶点的不同状态值分量在Reduce阶段被收集，最后Update阶段执行更新函数将计算好的状态值更新至相应的顶点，host完成batch之间的状态值传播。

加速器异步更新流程如图3所示，其中粗体的数字表示已经更新过的顶点的状态值，弧线的箭头表示异步更新的过程。初始阶段，第一条边(1,2)被访问并且被处理，根据源顶点1的状态值0，将目标顶点2的状态值更新为1；然后异步控制器遍历后续的边集，并且选取源顶点为2的边，将顶点2的更新过的状态值刷新至这些边的源顶点状态值域中，如第三条边(2,3)，因此在处理(2,3)的时候，更新目标顶点3的状态值可根据顶点2最新的状态值进行更新。

所述线性更新策略如下所示，线性更新策略对每个batch上的所有图数据进行线性查询。

所述二分更新策略如下所示，二分更新策略采用二分查找算法进行实现。

上述实施例只为说明本发明的技术构思及特点，其目的在于让熟悉此项技术的人能够了解本发明的内容并据以实施，并不能以此限制本发明的保护范围。凡根据本发明主要技术方案的精神实质所做的修饰，都应涵盖在本发明的保护范围之内。