Task scheduling in a GPU using wakeup event state data

Patent metadata

Field	Value
Publication number	US-11720399-B2
Application number	US-202117540009-A
Country	US
Kind code	B2
Filing date	Dec 1, 2021
Priority date	Sep 23, 2016
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

A method of scheduling tasks within a GPU or other highly parallel processing unit is described which is both age-aware and wakeup event driven. Tasks which are received are added to an age-based task queue. Wakeup event bits for task types, or combinations of task types and data groups, are set in response to completion of a task dependency and these wakeup event bits are used to select an oldest task from the queue that satisfies predefined criteria.

First claim

What is claimed is:

1. A method of scheduling tasks in a task queue within a processor, the task queue comprising tasks having task identifiers, wherein a task identifier is a task type identifier or a source identifier, the method comprising:
in response to receiving, at a task scheduling engine, an indication that a dependency for a task in the task queue has completed, updating wakeup event state data of the processor to indicate a wakeup event for the task identifier of the task;
identifying one or more candidate task types or sources based on the wakeup event state data indicating a wakeup event; and
selecting a task for execution based on the identified one or more candidate task types or sources.

2. The method according to claim 1 , further comprising, in response to receiving an indication that a dependency for a task in the task queue has completed, clearing a state bit for the task that relates to the completed dependency.

3. The method according to claim 1 , wherein updating wakeup event state data for the task identifier of the task comprises setting a wakeup event state bit for a task type or source corresponding to the task identifier of the task.

4. The method according to claim 1 , wherein a task has a both a task identifier and a data group identifier,
wherein the wakeup event state data is updated for a combination of the task type or source corresponding to the task identifier of the task and the data group corresponding to the data group identifier of the task,
and wherein selecting a task for execution based on the identified one or more candidate task types or sources comprises:
selecting a task for execution based on the identified one or more candidate task types or sources that has a task identifier and data group identifier that correspond to wakeup event state data that has been updated.

5. The method according to claim 4 , wherein a wakeup event state bit is set for the combination of the task type or source corresponding to the task identifier of the task and the data group corresponding to the data group identifier of the task and selecting a task for execution based on the identified one or more candidate task types or sources that has a task identifier and data group identifier that correspond to wakeup event state data that has been updated comprises:
selecting a task for execution based on the identified one or more candidate task types or sources that has a task identifier and data group identifier that correspond to a wakeup event state bit that has been set.

6. The method according to claim 4 , further comprising:
in response to determining that the selected task does not have all its dependencies met, clearing the wakeup event state data for the task identifier and data group identifier of the identified task; and
selecting a task for execution based on the identified one or more candidate task types or sources that has a task identifier and data group identifier that correspond to wakeup event state data that has been updated.

7. The method according to claim 1 , further comprising:
in response to receiving a task at the task scheduling engine, adding the task to the task queue.

8. The method according to claim 1 , further comprising:
in response to receiving, at the task scheduling engine, an indication that a task has completed execution, removing the task from the task queue.

9. The method according to claim 1 , further comprising:
in response to receiving, at the task scheduling engine, an indication that a task has completed execution, determining if the task is a first phase task of a multi-phase task;
in response to determining that the task is not a first phase task of a multi-phase task, removing the task from the task queue; and
in response to determining that the task is a first phase task of a multi-phase task, scheduling a second phase task of the multi-phase task.

10. The method according to claim 9 , wherein selecting a task for execution based on the identified one or more candidate task types or sources further comprises prioritizing selection of a task that is a second phase task of a multi-phase task over tasks that are not second phase tasks.

11. A scheduler for a processor comprising:
a task scheduling engine;
a task queue comprising tasks having task identifiers, wherein a task identifier is a task type identifier or a source identifier; and
a data store arranged to store wakeup state data;

wherein the task scheduling engine comprises:
a first hardware logic block arranged, in response to receiving an indication that a dependency for a task in the task queue has completed, to update wakeup event state data of the processor to indicate a wakeup event for the task identifier of the task; and
a second hardware logic block arranged to identify one or more candidate task types or sources based on the wakeup event state data indicating a wakeup event and to select a task for execution based on the identified one or more candidate task types or sources.

12. The scheduler according to claim 11 , wherein the wakeup state data comprises a plurality of wakeup state bits.

13. The scheduler according to claim 12 ,
wherein the first hardware logic is arranged, in response to receiving an indication that a dependency for a task in the task queue has completed, to clear a state bit for the task that relates to the completed dependency and to update a wakeup event state bit for a task type or source corresponding to the task identifier of the task,
and wherein the second hardware logic block is arranged to identify one or more candidate task types or sources based on the wakeup event state bits and to select a task for execution based on the identified one or more candidate task types or sources.

14. The scheduler according to claim 13 , wherein a task has a both a task identifier and a data group identifier,
wherein the first hardware logic block is arranged to set a wakeup event state bit for a combination of the task type or source corresponding to the task identifier of the task and the data group corresponding to the data group identifier of the task,
and wherein the second hardware logic block is arranged to select a task for execution based on the identified one or more candidate task types or sources that has a task identifier and data group identifier that correspond to a wakeup event state bit that has been updated.

15. The scheduler according to claim 14 , wherein the second logic block is further arranged, in response to determining that the selected task does not have all its dependencies met, to clear the wakeup event state bit for the task identifier and data group identifier of the identified task and to select a task for execution based on the identified one or more candidate task types or sources that has a task type identifier and data group identifier that correspond to a wakeup event state bit that has been set.

16. The scheduler according to claim 11 , further comprising:
a third hardware logic block arranged, in response to receiving a task, to add the task to the task queue.

17. The scheduler according to claim 11 , further comprising:
a fourth hardware logic block arranged, in response to receiving an indication that a task has completed execution, to remove the task from the task queue.

18. The scheduler according to claim 11 , further comprising:
a fourth hardware logic block arranged, in response to receiving an indication that a task has completed execution, to determine if the task is a first phase task of a multi-phase task; and in response

Assignees

• Imagination Tech Ltd

Inventors

• Nield Simon
• De Grasse Adam
• Iuliano Luca
• Mower Ollie
• Foo Yoong-Chert

Classifications

• G06F9/4881 Primary

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

• G06F1/329

  by task scheduling · CPC title

• G06F9/4893

  taking into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206) · CPC title

• G06F9/5027

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

• G06F2209/483

  Multiproc · CPC title