# US 2017/0255496 A1 · Method for scheduling data flow task and apparatus

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

- Number: US 2017/0255496 A1
- Document ID: US20170255496A1
- Status: Published application
- Kind: A1
- Application number: 15/598,696
- Filed: 2017-05-18
- Published: 2017-09-07
- Earliest claimed: 2014-11-19
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Liqun Deng; Junhua Zhu
- Web page: https://patentgrep.com/patent/US20170255496A1

## CPC

- G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5044: {considering hardware capabilities}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for scheduling a data flow task and an apparatus. The method includes: preprocessing a data flow task to obtain at least one subtask; classifying the subtask into a central processing unit (CPU) task group, a graphics processing unit (GPU) task group, or a to-be-determined task group; allocating the subtask to a working node; when the subtask belongs to the CPU task group, determining that a CPU executes the subtask; when the subtask belongs to the GPU task group, determining that a GPU executes the subtask; or when the subtask belongs to the to-be-determined task group, determining, according to costs of executing the subtask by a CPU and a GPU, a running platform (e.g., the CPU or the GPU) executes the subtask, where the cost includes duration of executing the subtask.

## Claims

### Claim 1

A method for scheduling a data flow task in a distributed heterogeneous system comprising at least one working node, the method comprising:
preprocessing the data flow task to obtain at least one subtask;
classifying a first subtask in the at least one subtask into a task group, wherein task groups of the distributed heterogeneous system comprise a central processing unit (CPU) task group, a graphics processing unit (GPU) task group, and a to-be-determined task group;
allocating the first subtask to a first working node in the at least one working node according to the task group to which the first subtask belongs and a resource status of the at least one working node; and
determining that a CPU corresponding to the first working node executes the first subtask when the first subtask belongs to the CPU task group; determining that a GPU corresponding to the first working node executes the first subtask when the first subtask belongs to the GPU task group; and determining, according to costs of executing the first subtask by a CPU and a GPU, a running platform that executes the first subtask when the first subtask belongs to the to-be-determined task group, wherein the cost comprises duration of executing the subtask.

### Claim 2 (depends on 1)

The method according to claim 1, wherein classifying a first subtask in the at least one subtask into a task group comprises:
classifying the first subtask into the CPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the CPU;
classifying the first subtask into the GPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the GPU; and
estimating first duration of executing the first subtask by the CPU and second duration of executing the first subtask by the GPU when the first subtask does not comprise indication information, and classifying the first subtask into a task group according to the first duration and the second duration.

### Claim 3 (depends on 2)

The method according to claim 2, wherein classifying the first subtask into a task group according to the first duration and the second duration comprises:
classifying the first subtask into the CPU task group if a ratio of the first duration to the second duration is less than a first preset threshold;
classifying the first subtask into the GPU task group if a ratio of the first duration to the second duration is greater than a second preset threshold; and
classifying the first subtask into the to-be-determined task group if a ratio of the first duration to the second duration is not less than the first preset threshold and is not greater than the second preset threshold.

### Claim 4 (depends on 1)

The method according to claim 1, further comprising:
recording execution log information of the first subtask into a performance database, wherein the execution log information comprises a data volume of the first subtask, required waiting duration before the first subtask is executed, and a running platform and running duration of the first subtask.

### Claim 5 (depends on 4)

The method according to claim 4, further comprising:
querying the performance database, and calculating first average duration of executing subtasks by the CPU corresponding to the first working node and second average duration of executing the subtasks by the GPU corresponding to the first working node; and
adjusting, according to the first average duration and the second average duration, subtasks distribution on the first working node.

### Claim 6 (depends on 5)

The method according to claim 5, wherein adjusting, according to the first average duration and the second average duration, subtasks distribution on the first working node comprises:
allocating first O subtasks that are in the to-be-determined task group on the first working node and that have greatest acceleration ratios to the GPU task group on the first working node if the first average duration is greater than the second average duration, wherein the acceleration ratio is a ratio of a time of executing a subtask by the CPU to a time of executing the subtask by the GPU; and
allocating first P subtasks that are in the to-be-determined task group on the first working node and that have smallest acceleration ratios to the CPU task group on the first working node if the first average duration is less than the second average duration, wherein O and P are positive integers.

### Claim 7 (depends on 5)

The method according to claim 5, wherein adjusting, according to the first average duration and the second average duration, subtasks distribution on the first working node comprises:
allocating first O subtasks that are in the CPU task group on the first working node and that have greatest acceleration ratios to the to-be-determined task group on the first working node if the first average duration is greater than the second average duration, wherein the acceleration ratio is a ratio of a time of executing a subtask by the CPU to a time of executing the subtask by the GPU; and
allocating first P subtasks that are in the GPU task group on the first working node and that have smallest acceleration ratios to the to-be-determined task group on the first working node if the first average duration is less than the second average duration, wherein O and P are positive integers.

### Claim 8

An apparatus for use in a distributed heterogeneous system comprising at least one working node, the apparatus comprising:
a memory configured to store instructions; and
a processor coupled to the memory and configured to execute the instructions to:
preprocess a data flow task to obtain at least one subtask,
classify a first subtask in the at least one subtask into a task group, wherein task groups of the distributed heterogeneous system comprise a central processing unit (CPU) task group, a graphics processing unit (GPU) task group, and a to-be-determined task group,
allocate the first subtask to a first working node in the at least one working node according to the task group to which the first subtask belongs and a resource status of the at least one working node, and
determine that a CPU corresponding to the first working node executes the first subtask when the first subtask belongs to the CPU task group; determine that a GPU corresponding to the first working node executes the first subtask when the first subtask belongs to the GPU task group; and determine, according to costs of executing the first subtask by a CPU and a GPU, a running platform that executes the first subtask when the first subtask belongs to the to-be-determined task group, wherein the cost comprises duration of executing the subtask.

