Graph computing method and apparatus

Patent metadata

Field	Value
Publication number	US-12411708-B2
Application number	US-202117508294-A
Country	US
Kind code	B2
Filing date	Oct 22, 2021
Priority date	Apr 24, 2019
Publication date	Sep 9, 2025
Grant date	Sep 9, 2025

Abstract

This application discloses a graph computing method and apparatus that support concurrent graph computing using a plurality of algorithms. A plurality of subgraphs of a graph are loaded into a plurality of computing units, and the plurality of computing units executes a plurality of algorithms in parallel, so that the same graph can be shared by the plurality of algorithms, and the plurality of algorithms can be executed in parallel on the same graph. In this way, the delay caused when one algorithm needs to executed after execution of another algorithm ends is avoided. The overall efficiency of performing graph computing is improved, and the overall time of performing graph computing is reduced.

First claim

What is claimed is:

1. A graph computing method, wherein the method comprises:
receiving at least one computing request to compute a graph by using a plurality of algorithms;
loading a plurality of subgraphs of the graph that are in at least one modality into a plurality of computing units, wherein the at least one modality comprises an incoming edge modality or an outgoing edge modality, the incoming edge modality indicates an incoming edge relationship between a first vertex and a second vertex in the plurality of subgraphs, the first vertex is different from the second vertex, the outgoing edge modality indicates an outgoing edge relationship between a third vertex and a fourth vertex in the plurality of subgraphs, and the third vertex is different from the fourth vertex;
obtaining at least one task in each algorithm of the plurality of algorithms, the at least one task comprising a gather task or a scatter task; and
executing the gather task in at least a first algorithm and a second algorithm, of the plurality of algorithms, in parallel based on a first subgraph in the incoming edge modality, wherein the loaded plurality of subgraphs comprise the first subgraph; executing the scatter task in at least a third algorithm and a fourth algorithm, in the plurality of algorithms, in parallel on a second subgraph in the outgoing edge modality, wherein the loaded plurality of subgraphs comprise the second subgraph.

2. The method according to claim 1 , wherein the obtaining the at least one task in each algorithm comprises at least one of the following:
classifying at least one step corresponding to a same function name in the algorithm into a first task based on a function name corresponding to each step in the algorithm;
classifying steps of a same execution body in the algorithm into a second task based on an execution body of each step in the algorithm;
classifying steps with a same access sequence in the algorithm into a third task based on an access sequence for vertices or edges on the graph in each step in the algorithm;
classifying steps, in the algorithm, in which a same vertex or a same edge is accessed into a fourth task based on a vertex or an edge that is on the graph and that is accessed in each step in the algorithm;
classifying steps of a same action in the algorithm into a fifth task based on an action executed in each step in the algorithm;
classifying steps that belong to a same iteration process in the algorithm into a sixth task based on an iteration process to which each step in the algorithm belongs; or
classifying steps that belong to a same algorithm into a seventh task based on a determining branch to which each step in the determining branch in the algorithm belongs.

3. The method according to claim 1 , wherein the method further comprises:
obtaining priorities of the plurality of algorithms based on quantities of iterations of the plurality of algorithms;
obtaining a scheduling scheme based on a priority of each algorithm, wherein the scheduling scheme is used to indicate a correspondence between at least one target task and at least one target subgraph, the target task is a task that is currently scheduled in the tasks in the plurality of algorithms, and the target subgraph is a subgraph that is currently scheduled in the plurality of subgraphs; and
executing the at least one target task in parallel by using a second plurality of computing units into which the at least one target subgraph is loaded.

4. The method according to claim 1 , wherein the method further comprises:
sending a capacity expansion request, wherein the capacity expansion request is used to request to expand capacities of the plurality of computing units;
receiving a capacity expansion indication, wherein the capacity expansion indication is used to indicate to expand the capacities of the plurality of computing units;
creating at least one additional computing unit;
copying a third subgraph of the plurality of subgraphs of the graph to obtain an instance of the third subgraph;
loading the instance of the third subgraph into the created at least one additional computing unit; and
executing the plurality of algorithms in parallel by using the created at least one additional computing unit.

5. The method according to claim 4 , wherein the copying at least the third subgraph of the plurality of subgraphs of the graph comprises:
counting a quantity of times that the third subgraph is requested by the plurality of algorithms; and
copying the third subgraph based on the quantity of times that it is requested reaching a threshold.

6. The method of claim 4 , wherein the first subgraph and the third subgraph are the same subgraph.

7. The method of claim 4 , wherein the second subgraph and the third subgraph are the same subgraph.

8. The method of claim 2 , wherein the first task is an apply task.

9. A graph computing apparatus, comprising a processor and a memory, wherein the memory stores at least one instruction that is loaded and executed by the processor to implement a method comprising:
receiving at least one computing request to compute a graph by using a plurality of algorithms;
loading a plurality of subgraphs of the graph that are in at least one modality into a plurality of computing units, wherein the at least one modality comprises an incoming edge modality or an outgoing edge modality, the incoming edge modality indicates an incoming edge relationship between a first vertex and a second vertex in the plurality of subgraphs, the first vertex is different from the second vertex, the outgoing edge modality indicates an outgoing edge relationship between a third vertex and a fourth vertex in the plurality of subgraphs, and the third vertex is different from the fourth vertex;
obtaining at least one task in each algorithm of the plurality of algorithms, the at least one task comprising a gather task or a scatter task; and
executing the gather task in at least a first algorithm and a second algorithm, of the plurality of algorithms, in parallel on a first subgraph in the incoming edge modality, wherein the loaded plurality of subgraphs comprise the first subgraph; executing the scatter task in at least a third algorithm and a fourth algorithm, in the plurality of algorithms, in parallel based on a second subgraph in the outgoing edge modality, wherein the loaded plurality of subgraphs comprise the second subgraph, by using the plurality of computing units.

10. The apparatus according to claim 9 , wherein the obtaining the at least one task in each algorithm comprises at least one of the following:
classifying at least one step corresponding to a same function name in the algorithm into a first task based on a function name corresponding to each step in the algorithm;
classifying steps of a same execution body in the algorithm into a second task based on an execution body of each step in the algorithm;
classifying steps with a same access sequence in the algorithm into a third task based on an access sequence for vertices or edges on the graph in each step in the algorithm;
classifying steps, in the algorithm, in which a same vertex or a same edge is accessed into a fourth task based on a vertex or an edge that is on the graph and that is accessed in each step in the algorithm;
classifying steps of a same action in the algorithm into a fifth task based on an action executed in each step in the algorithm;
classifying steps that belong to a same iteration process in the algorithm into a sixth task based on an iteration process to which each step in the algorithm belongs; or
classifying steps that belong to a same algorithm into a seventh task based on a determining branch to which each step i

Assignees

• Huawei Cloud Computing Tech Co Ltd

Inventors

• Xia Yinglong
• Zhang Chenyi
• Fang Yang

Classifications

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title