Method and apparatus for assigning computing task

Patent metadata

Field	Value
Publication number	US-11210131-B2
Application number	US-201916669134-A
Country	US
Kind code	B2
Filing date	Oct 30, 2019
Priority date	Mar 8, 2019
Publication date	Dec 28, 2021
Grant date	Dec 28, 2021

Abstract

Embodiments of the present disclosure relate to a method and apparatus for assigning a computing task. The method includes: segmenting, based on a computing resource required for a computing task of a graph, the graph into a subgraph set; determining, based on a computing resource required for a computing task of a subgraph in the subgraph set, whether a node in a node cluster is adapted to the subgraph in the subgraph set; assigning, in response to determining the node in the node cluster being adapted to the subgraph in the subgraph set, the computing task of the subgraph in the subgraph set to the node adapted to the subgraph in the subgraph set, to compute the subgraph; and synthesizing a computing result of the graph based on a computing result of each subgraph in the subgraph set.

First claim

The invention claimed is:

1. A method for assigning a computing task, comprising:
segmenting, based on a computing resource required for a computing task of a graph, the graph into a subgraph set;
determining, based on a computing resource required for a computing task of a subgraph in the subgraph set, whether a node in a node cluster is adapted to the subgraph in the subgraph set, wherein subgraphs in the subgraph set do not have a same vertex or edge with each other, and a number of computing tasks of the subgraph in the subgraph set is less than or equal to a maximum number of logical CPUs corresponding to the node cluster;
assigning, in response to determining the node in the node cluster being adapted to the subgraph in the subgraph set, the computing task of the subgraph in the subgraph set to the node adapted to the subgraph in the subgraph set, to compute the subgraph; and
synthesizing a computing result of the graph based on a computing result of each subgraph in the subgraph set.

2. The method according to claim 1 , wherein a number of idle logical CPUs of the node adapted to the subgraph in the subgraph set is equal to the number of computing tasks of the subgraph in the subgraph set, and an idle memory of the node adapted to the subgraph in the subgraph set is greater than or equal to a memory required to load metadata of the subgraph in the subgraph set.

3. The method according to claim 2 , wherein the determining, based on a computing resource required for a computing task of a subgraph in the subgraph set, whether a node in a node cluster is adapted to the subgraph in the subgraph set comprises:
enqueuing an identifier of each subgraph in the subgraph set, to generate a subgraph queue;
executing following adapting: querying, for a subgraph corresponding to a queue head element of the subgraph queue, a node resource state table based on the computing resource required for the computing task of the subgraph, and determining whether a node in the node cluster is adapted to the subgraph, wherein the node resource state table is configured to record a resource state of the node in the node cluster, and the resource state comprises the number of idle logical CPUs and a size of the idle memory; and
dequeuing the queue head element, in response to determining the node being adapted to the subgraph, and continuing to execute the adapting.

4. The method according to claim 3 , wherein the enqueuing an identifier of each subgraph in the subgraph set, to generate a subgraph queue comprises:
enqueuing identifiers of the subgraphs in the subgraph set successively based on priorities of the computing tasks or the number of computing tasks, to generate the subgraph queue.

5. The method according to claim 3 , wherein the method further comprises:
querying, in response to determining no node in the node cluster being adapted to the subgraph, the node resource state table in ascending order of the number of idle logical CPUs, and determining whether a node in the node cluster has the number of idle logical CPUs greater than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, wherein an ascending upper limit of the number of idle logical CPUs is the maximum number of logical CPUs corresponding to the node cluster; and
assigning, in response to determining the node having the number of idle logical CPUs greater than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, the computing tasks of the subgraph to the node having the number of idle logical CPUs greater than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, to compute the subgraph, dequeuing the queue head element, and continuing to execute the adapting.

6. The method according to claim 5 , wherein the method further comprises:
querying, in response to determining no node having the number of idle logical CPUs greater than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, the node resource state table in descending order of the number of idle logical CPUs, and determining whether a node in the node cluster has the number of idle logical CPUs less than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, wherein a descending lower limit of the number of idle logical CPUs is 1; and
assigning, in response to determining the node having the number of idle logical CPUs less than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, the computing tasks of the subgraph to the node having the number of idle logical CPUs less than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, to compute the subgraph, dequeuing the queue head element, and continuing to execute the adapting.

7. The method according to claim 3 , wherein the method further comprises:
updating the resource state of the node in the node cluster in the node resource state table after the node in the node cluster is selected or when the computing tasks of the subgraph are completed.

8. The method according to claim 7 , wherein the method further comprises:
continuing to execute the adapting, in response to determining no node having the number of idle logical CPUs less than the number of computing tasks of the subgraph, and the idle memory greater than or equal to the memory required to load the metadata of the subgraph, and after updating the node resource state table.

9. An apparatus for assigning a computing task, comprising:
at least one processor; and
a memory storing instructions, the instructions when executed by the at least one processor, cause the at least one processor to perform operations, the operations comprising:
segmenting, based on a computing resource required for a computing task of a graph, the graph into a subgraph set;
determining, based on a computing resource required for a computing task of a subgraph in the subgraph set, whether a node in a node cluster is adapted to the subgraph in the subgraph set, wherein subgraphs in the subgraph set do not have a same vertex or edge with each other, and a number of computing tasks of the subgraph in the subgraph set is less than or equal to a maximum number of logical CPUs corresponding to the node cluster;
assigning, in response to determining the node in the node cluster being adapted to the subgraph in the subgraph set, the computing task of the subgraph in the subgraph set to the node adapted to the subgraph in the subgraph set, to compute the subgraph; and
synthesizing a computing result of the graph based on a computing result of each subgraph in the subgraph set.

10. The apparatus according to claim 9 , wherein a number of idle logical CPUs of the node adapted to the subgraph in the subgraph set is equal to the number of computing tasks of the subgraph in the subgraph set, and an idle memory of the node adapted to the subgraph in the subgraph set is greater than or equal to a memory required to load metadata of the subgraph in the subgraph set.

11. The apparatus according to claim 10 , wherein the determining, based on a computing resource required for a computing task of a subgraph in the subgraph set, whether a node in a node c

Assignees

• Beijing Baidu Netcom Sci & Tech Co Ltd

Inventors

• Lu Wenxiang
• Li Yuming
• Wang Yunlong

Classifications

• G06F9/5072

  Grid computing · CPC title

• G06F2209/5017

  Task decomposition · CPC title

• G06F9/5005

  to service a request · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/5016

  the resource being the memory · CPC title