一种基于GRAPE框架的图算法并行加速方法和装置

摘要

本申请提供了一种基于GRAPE框架的图算法并行加速方法和装置，所述方法包括：获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型；获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果；可以把串行的图算法迁移到GRAPE框架，并保证迁移后的算法加速比足够高。

说明书

技术领域

本申请涉及数据处理领域，特别是一种基于GRAPE框架的图算法并行加速方法和装置。

背景技术

分布式计算是一种重要的算法加速技术。分布式计算将该应用分解成许多小的部分，分配给多台计算机进行处理，不同的计算机之间通过信道传递信息。这样可以节约整体计算时间，大大提高计算效率。目前已经有很多成熟的用于大规模数据集的分布式计算的编程框架，如MapReduce、Hadoop、Spark、GRAPE等等。其中，GRAPE框架是一种新的专门针对图数据的分布式计算框架。该计算框架由数据库领域著名科学家、英国皇家科学院院士樊文飞提出，相关工作获得了2016年数据库领域顶会SIGMOD的最佳论文奖，在国际上拥有巨大的影响力。

GRAPE框架是针对图数据的分布式计算框架。令Q为查询的集合，给定图G和某个查询Q∈Q，GRAPE框架计算结果为Q(G)。每个GRAPE框架所使用的节点包含两类，一个主节点P

目前没有基于GRAPE框架的串行算法并行加速方案；虽然很多重要的图算法都存在着PRAM并行算法，但没有一种通用的方案，将PRAM算法迁移到GRAPE框架上。

发明内容

鉴于所述问题，提出了本申请以便提供克服所述问题或者至少部分地解决所述问题的一种基于GRAPE框架的图算法并行加速方法和一种基于GRAPE框架的图算法并行加速装置，所述方法包括：

获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；

获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；

依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；

获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

进一步地，所述获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值的步骤，包括：

依据所述CPU个数k确认所述目标模型的工作节点个数n；其中，所述目标模型包括一个所述主节点和若干个所述工作节点，若干个所述工作节点包括P

依据所述输入内存单元的大小l确认目标输入内存单元的大小；

依据所述额外内存单元的大小q确认目标额外内存单元的大小；

依据所述工作节点个数n确认每个工作节点用于传递信息的顶点个数为所述工作节点个数n的两倍，具体地，工作节点P

依据所述工作节点个数、所述目标输入内存单元的大小、所述目标额外内存单元的大小和所述每个工作节点用于传递信息的顶点个数生成所述目标模型。

进一步地，所述获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>的步骤，包括：

获取所述输入数据，并调用所述目标模型内的目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组。

进一步地，所述获取所述输入数据，并调用所述目标模型内的目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组的步骤，包括：

调用所述目标模型内的所述目标工作节点根据所述输入数据在所述索引数组中查询生成数组元素；

依据所述数组元素确定对应所述目标工作节点的编号；

依据所述目标工作节点的编号生成对应于所述目标工作节点的所述初始ID元组；

依据输入数据生成所述访问内存元组。

进一步地，所述依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至满足收敛条件生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；当初始ID元组形式为<0，辅助阶段，i>时进行增量运算的步骤，包括：

依据所述初始ID元组确定工作节点编号i；

依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

生成用于下一次增量计算的所述更新ID元组。

进一步地，所述依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；当初始ID元组形式为时进行增量运算的步骤，包括：

依据所述初始ID元组获取工作节点编号i；

依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

依据所述当前工作节点P

生成用于下一次增量计算的所述更新ID元组。

进一步地，所述依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算生成用于下一次增量运算的更新ID元组；当初始ID元组形式为时进行增量运算的步骤，包括：

依据所述初始ID元组获取工作节点编号i；

依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

依据所述当前工作节点P

生成用于下一次增量计算的所述更新ID元组。

本发明实施例还公开了一种基于GRAPE框架的图算法并行加速装置,所述装置包括：