### Claim 9 (depends on 8)

The apparatus according to claim 8, wherein the processor is configured to:
classify the first subtask into the CPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the CPU;
classify the first subtask into the GPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the GPU; and
estimate first duration of executing the first subtask by the CPU and second duration of executing the first subtask by the GPU when the first subtask does not comprise indication information, and classify the first subtask into a task group according to the first duration and the second duration.

### Claim 10 (depends on 8)

The apparatus according to claim 8, wherein the processor is configured to:
classify the first subtask into the CPU task group if a ratio of the first duration to the second duration is less than a first preset threshold;
classify the first subtask into the GPU task group if a ratio of the first duration to the second duration is greater than a second preset threshold; and
classify the first subtask into the to-be-determined task group if a ratio of the first duration to the second duration is not less than the first preset threshold and is not greater than the second preset threshold.

### Claim 11 (depends on 8)

The apparatus according to claim 8, wherein the processor is further configured to:
record execution log information of the first subtask into a performance database, wherein the execution log information comprises a data volume of the first subtask, required waiting duration before the first subtask is executed, and a running platform and running duration of the first subtask.

### Claim 12 (depends on 11)

The apparatus according to claim 11, wherein the processor is further configured to:
query the performance database, and calculate first average duration of executing subtasks by the CPU corresponding to the first working node and second average duration of executing the subtasks by the GPU corresponding to the first working node; and
adjust, according to the first average duration and the second average duration, subtasks distribution on the first working node.

### Claim 13 (depends on 12)

The apparatus according to claim 12, wherein the processor is configured to:
allocate first O subtasks that are in the to-be-determined task group on the first working node and that have greatest acceleration ratios to the GPU task group on the first working node if the first average duration is greater than the second average duration, wherein the acceleration ratio is a ratio of a time of executing a subtask by the CPU to a time of executing the subtask by the GPU; and
allocate first P subtasks that are in the to-be-determined task group on the first working node and that have smallest acceleration ratios to the CPU task group on the first working node if the first average duration is less than the second average duration, wherein O and P are positive integers.

### Claim 14 (depends on 12)

The apparatus according to claim 12, wherein the processor is configured to:
allocate first O subtasks that are in the CPU task group on the first working node and that have greatest acceleration ratios to the to-be-determined task group on the first working node if the first average duration is greater than the second average duration, wherein the acceleration ratio is a ratio of a time of executing a subtask by the CPU to a time of executing the subtask by the GPU; and
allocate first P subtasks that are in the GPU task group on the first working node and that have smallest acceleration ratios to the to-be-determined task group on the first working node if the first average duration is less than the second average duration, wherein O and P are positive integers.

### Claim 15

A distributed heterogeneous system, comprising:
at least one working node; and
a scheduling apparatus configured to:
preprocess a data flow task to obtain at least one subtask,
classify a first subtask in the at least one subtask into a task group, wherein task groups of the distributed heterogeneous system comprise a central processing unit (CPU) task group, a graphics processing unit (GPU) task group, and a to-be-determined task group,
allocate the first subtask to a first working node in the at least one working node according to the task group to which the first subtask belongs and a resource status of the at least one working node, and
determine that a CPU corresponding to the first working node executes the first subtask when the first subtask belongs to the CPU task group; determine that a GPU corresponding to the first working node executes the first subtask when the first subtask belongs to the GPU task group; and determine, according to costs of executing the first subtask by a CPU and a GPU, a running platform that executes the first subtask when the first subtask belongs to the to-be-determined task group, wherein the cost comprises duration of executing the subtask.

### Claim 16 (depends on 15)

The system according to claim 15, wherein the scheduling apparatus is configured to:
classify the first subtask into the CPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the CPU;
classify the first subtask into the GPU task group when the first subtask comprises indication information indicating that the first subtask is executed by the GPU; and
estimate first duration of executing the first subtask by the CPU and second duration of executing the first subtask by the GPU when the first subtask does not comprise indication information, and classify the first subtask into a task group according to the first duration and the second duration.

### Claim 17 (depends on 15)

The system according to claim 15, wherein the scheduling apparatus is configured to:
classify the first subtask into the CPU task group if a ratio of the first duration to the second duration is less than a first preset threshold;
classify the first subtask into the GPU task group if a ratio of the first duration to the second duration is greater than a second preset threshold; and
classify the first subtask into the to-be-determined task group if a ratio of the first duration to the second duration is not less than the first preset threshold and is not greater than the second preset threshold.

### Claim 18 (depends on 15)

The system according to claim 15, wherein the scheduling apparatus is further configured to:
record execution log information of the first subtask into a performance database, wherein the execution log information comprises a data volume of the first subtask, required waiting duration before the first subtask is executed, and a running platform and running duration of the first subtask.

### Claim 19 (depends on 18)

The system according to claim 18, wherein the scheduling apparatus is further configured to:
query the performance database, and calculate first average duration of executing subtasks by the CPU corresponding to the first working node and second average duration of executing the subtasks by the GPU corresponding to the first working node; and
adjust, according to the first average duration and the second average duration, subtasks distribution on the first working node.

### Claim 20 (depends on 19)

The system according to claim 19, wherein the scheduling apparatus is configured to:
allocate first O subtasks that are in the to-be-determined task group on the first working node and that have greatest acceleration ratios to the GPU task group on the first working node if the first average duration is greater than the second average duration, wherein the acceleration ratio is a ratio of a time of executing a subtask by the CPU to a time of executing the subtask by the GPU; and
allocate first P subtasks that are in the to-be-determined task group on the first working node and that have smallest acceleration ratios to the CPU task group on the first working node if the first average duration is less than the second average duration, wherein O and P are positive integers.
