# US 2021/0342184 A1 · Method, electronic device, and computer program product for processing computing job

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0342184 A1
- Document ID: US20210342184A1
- Status: Published application
- Kind: A1
- Application number: 16/887,573
- Filed: 2020-05-29
- Published: 2021-11-04
- Earliest claimed: 2020-04-29
- Assignees: EMC IP Holding Company LLC
- Applicants: EMC IP Holding Company LLC
- Inventors: Jinpeng Liu; Jin Li
- Web page: https://patentgrep.com/patent/US20210342184A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5061: {Partitioning or combining of resources}
- G06F 9/3838: {Dependency mechanisms, e.g. register scoreboarding}
- G06F 9/5083: {Techniques for rebalancing the load in a distributed system}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments disclosed herein provide a method, an electronic device, and a computer program product for processing a computing job. The method includes determining a first dependency relationship between a plurality of computing tasks included in a to-be-processed computing job. The method further includes determining, based on the first dependency relationship and demands of the plurality of computing tasks for computing resources, a group of computing tasks for combination from the plurality of computing tasks. The method further includes combining the group of computing tasks into a target computing task. The method further includes determining, based on the first dependency relationship, a second dependency relationship between the target computing task and computing tasks that are other than the group of computing tasks in the plurality of computing tasks. The embodiments according to the present disclosure can reduce data movement during processing of a computing job, and are beneficial to load balancing.

## Claims

### Claim 1

A method for processing a computing job, comprising:
determining a first dependency relationship between a plurality of computing tasks included in a to-be-processed computing job;
determining, based on the first dependency relationship and demands of the plurality of computing tasks for computing resources, a group of computing tasks for combination from the plurality of computing tasks;
combining the group of computing tasks into a target computing task; and
determining, based on the first dependency relationship, a second dependency relationship between the target computing task and computing tasks that are other than the group of computing tasks in the plurality of computing tasks.

### Claim 2 (depends on 1)

The method according to claim 1, wherein determining the group of computing tasks from the plurality of computing tasks comprises:
determining, for each computing task of the plurality of computing tasks and based on the first dependency relationship, the number of computing tasks associated with at least one of an input or an output of a corresponding computing task;
determining a first group of candidate tasks from the plurality of computing tasks, wherein the number determined for each candidate task is less than a threshold number;
determining, based on demands of the first group of candidate tasks for the computing resources, a second group of candidate tasks for combination from the first group of candidate tasks; and
selecting the group of computing tasks from the second group of candidate tasks.

### Claim 3 (depends on 2)

The method according to claim 2, wherein determining the second group of candidate tasks from the first group of candidate tasks comprises:
determining the second group of candidate tasks by removing a candidate task with a demand for the computing resources exceeding a first threshold from the first group of candidate tasks.

### Claim 4 (depends on 2)

The method according to claim 2, wherein selecting the group of computing tasks from the second group of candidate tasks comprises:
determining, based on the first dependency relationship, a first candidate task and a second candidate task in the second group of candidate tasks, wherein the first candidate task does not depend on other candidate tasks in the second group of candidate tasks, and the second candidate task depends on the first candidate task;
estimating a first demand of a first combined task that combines the first candidate task and the second candidate task for the computing resources; and
selecting, if it is determined that the estimated first demand is less than a second threshold, the first candidate task and the second candidate task as at least a part of the group of computing tasks.

### Claim 5 (depends on 4)

The method according to claim 4, further comprising:
estimating, if it is determined that the second group of candidate tasks includes a third candidate task depending on the second candidate task, a second demand of a second combined task that combines the first combined task and the third candidate task for the computing resources; and
adding, if it is determined that the estimated second demand is less than the second threshold, the third candidate task into the group of computing tasks.

### Claim 6 (depends on 4)

The method according to claim 4, further comprising:
determining, if it is determined that a third candidate task depending on the second candidate task is not included in the second group of candidate tasks, the first candidate task and the second candidate task as the group of computing tasks.

### Claim 7 (depends on 1)

The method according to claim 1, wherein determining the first dependency relationship comprises:
obtaining a computation graph representing the computing job, a vertex in the computation graph corresponding to a corresponding computing task among the plurality of computing tasks; and
determining the first dependency relationship from the computation graph.

### Claim 8 (depends on 1)

The method according to claim 1, wherein combining the group of computing tasks into the target computing task comprises:
obtaining a group of generation logics corresponding to the group of computing tasks, each generation logic in the group of generation logics being used for generating an executable instruction for a corresponding computing task; and
combining the group of generation logics into a target logic for generating an executable instruction for the target computing task.

### Claim 9 (depends on 1)

The method according to claim 1, wherein the computing resources comprise at least one of memory resources and thread resources.