生成模块，用于获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；

确定模块，用于获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；

最终计算结果模块，用于依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；

运算结果模块，用于获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

本发明实施例还公开了一种设备，包括处理器、存储器及存储在所述存储器上并能够在所述处理器上运行的计算机程序，所述计算机程序被所述处理器执行时实现如上所述的一种基于GRAPE框架的图算法并行加速方法的步骤。

本发明实施例还公开了一种计算机可读存储介质，所述计算机可读存储介质上存储计算机程序，所述计算机程序被处理器执行时实现如上所述的一种基于GRAPE框架的图算法并行加速方法的步骤。

本申请具有以下优点：

在本申请的实施例中，通过获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

可以把串行的图算法迁移到GRAPE框架，并保证迁移后的算法加速比足够高。

附图说明

为了更清楚地说明本申请的技术方案，下面将对本申请的描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1是本申请一实施例提供的一种基于GRAPE框架的图算法并行加速方法的步骤流程图；

图2是本申请一实施例提供的一种基于GRAPE框架的图算法并行加速装置的结构框图；

图3是本发明一实施例提供的一种计算机设备的结构示意图。

具体实施方式

为使本申请的所述目的、特征和优点能够更加明显易懂，下面结合附图和具体实施方式对本申请作进一步详细的说明。显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

需要说明的是，在本发明任一实施例中，GRAPE框架是针对图数据的分布式计算框架。令Q为查询的集合，给定图G和某个查询Q∈Q，GRAPE框架计算结果为Q(G)。每个GRAPE框架所使用的节点包含两类，一个主节点P

一个GRAPE框架主要包含三个阶段，分别是部分计算、增量计算和终止阶段。

(1)部分计算：此阶段，每个工作节点P

(2)增量计算：此阶段，GRAPE框架反复执行如下步骤，直至终止。

(2.a)主节点：主节点搜集从工作节点传递来的信息。并将所有目标节点是P

(2.b)工作节点：接收到信息M

(3)终止阶段：主节点P

由工作节点P

把GRAPE框架执行一次函数PEval、函数IncEval或者函数Assemble称为GRAPE框架的一个超步。GRAPE框架最终的运行时间为∑

PRAM(Parallel Random Access Machine)模型是多指令流多数据流并行机中的一种具有共享存储的模型。PRAM模型的每一步包含如下三个阶段：(1)从共享内存单元中读取某个数据；(2)执行运算；(3)将数据写入某个共享内存单元。

参照图1，示出了本申请一实施例提供的一种基于GRAPE框架的图算法并行加速方法的步骤流程图；

所述方法包括：

步骤S110、获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU(central processing unit，中央处理器)个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID(Identity document，身份标识号)信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；

步骤S120、获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；

步骤S130、依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时确定工作节点所执行的具体操作，并生成用于下一次增量运算的更新ID元组；

步骤S140、获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

在本申请的实施例中，通过获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时确定工作节点所执行的具体操作，并生成用于下一次增量运算的更新ID元组；获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

可以把串行的图算法迁移到GRAPE框架上，并保证迁移后的算法加速比足够高。

下面，将对本示例性实施例中一种基于GRAPE框架的图算法并行加速方法作进一步地说明。

如所述步骤S110所述，获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值。

在本发明一实施例中，可以结合下列描述进一步说明步骤S110所述“获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值”的具体过程。

如下列步骤所述，

步骤S1101，依据所述CPU个数k确认所述目标模型的工作节点个数n；其中，所述目标模型包括一个所述主节点和若干个所述工作节点，若干个所述工作节点包括P

步骤S1102，依据所述输入内存单元的大小l确认目标输入内存单元的大小；

步骤S1103，依据所述额外内存单元的大小q确认目标额外内存单元的大小；

步骤S1104，依据所述工作节点个数n确认每个工作节点用于传递信息的顶点个数为所述工作节点个数n的两倍，具体地，工作节点P

