公开(公告)号：CN115049103A

公开(公告)日：2022-09-13

申请号：CN202210521780.9

申请日：2022-05-13

Applicant: 中国科学院计算技术研究所

Inventor： 张婕 ,  张园 ,  曹华伟 ,  安学军 ,  叶笑春

IPC: G06Q10/04

Abstract: 本发明提供了一种遍历图数据的方法，包括：获取待处理的图数据；获取处理器中线程的线程数量，根据线程数量和图数据中的节点数量将图数据的列数组记录的所有节点按节点编号均衡地分给各线程，得到多个第一子图；对各第一子图，分别以行数组记录的每个节点为排序单位，根据节点的邻边的权重大小将各邻边重新排序得到第二子图，确定每个第二子图中行数组记录的各个节点的轻边数量；由各线程基于改进的德尔塔步进算法和选定的根节点对相应的第二子图进行图遍历，该算法在对相应节点的轻边或者重边进行遍历时，根据相应节点的轻边数量在第二子图中确定该节点的轻边或者重边所在位置；根据所有线程的第二子图的子遍历结果，得到图数据的遍历结果。

公开(公告)号：CN118172230A

公开(公告)日：2024-06-11

申请号：CN202410341779.7

申请日：2024-03-25

Applicant: 中国科学院计算技术研究所

Inventor： 孙一鸣 ,  张婕 ,  曹华伟 ,  张园 ,  安学军 ,  叶笑春

IPC: G06T1/20 ,  G06T1/60 ,  G06F16/11 ,  G06F16/16 ,  G06F16/176

Abstract: 本发明提供一种基于CPU‑GPU协同计算的并发动态图快照处理方法，包括：步骤S1、通过CPU获取动态图快照数据，其包括多张图快照，每张图快照包括多条边、每条边的源节点和目的节点；步骤S2、通过CPU对所述数据进行预处理，得到所有图快照间的共享分区子图和每张图快照的不共享分区子图，共享分区子图和不共享分区子图均包括多个源节点和每个源节点的多条出边；步骤S3、通过CPU和GPU相互配合处理所有图快照的不共享分区子图和所述共享分区子图，包括通过CPU并发执行多个图计算算法处理所述不共享分区子图的多个源节点各自的多条出边，以及通过GPU并发执行多个图计算算法处理所述共享分区子图的多个源节点各自的多条出边，得到每条出边对应的目的节点的属性值。

公开(公告)号：CN115049103B

公开(公告)日：2024-09-24

申请号：CN202210521780.9

申请日：2022-05-13

Applicant: 中国科学院计算技术研究所

Inventor： 张婕 ,  张园 ,  曹华伟 ,  安学军 ,  叶笑春

IPC: G06Q10/047 ,  G06F9/50

Abstract: 本发明提供了一种遍历图数据的方法，包括：获取待处理的图数据；获取处理器中线程的线程数量，根据线程数量和图数据中的节点数量将图数据的列数组记录的所有节点按节点编号均衡地分给各线程，得到多个第一子图；对各第一子图，分别以行数组记录的每个节点为排序单位，根据节点的邻边的权重大小将各邻边重新排序得到第二子图，确定每个第二子图中行数组记录的各个节点的轻边数量；由各线程基于改进的德尔塔步进算法和选定的根节点对相应的第二子图进行图遍历，该算法在对相应节点的轻边或者重边进行遍历时，根据相应节点的轻边数量在第二子图中确定该节点的轻边或者重边所在位置；根据所有线程的第二子图的子遍历结果，得到图数据的遍历结果。

公开(公告)号：CN117851015A

公开(公告)日：2024-04-09

申请号：CN202410033218.0

申请日：2024-01-09

Applicant: 中国科学院计算技术研究所

Inventor： 张园 ,  曹华伟 ,  张婕 ,  孙一鸣 ,  安学军 ,  叶笑春

IPC: G06F9/48 ,  G06F9/50 ,  G06T1/20

Abstract: 本发明提供了一种应用多GPU协同进行单源最短路径计算方法，包括步骤：S1、获取原始的第一图数据和预设的步进增量，根据步进增量预先确定第一图数据中的轻边和重边，构建在不同子图分别存储轻边和重边的局部感知的第二图数据；S2、将所述第二图数据中的轻边和重边均衡划分为N份，并根据每份划分到的轻边和重边，生成在不同子图分别存储轻边和重边的第三图数据，得到N份第三图数据，所述N为参与计算的GPU的数量，N≥2；S3、获取源顶点，由N个GPU读取各自分到的第三图数据，基于德尔塔步进算法协同进行单源最短路径计算，确定源顶点到每个顶点间的最短路径；本发明提升了确定单源最短路径的效率。