Task scheduling in a GPU

Patent metadata

Field	Value
Publication number	US-10503547-B2
Application number	US-201916412197-A
Country	US
Kind code	B2
Filing date	May 14, 2019
Priority date	Sep 23, 2016
Publication date	Dec 10, 2019
Grant date	Dec 10, 2019

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 type identifiers and associated state data identifying any task specific dependencies, 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 the state data for the task that relates to the completed dependency to indicate that the dependency has completed and updating wakeup event state data of the processor to indicate a wakeup event for the task type identifier of the task;
identifying one or more candidate task types 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.

2. The method according to claim 1 , wherein updating state data for the task that relates to the completed dependency comprises 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 type identifier of the task comprises setting a wakeup event state bit for a task type corresponding to the task type identifier of the task.

4. The method according to claim 1 , wherein a task has a both a task type identifier and a data group identifier,
wherein the wakeup event state data is updated for a combination of the task type corresponding to the task type 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 comprises:
selecting a task for execution based on the identified one or more candidate task types that has a task type 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 corresponding to the task type 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 that has a task type 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 that has a task type 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 type 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 that has a task type 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 and setting state data for the task to identify any dependencies for the task.

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 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 type identifiers and associated state data identifying any task specific dependencies; and
a data store arranged to store wakeup state data,

and 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 the state data for the task that relates to the completed dependency to indicate that the dependency has completed by clearing the state data for the task and to update wakeup event state data of the processor to indicate a wakeup event for the task type identifier of the task;
a second hardware logic block arranged to identify one or more candidate task types 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.

12. The scheduler according to claim 11 , wherein the wakeup state data comprises a plurality of wakeup state bits,
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 corresponding to the task type identifier of the task,
and wherein the second hardware logic block is arranged to identify one or more candidate task types based on the wakeup event state bits and to select a task for execution based on the identified one or more candidate task types.

13. The scheduler according to claim 12 , wherein a task has a both a task type 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 corresponding to the task type 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 that has a task type identifier and data group identifier that correspond to a wakeup event state bit that has been updated.

14. The scheduler according to claim 13 , 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 type 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 that has a task type identifier and data group identifier that correspond to a wakeup event state bit that has been set.

15. The scheduler according to claim 11 , wherein the task queue comprises state data associated with each task stored in the task queue and the scheduler further comprises:
a third hardware logic block arranged, in response to receiving a task, to add the task to the task queue and set the state data for the task to identify any dependencies for the task.

16. The scheduler according to claim 15 , wherein the state data comprises a plurality of state bits.

17. The scheduler according to cl

Assignees

• Imagination Tech Ltd

Inventors

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

Classifications

• 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/4881 Primary

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

• G06F1/329 Primary

  by task scheduling · CPC title

• G06F2209/486

  Scheduler internals · CPC title

• G06F2209/483

  Multiproc · CPC title