步骤S1105，依据所述工作节点个数、所述目标输入内存单元的大小、所述目标额外内存单元的大小和所述每个工作节点用于传递信息的顶点个数生成所述目标模型。

需要说明的是，通过模拟PRAM模型，构造基于GRAPE框架的目标模型。

作为一种示例，PRAM模型的工作节点为CPU，模拟PRAM模型使用k个CPU(CentralProcessing Unit，中央处理器)，对应的基于GRAPE框架的目标模型运行在1个主节点P

作为一种示例，模拟PRAM模型使用的内存分为两部分，用来存储输入的内存单元，大小为l；以及用来进行计算的额外内存单元，大小为q；不失一般性，假设k、l、q都是n的倍数。

作为一种示例，用编号来标识某个具体的CPU或者内存单元，如PRAM模型的额外内存j表示PRAM模型使用的第j号额外内存单元。

作为一种示例，用f(t)表示函数

作为一种示例，用λ(t)表示

作为一种示例，基于GRAPE框架的目标模型的每个工作节点模拟PRAM模型的k/n个CPU。如果PRAM模型的第t号CPU执行了某个运算，则目标模型的工作节点P

作为一种示例，基于GRAPE框架的目标模型的输入包含三部分，PRAM模型的输入，图G

在函数PEval中，这些输入将被重新分配，使得输入(j,d

为了便于在不同的工作节点之间通信，除了输入(1,d

索引数组D

作为一种示例，目标模型的每个工作节点除了存储输入的内存单元之外，还额外使用q/n个内存单元。我们用二元组[i,j]表示工作节点Pi所使用的第j个额外内存单元。PRAM模型的额外内存s由目标模型的额外内存[h(s),λ(s)]来模拟。

作为一种示例，当PRAM模型的t号CPU访问了输入d

作为一种示例，当PRAM模型的t号CPU访问了额外内存s，则目标模型的工作节点P

作为一种示例，目标模型通过函数PEval和函数IncEval来实现PRAM模型的不同指令。函数PEval从输入的索引数组D

作为一种示例，目标模型通过内存访问元组来模拟PRAM模型的内存读写操作；目标模型用内存访问元组来编码PRAM模型的内存读写操作，并将这些元组作为目标模型的更新参数。在执行函数PEval和函数IncEval之后，工作节点把更新参数发送给主节点P

作为一种示例，目标模型通过执行两次函数IncEval来模拟PRAM模型的一步。

如所述步骤S120所述获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>。

在本发明一实施例中，可以结合下列描述进一步说明步骤S120所述“获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>”的具体过程。

如下列步骤所述，

步骤S1201，获取所述输入数据，并调用所述目标模型内的所述目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组。

需要说明的是，目标模型的更新参数主要包含两个部分，分别为ID元组和内存访问元组。ID元组形式为<步数编号，阶段，工作节点编号>，其中步数编号编码当前PRAM模型运行了多少步，阶段包括计算阶段和辅助阶段，工作节点编号编码工作节点的ID。内存访问元组形式为<操作-段，地址，数据>，其中操作-段包括传递-输入、读-输入、读-额外和写-额外；其中，传递-输入是指在函数PEval中，目标模型将输入(1,d

如下列步骤S1201所述，获取所述输入数据，并调用所述目标模型内的所述目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组；

在本发明一实施例中，可以结合下列描述进一步说明步骤S1201所述“获取所述输入数据，并调用所述目标模型内的所述目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组”的具体过程。

如下列步骤所述，

步骤S12011，调用所述目标模型内的所述目标工作节点根据所述输入数据在所述索引数组中查询生成数组元素；

步骤S12012，依据所述数组元素确定对应所述目标工作节点的编号；

步骤S12013，依据所述目标工作节点的编号生成对应于所述目标工作节点的所述初始ID元组；

步骤S12014，依据输入数据生成所述访问内存元组。

需要说明的是，函数PEval初始化更新参数中的ID元组，并通过设置内存访问元组，来实现输入(1,d

作为一种示例，步骤S12014，依据输入数据生成所述访问内存元组，依据输入数据生成所述访问内存元组，具体的，工作节点P

作为一种示例，调用目标模型内的目标工作节点P

如下列步骤S130所述，依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时确定工作节点所执行的具体操作，并生成用于下一次增量运算的更新ID元组；

在本发明一实施例中，可以结合下列描述进一步说明步骤S130所述“当初始ID元组形式为<0，辅助阶段，i>时进行增量运算”的具体过程。

如下列步骤所述，

步骤S13011，依据所述初始ID元组确定工作节点编号i；

步骤S13012，依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

步骤S13013，生成用于下一次增量计算的所述更新ID元组。

作为一种示例，初始ID元组是<0，辅助阶段，i>时，函数IncEval从更新参数的内存访问元组中读取出输入，并为PRAM模型的第一步的读取做准备；

通过查询初始ID元组获得i，工作节点P

如下列步骤S130所述，依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时确定工作节点所执行的具体操作，并生成用于下一次增量运算的更新ID元组；

在本发明一实施例中，可以结合下列描述进一步说明步骤S130所述“当初始ID元组形式为时进行增量运算”的具体过程。

如下列步骤所述，

步骤S13021，依据所述初始ID元组获取工作节点编号i；

步骤S13022，依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

步骤S13023，依据所述当前工作节点P

步骤S13024，生成用于下一次增量计算的所述更新ID元组。

作为一种示例，初始ID元组是，其中r≥1，则函数IncEval实现PRAM模型在第r步中的相应操作；

通过查询初始ID元组获得r和i，工作节点P

具体地，数据D在这一个超步之前已经被存储到

如下列步骤S130所述，依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时确定工作节点所执行的具体操作，并生成用于下一次增量运算的更新ID元组；

在本发明一实施例中，可以结合下列描述进一步说明步骤S130所述“当初始ID元组形式为时进行增量运算”的具体过程。

如下列步骤所述，

步骤S13031，依据所述初始ID元组获取工作节点编号i；

步骤S13032，依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

步骤S13033，依据所述当前工作节点P

步骤S13034，生成用于下一次增量计算的所述更新ID元组。

作为一种示例，初始ID元组是，其中r≥1，则函数IncEval完成PRAM模型在第r步中的写操作，并为第r+1步中的读操作做准备；工作节点P

具体地，数据D在这一个超步之前已经被存储到了

需要说明的是，在每一个超步的结尾，目标工作节点P

如下列步骤S140所述，获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果；

在本发明一实施例中，可以结合下列描述进一步说明步骤S140所述“获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果”的具体过程。

需要说明的是，主节点P

本发明的有益效果为：基于PRAM模型的图算法都可以迁移到GRAPE框架下，并且如果原PRAM模型在m个CPU上的运行时间为T，GRAPE框架下的算法在n≤m个工作节点上的运行时间至多为

对于装置实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

参照图2，示出了本申请一实施例提供的一种基于GRAPE框架的图算法并行加速的结构框图；

具体包括：

生成模块210，用于获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；

确定模块220，用于获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；

最终计算结果模块230，用于依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；

运算结果模块240，用于获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

在本发明的一种实施例中，所述生成模块210，包括：

第一确认子模块，用于依据所述CPU个数k确认所述目标模型的工作节点个数n；其中，所述目标模型包括一个所述主节点和若干个所述工作节点，若干个所述工作节点包括P

第二确认子模块，用于依据所述输入内存单元的大小l确认目标输入内存单元的大小；

第三确认子模块，用于依据所述额外内存单元的大小q确认目标额外内存单元的大小；

第四确认子模块，用于依据所述工作节点个数n确认每个工作节点用于传递信息的顶点个数为所述工作节点个数n的两倍，具体地，工作节点P

第一生成子模块，用于依据所述工作节点个数、所述目标输入内存单元的大小、所述目标额外内存单元的大小和所述每个工作节点用于传递信息的顶点个数生成所述目标模型。

在本发明的一种实施例中，所述确定模块220，包括：

第二生成子模块，用于获取所述输入数据，并调用所述目标模型内的所述目标工作节点以及所述索引数组对所述输入数据进行部分计算，生成所述初始ID元组和所述内存访问元组。

在本发明的一种实施例中，所述第二生成子模块，包括：

第一生成单元，用于调用所述目标模型内的所述目标工作节点根据所述输入数据在所述索引数组中查询生成数组元素；

第二生成单元，用于依据所述数组元素确定对应所述目标工作节点的编号；

第三生成单元，用于依据所述目标工作节点的编号生成对应于所述目标工作节点的所述初始ID元组；

第四生成单元，用于依据输入数据生成所述访问内存元组。

在本发明的一种实施例中，所述最终计算结果模块230，包括：

第五确认子模块，用于依据所述初始ID元组确定工作节点编号i；

第一确定子模块，用于依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

第三生成子模块，用于生成用于下一次增量计算的所述更新ID元组。

在本发明的一种实施例中，所述最终计算结果模块230，包括：

第一获取子模块，用于依据所述初始ID元组获取工作节点编号i；

第二确定子模块，用于依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

第一读取子模块，用于依据所述当前工作节点P

第四生成子模块，用于生成用于下一次增量计算的所述更新ID元组。

在本发明的一种实施例中，所述最终计算结果模块230，包括：

第二获取子模块，用于依据所述初始ID元组获取工作节点编号i；

第三确定子模块，用于依据所述工作节点编号i确定对应于所述工作节点编号i的当前工作节点P

第二读取子模块，用于依据所述当前工作节点P

第五生成子模块，用于生成用于下一次增量计算的所述更新ID元组。

参照图3，示出了本发明的一种基于GRAPE框架的图算法并行加速方法的计算机设备，具体可以包括如下：

上述计算机设备12以通用计算设备的形式表现，计算机设备12的组件可以包括但不限于：一个或者多个处理器或者处理单元16，系统存储器28，连接不同系统组件(包括系统存储器28和处理单元16)的总线18。

总线18表示几类总线18结构中的一种或多种，包括存储器总线18或者存储器控制器，外围总线18，图形加速端口，处理器或者使用多种总线18结构中的任意总线18结构的局域总线18。举例来说，这些体系结构包括但不限于工业标准体系结构(ISA)总线18，微通道体系结构(MAC)总线18，增强型ISA总线18、音视频电子标准协会(VESA)局域总线18以及外围组件互连(PCI)总线18。

计算机设备12典型地包括多种计算机系统可读介质。这些介质可以是任何能够被计算机设备12访问的可用介质，包括易失性和非易失性介质，可移动的和不可移动的介质。

系统存储器28可以包括易失性存储器形式的计算机系统可读介质，例如随机存取存储器(RAM)30和/或高速缓存存储器32。计算机设备12可以进一步包括其他移动/不可移动的、易失性/非易失性计算机体统存储介质。仅作为举例，存储系统34可以用于读写不可移动的、非易失性磁介质(通常称为“硬盘驱动器”)。尽管图3中未示出，可以提供用于对可移动非易失性磁盘(如“软盘”)读写的磁盘驱动器，以及对可移动非易失性光盘(例如CD-ROM，DVD-ROM或者其他光介质)读写的光盘驱动器。在这些情况下，每个驱动器可以通过一个或者多个数据介质界面与总线18相连。存储器可以包括至少一个程序产品，该程序产品具有一组(例如至少一个)程序模块42，这些程序模块42被配置以执行本发明各实施例的功能。

具有一组(至少一个)程序模块42的程序/实用工具40，可以存储在例如存储器中，这样的程序模块42包括——但不限于——操作系统、一个或者多个应用程序、其他程序模块42以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。程序模块42通常执行本发明所描述的实施例中的功能和/或方法。

计算机设备12也可以与一个或多个外部设备14(例如键盘、指向设备、显示器24、摄像头等)通信，还可与一个或者多个使得医护人员能与该计算机设备12交互的设备通信，和/或与使得该计算机设备12能与一个或多个其他计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这种通信可以通过输入/输出(I/O)界面22进行。并且，计算机设备12还可以通过网络适配器20与一个或者多个网络(例如局域网(LAN))，广域网(WAN)和/或公共网络(例如因特网)通信。如图所示，网络适配器20通过总线18与计算机设备12的其他模块通信。应当明白，尽管图3中未示出，可以结合计算机设备12使用其他硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元16、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统34等。

处理单元16通过运行存储在系统存储器28中的程序，从而执行各种功能应用以及数据处理，例如实现本发明实施例所提供的基于GRAPE框架的图算法并行加速方法。

也即，上述处理单元16执行上述程序时实现：获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

在本发明实施例中，本发明还提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如本申请所有实施例提供的基于GRAPE框架的图算法并行加速方法：

也即，给程序被处理器执行时实现：获取PRAM模型的参数信息，并根据所述PRAM模型的参数信息构建生成目标模型，其中，所述目标模型包括索引数组、一个主节点和若干个工作节点，且工作节点数量小于或等于所述PRAM模型中的CPU的数量；具体地，所述参数信息至少包括CPU个数k、输入内存单元的大小l、额外内存单元的大小q、数据ID信息和PRAM模型执行信息；所述数据ID信息用于获取数据集内的数据对应的ID值；获取输入数据，并依据所述目标模型中的所述索引数组对所述输入数据进行运算，确定初始ID元组和内存访问元组；其中，ID元组形式为<步数编号，阶段，工作节点编号>；内存访问元组形式为<操作-段，地址，数据>；依据所述初始ID元组和所述输入数据进行增量运算，迭代运算直至所有工作节点均不再接收来自其他工作节点的参数信息时生成最终计算结果；具体地，依据所述初始ID元组的所述步数编号、所述阶段和所述工作节点编号在每一次增量运算时生成用于下一次增量运算的更新ID元组；获取所述最终计算结果内所有工作节点的计算结果，并依据所述所有工作节点的计算结果汇总生成所述运算结果。

可以采用一个或多个计算机可读的介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质例如可以是——但不限于——电、磁、光、电磁、红外线或半导体的系统、装置或器件，或者任意以上的组合。计算机可读存储介质的更具体的例子(非穷举的列表)包括：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机存取存储器(RAM)、只读存储器(ROM)、可擦可编程只读存储器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件或者上述的任意合适的组合。在本文件中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。

计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括——但不限于——电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。

可以以一种或多种程序设计语言或其组合来编写用于执行本发明操作的计算机程序代码，上述程序设计语言包括面向对象的程序设计语言——诸如Java、Smalltalk、C++，还包括常规的过程式程序设计语言——诸如“C”语言或类似的程序设计语言。程序代码可以完全地在医护人员计算机上执行、部分地在医护人员计算机上执行、作为一个独立的软件包执行、部分在医护人员计算机上部分在远程计算机上执行或者完全在远程计算机或者服务器上执行。在涉及远程计算机的情形中，远程计算机可以通过任意种类的网络——包括局域网(LAN)或广域网(WAN)——连接到医护人员计算机，或者，可以连接到外部计算机(例如利用因特网服务提供商来通过因特网连接)。本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。

尽管已描述了本申请实施例的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本申请实施例范围的所有变更和修改。

最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。

以上对本申请所提供的一种基于GRAPE框架的图算法并行加速方法和装置，进行了详细介绍，本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。