### Claim 10

An electronic device, comprising:
a processor; and
a memory coupled to the processor and having instructions stored therein, wherein the instructions, when executed by the processor, cause the device to execute actions comprising:
determining a first dependency relationship between a plurality of computing tasks included in a to-be-processed computing job;
determining, based on the first dependency relationship and demands of the plurality of computing tasks for computing resources, a group of computing tasks for combination from the plurality of computing tasks;
combining the group of computing tasks into a target computing task; and
determining, based on the first dependency relationship, a second dependency relationship between the target computing task and computing tasks that are other than the group of computing tasks in the plurality of computing tasks.

### Claim 11 (depends on 10)

The device according to claim 10, wherein determining the group of computing tasks from the plurality of computing tasks comprises:
determining, for each computing task of the plurality of computing tasks and based on the first dependency relationship, the number of computing tasks associated with at least one of an input or an output of a corresponding computing task;
determining a first group of candidate tasks from the plurality of computing tasks, wherein the number determined for each candidate task is less than a threshold number;
determining, based on demands of the first group of candidate tasks for the computing resources, a second group of candidate tasks for combination from the first group of candidate tasks; and
selecting the group of computing tasks from the second group of candidate tasks.

### Claim 12 (depends on 11)

The device according to claim 11, wherein determining the second group of candidate tasks from the first group of candidate tasks comprises:
determining the second group of candidate tasks by removing a candidate task with a demand for the computing resources exceeding a first threshold from the first group of candidate tasks.

### Claim 13 (depends on 11)

The device according to claim 11, wherein selecting the group of computing tasks from the second group of candidate tasks comprises:
determining, based on the first dependency relationship, a first candidate task and a second candidate task in the second group of candidate tasks, wherein the first candidate task does not depend on other candidate tasks in the second group of candidate tasks, and the second candidate task depends on the first candidate task;
estimating a first demand of a first combined task that combines the first candidate task and the second candidate task for the computing resources; and
selecting, if it is determined that the estimated first demand is less than a second threshold, the first candidate task and the second candidate task as at least a part of the group of computing tasks.

### Claim 14 (depends on 13)

The device according to claim 13, further comprising:
estimating, if it is determined that the second group of candidate tasks includes a third candidate task depending on the second candidate task, a second demand of a second combined task that combines the first combined task and the third candidate task for the computing resources; and
adding, if it is determined that the estimated second demand is less than the second threshold, the third candidate task into the group of computing tasks.

### Claim 15 (depends on 13)

The device according to claim 13, further comprising:
determining, if it is determined that a third candidate task depending on the second candidate task is not included in the second group of candidate tasks, the first candidate task and the second candidate task as the group of computing tasks.

### Claim 16 (depends on 10)

The device according to claim 10, wherein determining the first dependency relationship comprises:
obtaining a computation graph representing the computing job, a vertex in the computation graph corresponding to a corresponding computing task among the plurality of computing tasks; and
determining the first dependency relationship from the computation graph.

### Claim 17 (depends on 10)

The device according to claim 10, wherein combining the group of computing tasks into the target computing task comprises:
obtaining a group of generation logics corresponding to the group of computing tasks, each generation logic in the group of generation logics being used for generating an executable instruction for a corresponding computing task; and
combining the group of generation logics into a target logic for generating an executable instruction for the target computing task.

### Claim 18 (depends on 10)

The device according to claim 10, wherein the computing resources comprise at least one of memory resources and thread resources.

### Claim 19

A computer program product tangibly stored in a computer-readable medium and comprising machine-executable instructions, wherein the machine-executable instructions, when executed, cause a machine to execute a method for processing a computing job, the method comprising:
determining a first dependency relationship between a plurality of computing tasks included in a to-be-processed computing job;
determining, based on the first dependency relationship and demands of the plurality of computing tasks for computing resources, a group of computing tasks for combination from the plurality of computing tasks;
combining the group of computing tasks into a target computing task; and
determining, based on the first dependency relationship, a second dependency relationship between the target computing task and computing tasks that are other than the group of computing tasks in the plurality of computing tasks.

### Claim 20 (depends on 19)

The computer program product according to claim 19, wherein determining the group of computing tasks from the plurality of computing tasks comprises:
determining, for each computing task of the plurality of computing tasks and based on the first dependency relationship, the number of computing tasks associated with at least one of an input or an output of a corresponding computing task;
determining a first group of candidate tasks from the plurality of computing tasks, wherein the number determined for each candidate task is less than a threshold number;
determining, based on demands of the first group of candidate tasks for the computing resources, a second group of candidate tasks for combination from the first group of candidate tasks; and
selecting the group of computing tasks from the second group of candidate tasks.
